그래프
-
[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는 일반적으로 미로찾기를 해나갈 때와 같이 분기점에서 하나의 길을 선택하고 그 길을 따..
-
[Graph] 그래프의 표현 - 인접 행렬과 인접 리스트 (Adjacency Matrix, Adjacency List)알고리즘, 코딩테스트/알고리즘 개념 2023. 9. 12. 01:38
그래프(Graph) 탐색 문제를 풀기 위해서 가장 먼저 고려해야하는 것은 그 그래프를 어떻게 자료구조로 표현할지에 대한 것이다. DFS든 BFS든, 최단경로를 찾아내기 위한 다익스트라(Dijkstra)를 이용하든 일단 그래프를 프로그램으로 적절히 옮겨와야 무엇이든 해볼 수 있다. 정점 (Node 또는 Vertex) 과 간선 (Edge)으로 구성된 그래프를 자료구조로 표현하는 방법에는 인접행렬 (Adjacency Matrix)과 인접 리스트 (Adjacency List), 두가지가 있다. 각각 이름에서 알 수 있듯이 행렬(배열)을 이용해 표현하는 방법과 리스트를 이용하는 방법이다. 여기에서 말하는 '인접'은 두 노드 간 간선이 연결되어있음을 뜻한다. 그래프에서 두 노드가 간선으로 연결되어있다면 인접했다고 ..
-
[백준 BOJ/C++] 5214 환승알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 2. 02:00
5214번: 환승 단순한 최단거리 탐색 문제로 보이지만 의외로 정답비율이 낮은편이고 헷갈릴 수 있는 부분이 있는 문제다. 하이퍼튜브라는 컨셉을 문제에서 의도한대로 머릿속에 그리는데 어려움이 있었다. 문제 설명은 아주 짧고 간단하다. K개의 역이 주어지고 이 중 1번역에서 N번역까지 도달하는 최단경로를 찾아주면 된다. 간선에는 가중치도 없기 때문에 그냥 보기에는 상당히 간단해 보였다. 하지만 금방 하이퍼튜브라는 컨셉을 정확히 이해하지 못했음을 깨달았다. 주어지는 경로상 존재하는 역들을 모두 각각 연결하고 하이퍼튜브로 연결된 경로에 대한 비용은 1로 계산 하는 형태로 이해하고 풀었었는데 메모리 제한에 걸리는 상황이 발생했다. 문제의 설명도 너무 짧아 더욱 이해하기 어려웠다. 문제의 포인트 하이퍼튜브 컨셉 이..
-
[백준 BOJ/C++] 1707 이분 그래프알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 28. 01:04
1707번: 이분 그래프 이분 그래프 (Bipartite Graph) 의 개념을 알고있거나 문제에서 빠르게 이해했다면 그리 어렵지 않은 탐색 문제다. 하지만 문제의 설명이 짧고 친절하지도 않은 편이라 혼란스러울 수 있는 부분들이 있었다. 노골적으로 그래프 문제임을 보여주고있지만 자세한 설명이나 예시 없이 이분 그래프인지 아닌지를 판별하도록 하고있다. 이분 그래프라는 개념을 어느정도 알고 있었다면 그나마 접근이 용이하겠지만 그렇지 않은 경우 예시도 없는 한줄 설명 만으로 빠르고 정확히 이해하기에는 쉽지 않은 편이었다. 문제 자체에서 여러번 탐색이 필요하다거나 특정 알고리즘을 사용한다거나 구현 양이 많아지는 문제는 아니지만 생소할 수 있는 문제라 한번쯤 풀어보면 좋을 문제다. 문제의 포인트 이분 그래프의 개..
-
[백준 BOJ/C++] 9466 텀 프로젝트알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 23. 23:20
9466번: 텀 프로젝트 그래프에서 사이클을 찾고 사이클을 이루지 않는 노드들의 갯수를 세는 문제다. 제한시간에 걸리지 않기 위해서는 탐색했던 노드를 다시 방문하지 않도록 해야 한다. 학생들이 노드로 주어지며 다른 학생을 지목하는 간선을 통해서 그래프(Graph)가 만들어진다. 그래프에서 사이클(Cycle) 은 특정 노드에서 탐색해가다가 다시 해당 노드로 돌아오게되는 형태의 연결을 말한다. 팀은 자기 자신을 지목한 학생이나 사이클을 이루는 학생들로 만들어지며 팀을 이루지 못한 학생들의 수를 카운트 하면 된다. 문제는 간단해 보이지만 일반적인 그래프 탐색 알고리즘 보다 고민하고 체크해야할 것이 추가되어 난이도가 꽤 있는 편이다. 중복을 피하기 위해 방문했던 노드를 체크해야 하는데 추가적으로 싸이클에 포함되..
-
[백준 BOJ/C++] 1092 배알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 23:03
1092번: 배 전형적인 그리디 알고리즘 문제이지만 시간 초과 가능성을 고려해야 한다. 특별한 복잡한 스킬이 필요하진 않지만 그리드 적인 접근 방식을 연습하기 좋은 문제다. N대의 크레인에 M개의 박스를 최소 횟수로 옮기는 문제다. 각 크레인에는 무게 제한이 있어서 제한 내의 무게를 가진 박스만 옮길 수 있다. 크레인에 박스를 효율적으로 배분해서 최소 몇 회 만에 옮길 수 있는지 찾아야 한다. 문제의 포인트 그리디 알고리즘 시간초과를 피하는 방법 그리디 알고리즘 Greedy Algorithm은 사실 특별한 기술이나 전형적인 틀이 있는 유형은 아니다. 어찌보면 그만큼 발견이나 아이디어가 중요다고 할 수 있다. 그래도 그리드 알고리즘 문제를 여럿 풀다보면 어느정도 접근 방법에 대한 감을 기를 수 있다. 숫자..
-
[백준 BOJ/C++] 1774 우주신과의 교감알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 22:48
1774번: 우주신과의 교감 크루스칼 알고리즘을 연습해보기 좋은 문제다. 특별히 복잡하게 꼬아놓은 부분은 없는데 사전에 일부 간선만 주어지고 나머지 가능한 모든 간선을 추가하는 과정만 추가되었다. 입력으로 주어지는 모든 노드들 사이에 가능한 모든 간선들을 list up 하고 각 간선의 길이를 계산해두고 이를 토대로 크루스칼 알고리즘을 이용해 최소 신장 트리를 찾아주면 된다. 단, 입력으로 주어지는 이미 연결된 통로는 최소 신장 트리에 반드시 포함되어야 하며 새로 추가한 간선들의 길이의 합을 출력해야 한다. 문제의 포인트 최소 신장 트리를 구할 수 있는가? 간선의 길이는 주어지지 않는다. 최소 신장 트리 사이클 없이 모든 노드를 연결하는 최소 신장 트리 (MST, Minimum Spanning Tree)만..