전체
Coding Test(다이나믹 프로그래밍)
다이나믹 프로그래밍 - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과는 별도의 메모리 영역에 저장 ==> 메모이제이션(Memoization) TopDown(메모이제이션) : 하향식 BottomUp : 상향식 1. 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제(Overlapping Subproblem) - 동일한 작은 문제를 반복적으로 해결해야 한다. 다이나믹 프로그래밍 vs 분할 정복 - 2개 모두 최적 부분 구조를 가질 때 사용(큰 문제를 작은 문제로 나눌 수 있을 때) - 차이점은 부분 문제의 중복 다이나믹 프로그래밍 : 각 ..
Coding Test(이진 탐색)
순차 탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진탐색 - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 시작점, 끝점, 중간점을 이용하여 탐색 범위 설정 - 시간복잡도 : O(logN) # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: return ..
Coding Test(DFS/BFS)
스택(Stack) stack = [] stack.append(5) stack.append(2) stack.append(6) stack.pop() stack.append(3) stack.pop() 큐(Queue) from collections import deque queue = deque() queue.append(6) queue.append(2) queue.append(1) queue.popleft() queue.append(7) queue.popleft() DFS (Depth-First Search) - 깊이 우선 탐색, 깊은 부분을 우선적으로 탐색하는 알고리즘 - 스택 or 재귀 함수를 이용 장점: 최선의 경우, 가장 빠른 알고리즘이다. ‘운 좋게’ 항상 해에 도달하는 올바른 경로를 선택한다면, 깊..
Coding Test(그리디 & 구현)
그리티 알고리즘(탐욕법) - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 - 정당성 분석 중요 => 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론 구현 - 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 - 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 - 시뮬레이션 및 완전 탐색 문제에서는 방향 벡터 자주 사용 #방향벡터 #동, 북, 서, 남 dx = [0,-1,0,1] dy = [1,0,-1,0]