1. DFS/BFS란? 1-1. 그래프 DFS/BFS에 대해 이해하려면 먼저 그래프의 기본 구조를 알아야한다. 그래프는 노드(Node)와 간선(Edge)으로 표현되며 이 때 노드를 정점(Vertex)라고 말한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말하며 두 노드가 간선으로 연결되어 있을 때 ‘인접하다’고 표현한다. 그래프는 크게 2가지 방식으로 표현할 수 있다. 인접 행렬(Adjacency Matrix) 인접 리스트(Adjacency List) 먼저 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 인접 리스트 방식은 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결해서 저장한다. 인접 행렬 방식은 노드 개수가 많을수록 메모리가 불필요하게 ..
1. 구현 알고리즘이란? 코딩 테스트에서 구현이란 “머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정”이다. 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이라고 할 수 있기 때문에 대부분 별도의 유형으로 분류하지 않는다. 하지만 구현이 중심이 되는 문제가 자주 출제되기에 다른 알고리즘보다 먼저 다루고자 한다. 2. 예제 💡 모든 문제는 나동빈 저자의 “이것이 코딩테스트다”에 수록되어 있으며 작성한 코드는 오류가 있을 수도 있음을 미리 밝힙니다. 2-1. 상하좌우 문제 여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다. .가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A..
1. 그리디 알고리즘이란? 그리디 알고리즘은 현재 상황에서 가장 좋은 것만 선택하고 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 문제 출제의 폭이 매우 넓기 때문에 단순 암기를 통해서는 모든 문제에 대처하기 어렵다. 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 “가장 큰 순서대로”, “가장 작은 순서대로”와 같은 기준을 알게 모르게 제시해준다. 또한 대체로 정렬 알고리즘과 짝을 이뤄 출제된다. 2. 예제 💡 모든 문제는 나동빈 저자의 “이것이 코딩테스트다”에 수록되어 있으며 작성한 코드는 오류가 있을 수 있음을 미리 밝힙니다. 2-1. 큰 수의 법칙 문제 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열..
