그래프 탐색 알고리즘 (DFS / BFS) Stack (스택 자료구조) 1) 먼저 들어간 데이터가 나중에 나가는 자료 구조 (선입후출) 2) 구성 : 삽입 & 삭제 - list(), append(), pop()을 사용 - list[::-1] : 최하단 원소부터 출력 - list : 최상단 원소부터 출력 Queue (큐 자료구조) 1) 먼저 들어간 데이터가 먼저 나가는 자료 구조 (선입선출) 2) 구성 : from collections import deque 라이브러리 사용 - queue = deque() : 큐 구현 - queue.append() - queue.popleft() : 먼저 들어간 데이터 뽑아내기 - queue.reverse() : 역순 3) 억지로 리스트 자료형을 사용하지 말고 라이브러리를 사용하여 시간복잡도를 줄인다. Recurs.. Python/Coding Test 4년 전
Greedy Algorithm 그리디 알고리즘 (탐욕법) 1) 개요 - 현재 상황에서 가장 좋은 것만 고르는 방법 - 최적의 해를 구할 수 있는지 정당성 분석이 요구됨 - 코딩테스트의 경우에 한해서, 이를 이용한 방법이 최적의 해가 구해지는 상황이라고 생각해야함 2) 샘플 문제 - 임의의 수 N이 1이 될 때가지 두 과정 중 반복 선택하여야 하는데 두번째는 나누어 떨어질 때만 선택 가능 (1) N 에서 1 빼기 (2) N에서 K 나누기 n, k = map(int, input().split()) # 내가 푼 방법 (숫자가 커지면 시간복잡도가 높아짐) cnt = 0 while True: if n == 1: break elif n % k == 0: n //= k cnt += 1 else: n -= 1 cnt += 1 print(cnt) #.. Python/Coding Test 4년 전