[Algorithm] DFS/BFS 알고리즘 정리
알고리즘 1도 모르던 시절, DFS와 BFS는 주변에서 너무나 많이 언급한 탓에 익히 들었던 알고리즘이다. 그만큼 코테에서 많이 등장하는 알고리즘이다. 처음 알고리즘 배울 때 개념은 이해가 되는데 막상 구현하려고 하면 너무나 헷갈렸던 기억이 난다. 그래서 이제 두번 다시 헷갈릴 일 없도록 마지막으로!!! 확실히 개념을 정리하고 넘어가려고 한다. DFS 우선, DFS(Depth First Search)는 직역한 그대로 '깊이 우선 탐색' 알고리즘이다. 그래프에서 깊은 부분을 우선적으로 탐색한다. DFS 구현 코드는 아래와 같다. # DFS 메소드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end='') # 현재 노드와 ..
[Algorithm] Greedy(그리디) 개념 정리
수업시간에 교수님께서 그리디 알고리즘을 소개하실 때 단어 뜻 그대로 '탐욕' 알고리즘이라고 설명하셨던게 기억난다. 실제로 이 알고리즘은 가장 좋아보이는, 당장 좋은 것을 먼저 고르는 알고리즘이다. 대표적으로 동전 개수 구하기, 회의실 배정 등의 문제들이 있다. 무조건적으로 그리디가 최적해를 보장하지는 않기 때문에 (오히려 그리디로 최적의 해를 찾기 어렵다고 한다.) 그리디를 사용할 때는 문제 유형을 보고 판단하도록 하자. 동전문제는 그리디의 대표적인 문제인데, 이때 그리디 알고리즘으로 최적해가 보장되는 경우는 아래의 조건을 만족한 경우이다. - 동전의 액면이 모두 바로 아래 액면의 배수가 된다. 백준에 올라와있는 동전 문제는 주어진 동전들이 배수의 관계이므로 그리디 알고리즘을 사용하여 풀 수 있었다. h..
다이나믹 프로그래밍이란, 한마디로 똑같은 계산을 두번 다시 하지 않도록 하는 알고리즘이다. DP는 메모리 공간을 조금 더 사용하는 대신, 연산 속도를 증가시키는 방법이다. 따라서 한번 구한 결과값을 별도의 메모리 공간에 저장하는 방식을 따른다. 이러한 방식을 Memoization(메모이제이션)이라고 한다. DP에도 두가지 방식이 있는데 하나는 Top-Down(하향식), 하나는 Bottom-Up(상향식)이다. '이것이 코딩테스트다' 교재에도 나와있고 백준에도 나와있는 DP의 가장 베이직한 문제 "1로 만들기"를 다이나믹 프로그래밍으로 푼 코드이다. 이때 Bottom-Up(상향식)을 사용했다. Top-Down 방식으로도 구현해보려고 했는데 찾아보니 메모리 초과가 난다고... https://www.acmicp..
