결국 빛나리라

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ DFS (Depth-First Search) 란? 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 시작노드에서 시작하여 인접한 노드들을 방문하며 가장 깊숙이 위치하는 노드에 닿을 때까지 탐색한다. 인접한 리스트가 여러개일 경우 노드의 숫자가 가장 낮은 방향으로 탐색한다. > 다음 그래프가 있을 때 DFS는 어떤식으로 탐색할까? (설명 뒤의 []는 쌓이는 스택을 표현한 것이다) - 1에서 탐색을 시작한다. [1] - 연결된 노드 2,8,6중 가장 낮은 수인 2로 탐색한다. [1,2] - 2에서 3으로 방문한다. [1..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. ▶ 재귀함수(Recursive Function)란? 자기 자신을 다시 호출하는 함수로 DFS와 BFS에 자주 활용되는 형식이다. 파이썬에서 재귀함수는 무한히 함수를 호출하다가 최대 재귀 깊이를 초과하게 되면 최대 재귀 깊이 초과메시지가 출력되며 함수실행이 종료된다. 따라서 반복문 대신 재귀함수를 사용하여 반복문을 사용하지 않고 코드를 반복할 수 있다 ▶ 재귀함수의 종료조건 재귀함수 실행을 종료시키는 조건을 명시함으로써 특정 조건을 만족하면 함수가 종료되도록 설정해야한다. 그렇지 않으면 함수가 최대 재귀깊이까지 반복될 것이다. i가 10이 되었을 때 재귀함수 호출을 중단하도록 조건을 명시하였다. 재귀함수는 호출 될 때 메모리 ..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. ▶ 탐색이란? 탐색이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정으로 DFS와 BFS가 있다. 이 유형은 코딩테스트에서 매우 자주 출되는 유형이라고 한다. DFS와 BFS에 대해 설명하기 전 먼저 알아야할 개념인 스택과 큐 자료구조에 대해 알아보고 가자. ▶ 스택 자료구조란? 먼저 들어온 데이터가 나중에 나가고 나중에 들어온 데이터가 먼저 나가는 형식으로 선입후출의 자료구조이다. 파이썬에서 스택은 append를 사용하여 원소를 추가하고 pop을 사용하여 나중에 들어온 데이터를 빼서 활용할 수 있다. 최상단 원소(나중에 들어온 원소)부터 출력하기 위해선 print(lst[::-1])로, 최하단 원소부터 출력하기 위해선 p..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. 본 포스팅에서 작성한 코드문제는 해당 저서에 나와있는 문제 일부입니다. 예시답안코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 구현이란? 내가 생각한 아이디어를 소스코드로 바꾸는 과정을 말한다. 주로 알고리즘 문제에서 구현유형이란 아이디어를 떠올리는 건 쉽지만 코드로 구현하기 어렵거나 복잡한 문제를 말한다. 해당 유형의 문제를 풀기위해 다양한 라이브러리와 사용법을 알고 많은 문제를 풀어볼수록 더 유리할 수 있다. ▶ 구현 유형 대표적으로 시뮬레이션 및 완전 탐색 문제가 자주 출제된다. 해당 유형의 문제에서 2차원 공간은 행렬을 의미한다. 특히 행렬에서 방향벡터가 자주 활..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. 본 포스팅에서 작성한 코드문제는 해당 저서에 나와있는 문제 일부입니다. https://westshine-data-analysis.tistory.com/30 그리디 알고리즘 (1) / 그리디 알고리즘이란 나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다 ▷그리디 알고리즘이란? 탐욕법으로 번역되는 해당 알고리즘은 현재 주어진 상황에서 가장 좋은 것만 고르는 방 westshine-data-analysis.tistory.com ▷ 동빈이의 큰 수의 법칙 1. 아이디어: 가장 큰 수를 M//K * K만큼 더할 수 있다. 그 외 남은 나머지 횟수만큼은 두번째로 큰수로 더한다. 만약 배열에 가장 큰 수가 중복..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다 ▷그리디 알고리즘이란? 탐욕법으로 번역되는 해당 알고리즘은 현재 주어진 상황에서 가장 좋은 것만 고르는 방법이다. 문제를 보고 해당 문제를 풀 수 있는 아이디어를 떠올리는 것이 중요하다. 코테에서 많이 출제되는 유형이지만 아이디어를 생각하는 것이 중요하기 때문에 사전에 알고리즘을 외우지않아도 충분히 풀 수 있는 문제유형이다. 아이디어를 떠올린 후에는 가장 좋아보이는 걸 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야한다. ▷ 그리디 알고리즘 풀이법 즉 그리디 알고리즘은, 1. 최소한의 아이디어를 생각해내고, 2. 아이디어의 정당성을 분석해야한다. 다른 말로 내가 생각해낸 아이디어로 해를 구하고자 할때 최적의 해를 항상..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다 프로그래머스에서 문제를 풀다보면 종종 시간초과 때문에 문제를 틀리는 경우가 발생한다. 그렇기 때문에 코드를 짤때엔 시간 복잡도를 고려해주는 것이 중요한 요소이다. ▷시간 복잡도란? 알고리즘이 특정 크기의 입력에 대해 수행하는데 얼마나 오래걸리는 지를 나타내는를 의미한다. 내가 코드를 어떻게 짜느냐에 따라 시간복잡도가 달라지기 때문에 데이터의 입력 크기에 맞춰 적절한 전략을 세워 시간복잡도를 줄이도록 노력하는 것이 중요하다. ▷ 시간복잡도 표현 - bigO 표기법 시간복잡도를 표현하는 방법으로는 bigO표기법이라는 것이 있다. 만일 2N^3 + 1000이라는 다항식이 있다고 할 때 빅오 표기법은 차수가 가장 높은 항만을 고려하여..

https://programmers.co.kr/learn/courses/30/lessons/67256/solution_groups?language=python3&type=my 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def distance(left_loc, right_loc, mid_loc): return [abs(left_loc[0]-mid_loc[0])+abs(left_loc[1]-mid_loc[1]), abs(right_loc[0]-mid_loc[0])+abs(right_loc[1]-mid_loc[1])] def solution(numbers,..

https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 로또의 순위를 매겨주는 rank함수를 만들어서 해결하였다. def rank(value): if value == 6: return 1 elif value == 5: return 2 elif value == 4: return 3 elif value == 3: return 4 elif value == 2: return 5..

https://programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 배열과 pop함수를 사용하여 풀었다. 배열을 순서대로 쌓는 과정에서 바로 이전 배열의 값과 반복되는 값이 있으면 이를 제거하고 다시 쌓아 올리는 방식을 택했다. def solution(board,moves): result_lst=[] n=0 result=0 for j in moves: for i in range(len(board)): # board배열의 해당위치에 값이 있으면 result..