예니의 코딩일기

강의 "깊이 우선 탐색"은 한 정점에서 인접하고 아직 방문하지 않은 모든 정점을 방문할 때, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝내고 다음 정점으로 이동하는 알고리즘 입니다. "너비 우선 탐색"은 한 정점에서 인접하고 아직 방문하지 않은 모든 정점을 방문할 때, 방문한 각 인접 정점을 기준으로 방문한 순서에 따라 너비 우선 탐색을 행하는 알고리즘 입니다. Step 7-3: 풀어서 내 것으로 만들자! 여행 경로 ⭐ 힌트 풀이 : stack과 DFS를 이용하여 푸는 문제! def solution(tickets): routes = {} for t in tickets: routes[t[0]] = routes.get(t[0], []) + [t[1]] for r in routes: routes[r].sor..

강의 "동적계획법"은 최적화 문제를 재귀적인 방식으로 작은 부분 문제로 나누어 해를 조합하여 전체 문제의 해답에 이르는 알고리즘 입니다. 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있습니다. 응용 Knapsack Problem Step 6-3: 풀어서 내 것으로 만들자! N으로 표현 ⭐ 힌트 풀이 : 이전에 기록한 값을 다시 계산하도록 구현하는 문제! def solution(N, number): dp = [set() for i in range(8)] for i, x in enumerate(dp): x.add(int(str(N) * (i+1))) for i in range(len(dp)): for j in range(i): for op1 in dp[j]: for op2 in dp[i-..

강의 "힙"은 최대 / 최소 원소를 빠르게 찾을 수 있는 알고리즘 입니다. 힙은 완전 이진 트리 자료구조를 통해 구현합니다. max heap min heap 연산 heapify : 힙 구성. O(N log N) insert : 삽입. O(log N) remove : 삭제. O(log N) import heapq heapq.heapify(L) heap.heappush(L, x) min = heapq.heappop(L) 응용 정렬 (heapsort) 우선 순위 큐 (priority queue) Step 5-3: 풀어서 내 것으로 만들자! 더 맵게 ⭐ heapq 라이브러리를 이용하여 푸는 문제! import heapq def solution(scoville, k): heapq.heapify(scoville) ..

강의 탐욕법을 사용할 때에는 탐욕법을 사용하여도 그 뒤에 일어날 일에서도 최적의 해를 갖는지 확인해야 합니다. Step 4-3: 풀어서 내 것으로 만들자! 큰 수 만들기 ⭐ 이전에 풀었던 문제! def solution(number, k): stack = [] cnt = 0 for num in number: while stack and stack[-1] < num and cnt < k: stack.pop() cnt += 1 stack.append(num) while cnt < k: stack.pop() cnt += 1 return ''.join(stack) ⭐ 힌트 풀이 : 앞에서부터 삭제한 경우 자연스럽게 내림차순이 되는 점을 이용하는 방법! def solution(number, k): collected..

강의 "탐욕법"은 알고리즘의 각 단계에서 그 순간에 지엽적으로 최적이라고 생각되는 것을 선택하는 알고리즘 입니다. Step 2-3: 풀어서 내 것으로 만들자! 체육복 ⭐ 직관적 풀이 def solution(n, lost, reserve): stack = [0] * n for student in range(1, n+1): if student in lost: if student in reserve: stack[student-1] = 1 reserve.remove(student) else: if student-1 in reserve and student-1 not in lost: stack[student-1] = 1 reserve.remove(student-1) elif student+1 in reserve ..

강의 정렬을 사용할 때에는 제한 조건과 시간 복잡도에 주의해야 합니다. Step 3-3: 풀어서 내 것으로 만들자! 가장 큰 수 ⭐ 직관적 풀이 : 새로운 정렬 기준을 생성하여 푸는 방법! from functools import cmp_to_key def custom(a, b): if a + b > b + a: return -1 elif a + b < b + a: return 1 else: return 0 def solution(numbers): numbers = list(map(str, numbers)) sort_numbers = sorted(numbers, key = cmp_to_key(custom)) if len(sort_numbers) == sort_numbers.count("0"): sort_n..