알고리즘
-
[Graph] 그래프의 탐색 - 너비 우선 탐색 (BFS, Breadth-First Search)알고리즘, 코딩테스트/알고리즘 개념 2023. 12. 18. 01:21
다양한 그래프 탐색 알고리즘이 있지만 가장 기본이 되면서 대표적인 알고리즘은 바로 DFS와 BFS다. 특히 DFS와 BFS는 탐색 방법이 상반되는 만큼 특징과 용도가 확실히 구분되는 편이기 때문에 두 탐색 방법 모두 확실히 이해하고 자유자재로 활용할 수 있어야 한다. 나아가 문제를 만났을 때 어떤 탐색 방식을 사용하는 것이 좋을지 결정할 수 있도록 그 특징을 이해하고 다양한 유형의 문제를 접해보는 것이 좋다. 너비 우선 탐색 (BFS, Breadth-First Search) DFS와 함께 대표적인 그래프 탐색 알고리즘 중 하나다. 깊이 우선 탐색인 DFS와 대조적인 탐색 방법으로 한가지 경로씩 끝까지 탐색하는 DFS와 달리 각 노드의 인접한 노드들부터 탐색해가는 특징을 가진다. 따라서 시작지점에 가까운 ..
-
[Graph] 그래프의 탐색 - 깊이 우선 탐색 (DFS, Depth-First Search)알고리즘, 코딩테스트/알고리즘 개념 2023. 12. 5. 02:12
알고리즘 문제에서 가장 큰 비중을 차지하는 유형 중 하나가 바로 그래프 탐색 문제다. 어떤 형태의 코딩 테스트, 알고리즘 시험에서든 가장 쉽게 만날 수 있는 문제 유형이기도 하고 여러 문제가 출제되는 형식이라면 반드시 한문제 이상 포함된다고 할 수 있을 정도다. 그래프 탐색 알고리즘은 필수 중 필수이기 때문에 반드시 익숙해져야 한다. 깊이 우선 탐색 (DFS, Depth-First Search) DFS는 대표적인 그래프 탐색 알고리즘 중 하나다. 직관적인 이름 그대로 깊이를 따라서 탐색해나가는 방법으로 너비 우선 탐색(BFS)과 대조되는 특징을 가진다. BFS의 경우 동시에 여러 갈래의 길을 뻗어나가듯 탐색한다면 DFS는 일반적으로 미로찾기를 해나갈 때와 같이 분기점에서 하나의 길을 선택하고 그 길을 따..
-
[백준 BOJ/C++] 4803 트리알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 10. 10. 00:54
4803번: 트리 기본적인 사이클 탐지 알고리즘 문제다. 그래프(Graph) 내에서 사이클(Cycle) 이 존재하는지를 찾는 문제는 흔한 그래프 탐색 문제 유형 중 하나다. 이 문제에서는 트리(Tree) 의 정의를 이용해서 주어진 그래프 내에서 사이클이 존재하는지 확인하고 사이클을 이루는 노드들에 연결되지 않은 트리의 수를 찾아야 한다. 트리는 그래프의 한 종류로 그래프가 트리가 되기 위해서는 몇가지 조건이 있지만 이 문제에서는 사이클만 신경써주면 된다. 문제에서 입력 자체가 두 노드 사이에 간선은 하나만 주어지고 간선에 가중치가 있는것도 아니기 때문에 사이클의 존재 여부로만 트리인지 아닌지 판단할 수 있다. 단, 주의해야하는 점은 예제로 주어진 입력과 같이 주어지는 간선정보에 포함되지 않은, 다른 노드..
-
[백준 BOJ/C++] 2668 숫자 고르기알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 10. 3. 00:55
2668번: 숫자 고르기 문제를 처음 접하면 아이디어가 잘 떠오르지 않는 어려운 문제이기도 하지만 막상 제대로 파악하고 나면 의외로 간단히 풀 수 있는 문제다. 그래프(Graph)와 관련된 문제이고 사이클(Cycle)을 찾는 문제임을 발견하기만 한다면 그 이후부터는 크게 까다로울 것은 없다. 문제는 정체를 알 수 없는 표가 주어지고 여기에서 집합을 찾는다는 표현으로 접근 방법을 어렵게하고 있다. 이 문제의 핵심은 바로 이 표가 그래프로 나타내어질 수 있음을 발견하는 것 그리고 찾고자 하는 집합의 조건이 그래프에서 사이클을 형성하는 노드들임을 발견하는 것이다. 대놓고 그래프 문제임을 보여주거나 연결과 탐색, 경로와 같이 큰 고민 없이 그래프로 연상할 수 있는 키워드를 사용하는 문제들도 많지만 이렇게 특이한..
-
[백준 BOJ/C++] 1240 노드사이의 거리알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 30. 02:07
1240번: 노드사이의 거리 간선정보를 입력받아 그래프의 최단거리를 구하는 문제다. 아주 기본에 가까운 문제라 최단거리 알고리즘의 기본기를 연습하기 좋은 문제라고 할 수 있다. 시작점과 끝점 여러개를 입력받아 거리를 구해야한다는 점과 문제 설명이 자세하지 않다는 점 정도가 고민해봐야할 부분이다. 문제 설명이 아주 간단한데 말 그대로 주어진 그래프에서 특정 두 노드의 거리를 구해주면 된다. 두 노드 사이의 간선에 방향성이 있는지, 여러개의 간선이 같은 두 노드 사이에 존재할 수 있는지 등 일반적인 그래프 탐색 문제에서 주어지는 설명은 한마디로 압축하고있다. 트리는 두 노드 사이에 간선이 하나만 존재하며 간선에 방향이 존재하지 않는다. 또한 트리는 사이클이 없는 그래프일 뿐이므로 BFS나 DFS와 같은 그래..
-
[백준 BOJ/C++] 10026 적록색약알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 25. 00:39
10026번: 적록색약 BFS, DFS 등을 이용해 2차원 맵을 탐색하는 그래프 탐색 문제다. 기본적이고 전형적인 유형에 아주 약간의 아이디어로 살짝 난이도를 올려놓아서 아주 까다롭지 않게 그래프 탐색 기본기를 익히기 좋은 문제라고 할 수 있다. RGB로 표현한 2차원 맵을 탐색하는 문제다. 보통 주어진 2차원 맵을 탐색하는 문제에서 요구하는 목표는 길을 찾거나 맵 상 구분되는 영역의 크기를 구하거나 영역의 수를 세는 형태로 자주 등장한다. 여기에 추가적으로는 맵을 변화시키는 등의 요소를 더하는 것이 대부분이다. 이 문제도 색상 지도와 적록색약을 가져와 결국 맵에 변화 요소를 주고 변화 전, 후의 영역의 수를 구하도록 하는 문제다. R과, G, B를 모두 구분하도록 그래프를 탐색시켜 적록색약이 아닌 사람..
-
[백준 BOJ/C++] 11497 통나무 건너뛰기알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 17. 23:16
11497번: 통나무 건너뛰기 정렬을 이용해서 그리디(Greedy)한 방법으로 풀 수 있는 전형적인 유형의 문제다. 그리디 알고리즘을 이용해야하는 문제들이 아이디어를 떠올리기만 하면 풀이가 간단해지는데 이 문제 역시 마찬가지다. 하지만 실버1 난이도의 문제인 만큼 핵심 아이디어를 찾기 까다롭지는 않은 편이다. 그림과 같이 통나무들을 원형으로 배치해 하나씩 건너 뛸 수 있게 한다는 컨셉이다. 문제에서 요구하는 것은 통나무들의 순서를 조정해서 바로 인접한 통나무의 높이 차이가 최소가 되어 뛰어다니기 쉽게 만드는 것이다. 각 통나무들의 높이가 주어졌을 때 인접한 통나무들의 높이차이 중 가장 큰 차이를 최소로 만들어 그 값을 출력하면 된다. 단 통나무들은 일직선으로 펼쳐진 것이 아니라 원형으로 양 끝이 연결된 ..
-
[Graph] 그래프의 표현 - 인접 행렬과 인접 리스트 (Adjacency Matrix, Adjacency List)알고리즘, 코딩테스트/알고리즘 개념 2023. 9. 12. 01:38
그래프(Graph) 탐색 문제를 풀기 위해서 가장 먼저 고려해야하는 것은 그 그래프를 어떻게 자료구조로 표현할지에 대한 것이다. DFS든 BFS든, 최단경로를 찾아내기 위한 다익스트라(Dijkstra)를 이용하든 일단 그래프를 프로그램으로 적절히 옮겨와야 무엇이든 해볼 수 있다. 정점 (Node 또는 Vertex) 과 간선 (Edge)으로 구성된 그래프를 자료구조로 표현하는 방법에는 인접행렬 (Adjacency Matrix)과 인접 리스트 (Adjacency List), 두가지가 있다. 각각 이름에서 알 수 있듯이 행렬(배열)을 이용해 표현하는 방법과 리스트를 이용하는 방법이다. 여기에서 말하는 '인접'은 두 노드 간 간선이 연결되어있음을 뜻한다. 그래프에서 두 노드가 간선으로 연결되어있다면 인접했다고 ..