Algorithm/concept

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]

Coding Test(Algorithm) - Python

문제 해결 과정 1. 지문 읽기 및 컴퓨터적 사고 2. 요구사항(복잡도) 분석 3. 문제 해결을 위한 아이디어 찾기 4. 소스코드 설계 및 코딩 시간 복잡도 O(n^2) => O(xlogx) => O(x) => O(logx) N의 범위 500 : O(N^3) N의 범위 2,000: O(N^2) N의 범위 100,000 : O(NlogN) N의 범위 10,000,000 : O(N) 수행 시간 측정 import time start_time = time.time() # 측정 시작 # 프로그램 소스코드 end_time = time.time() # 측정 종료 print("time:", end_time - start_time) # 수행 시간 출력 지수 표현 방식 #1,000,000,000 지수 표현 방식 a = 1..

Coding Test(Grammar) - Python

Input # map()을 이용하여 list에 저장 data = list(map(int,input().split())) [1, 1] #map()을 이용하여 두 변수에 저장 a,b = map(int,input().split()) 1 1 #sys.stdin.readline()을 사용하면 줄 바꿈 기호가 입력 되기때문에 rstrip() 같이 사용 data = list(map(str,sys.stdin.readline())) #['w', 'a', '\n'] num = list(map(str,input())) #['w', 'a'] # 123 => [1,2,3], 각 자리수 따로따로 저장됨 data = list(map(int,str(i))) data = list(map(int,input())) Dictionary #..