빛나는 아이디어✨

5.2.1 BFS (Breadth-First-Search) 알고리즘 너비 우선 탐색 : 가까운 노드부터 차례대로 탐색하는 알고리즘 BFS 는 가장 가까운 노드부터 방문한 후, 다시 돌아가 다른 경로를 탐색하는 알고리즘을 말한다. 따라서, BFS 는 큐 자료구조 (선입선출) 를 이용하여 구현할 수 있다. BFS 동작 과정은 다음과 같다. 1) 큐에 탐색 시작 노드를 삽입하고, 방문값을 true 로 바꾼다. 2) 큐에서 방문하지 않은 인접노드를 모두 큐에 넣고, 방문값을 true 로 바꾼다. 4) 더 이상 방문할 노드가 없을 때까지 1, 2 번의 과정을 반복한다. 5.2.2 BFS 알고리즘 특징 BFS 알고리즘은 큐 자료구조를 이용하여 구현된다. 하지만, 실제 알고리즘을 구현할 때, 큐보다 deque 라이브..

5.1.1 DFS (Depth-First-Search) 알고리즘 깊이 우선 탐색 : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS 는 최대한 깊숙이 노드들을 방문한 후, 다시 돌아가 다른 경로를 탐색하는 알고리즘을 말한다. 따라서, DFS 는 스택 자료구조를 이용하여 구현할 수 있다. DFS 동작 과정은 다음과 같다. 1) 스택에 탐색 노드를 삽입하고, 방문값을 true 로 바꾼다. 2) 스택의 최상단 노드에서 방문하지 않은 인접노드를 스택에 넣고, 방문값을 true 로 바꾼다. 3) 스택의 최상단 노드에서 방분하지 않은 인접노드가 없으면, 단순히 최상단 노드를 꺼낸다. 4) 스택에 값이 없을 때까지 2, 3 번의 과정을 반복한다. 5.1.2 DFS 알고리즘 특징 DFS 알고리즘은 스택 자료..

4.1 구현 알고리즘 머릿속에 있는 알고리즘을 정확하고 빠르게 코드로 작성해야 하는 알고리즘 구현은 머릿속으로 구상한 알고리즘을 소스코드로 작성하는 과정을 말한다. 코딩 테스트에서 구현이란 조금 더 좁은 의미로 사용되는데, 풀이는 떠올리기는 쉽지만, 소스코드를 작성하기 어려운 문제를 말한다. 알고리즘 문제를 해결할 때, 정확한 풀이 방법을 떠올리더라도, 소스코드로 구현하지 못하는 경우가 있다. 따라서 구현문제에서는, 프로그래밍 문법을 정확히 알고, 실수 없이 답안 코드를 작성하는 능력이 요구된다. 4.2 구현 알고리즘 문제유형 구현 문제는 알고리즘을 설계하기는 쉽지만, 소스코드로 옮기기 어려운 문제를 말한다. 이러한 문제들은 사소한 조건이 설정되어 있는 경우가 많다. 구현 문제는 다음과 같은 유형으로 나..

3.1 그리디(Greedy) 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘은 탐욕법 이라고도 불리며, 현재 상황에서 가장 최선의 선택만을 하는 알고리즘이다. 즉, 현재의 선택이 나중에 미칠 영향은 고려되지 않는다. 3.2 그리디 알고리즘 문제유형 그리디 알고리즘 문제유형은 다른 유형에 비해, 사전에 외우고 있지 않아도 풀 수 있을 가능성이 매우 높은 문제 유형이다. 하지만 문제를 풀기 위한 아이디어와 창의력을 요구한다. 따라서 많은 문제 유형을 접하고 풀어보는 훈련이 필요하다. 먼저, 코딩테스트에는 문제 유형을 바로 파악하기 어렵다면, 그리디 문제를 의심해본다. 하지만 정당한 탐욕적 해결법이 없다면, 다이나믹 프로그래밍 / 그래프 알고리즘을 고민해보자. 또한, 그리디 문제에서는..