본문 바로가기

알고리즘6

순서가 있는 정렬 : 위상 정렬 (Topological sorting) 들어가며 오늘은 특정한 몇몇 요소끼리의 순서가 정해진 상황에서 사용할 수 있는 정렬 방법인 위상 정렬(Topological sorting)에 대하여 알아보겠습니다. 알고리즘 수학에서 위상(topology)이란 연속적인 힘에 의한 변형에도 유지되는 기하학적인 속성을 의미합니다. 이렇게만 말하면 와닿지 않으니 갓 나온 가래떡을 하나 떠올려봅시다. 길쭉한 원기둥 모양을 한 가래떡에 찢어지지 않을 정도로 적당한 힘을 가하면 원래 모양보다 늘어나거나 구부러집니다. 그러나 가래떡의 모양이 변했다고 해서 원래 가지고 있던 속성들이 모두 변하는 것은 아닙니다. 아래 그림을 한 번 보겠습니다. 예를 들어, 이렇게 가래떡을 구성하는 분자들끼리 연결된 상태들은 변하지 않죠. 여전히 서로를 꽉 붙잡고 있습니다. 이렇게 서로간.. 2023. 7. 9.
최단 경로 찾기 : 플로이드 워셜(Floyd-Warshall) 알고리즘 들어가며 오늘 살펴볼 알고리즘은 지난번에 살펴봤던 다익스트라 알고리즘과 마찬가지로 최단경로를 찾는 알고리즘 중 하나인 플로이드 워셜(Floyd-Warshall) 알고리즘입니다. 같은 목적을 가진 알고리즘이라 그런지 익숙하게 느껴지는데, 플로이드 워셜은 어떤 방법을 통해서 최단경로를 구하는지 살펴보도록 하겠습니다. 알고리즘 플로이드 워셜 알고리즘은 동적 계획법을 활용한 길찾기 알고리즘입니다. 다익스트라가 지금까지 방문한 지점에서 가장 짧은 거리에 있는 지점을 차례로 선택하여 길을 찾아가는 반면, 플로이드 워셜은 지점들 중 하나를 선택해 두 지점을 연결하는 경로 중 해당 지점을 경유하는 가장 짧은 거리를 갱신하여 저장하는 과정을 반복해 길을 찾아가는 방법입니다. 로직으로 만들기 쉽게 단계별로 살펴보면, 경로.. 2023. 5. 21.
최단 경로 찾기 : 다익스트라(Dijkstra) 알고리즘 들어가며 지난 포스트에서는 그래프를 탐색하는 두 가지 방법인 DFS와 BFS에 대해서 알아보았습니다. 이번에는 그래프 상의 최단 경로를 찾는 알고리즘 중 하나인 다익스트라(Dijkstra, 또는 데이크스트라) 알고리즘에 대해서 알아보겠습니다. 다익스트라 알고리즘은 1972년도에 튜링상을 수상했던 에츠허르 데이크스트라(Edsger Wybe Dijkstra)가 1956년에 고안한 알고리즘으로, 암스테르담에서 약혼녀와 쇼핑을 하다가 카페 테라스에서 잠깐 쉬어가던 중 "한 도시에서 다른 도시로 가는 가장 짧은 길이 무엇일까?" 를 생각하며 고안하게 되었다고 하네요. 이 알고리즘은 그래프 상의 최단 경로를 찾는 알고리즘으로, DFS나 BFS와 같이 정점과 간선으로 이루어진 구조에서 사용됩니다. 그 중에서도 간선의.. 2023. 4. 2.
그래프 탐색하기 : BFS와 DFS 그래프와 트리는 정점(Node)과 간선(Edge)으로 이루어진 자료구조입니다. 점과 선을 통해 데이터를 저장하기 때문에, 그래프의 경우 도로, 전력망, 네트워크 등 우리가 살고있는 실제 세계를 모델링하는데 많이 사용되며 트리의 경우 컴퓨터의 디렉토리와 같은 계층 구조를 모델링하는데 사용됩니다. 어떤 트리나 그래프에서 특정 노드를 찾기 위해서는 구조 전체를 탐색할 필요가 있습니다. 기존 자료구조의 형식이나 특징에 따라 효율적인 탐색을 할 수 있도록 하는 몇 가지 방법이 있는데, 대표적으로 BFS(Breadth-First Search)와 DFS(Depth-First Search) 두 가지가 있습니다. 오늘 포스팅에서는 이 두 가지 탐색 방법들의 특징과 각 방법을 사용하기 좋은 케이스 등을 알아보겠습니다. B.. 2023. 3. 24.
[C++] 백준 13549번: 숨바꼭질 3 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 규칙에 따라 특정 위치로 이동하는 최단시간을 찾는 숨바꼭질 문제 시리즈입니다. 문제에서 시작지점에 위치한 수빈이는 1초의 시간을 소모하여 +1 또는 -1 로 움직이거나, 0초의 시간을 소모하여 현재 인덱스의 두 배 지점으로 순간이동을 할 수 있습니다. 이동 방식의 가중치가 다르기 때문에 다익스트라를 사용하셔도 되고, 이 문제의 경우 단순 bfs로 해결할 수도.. 2021. 10. 7.
[C++] BOJ 에서 정해지지 않은만큼의 입력을 받을 때 얼마 전부터 백준 온라인 저지에서 문제를 꾸준히 풀고 있었지만 알고리즘 관련한 포스팅은 되도록이면 나중으로 미루거나 안하려고 했는데, 입력 관련으로 문제를 겪어서 저처럼 헤매시는분이 계실까봐 기록합니다. BOJ 5639번 문제는 이진 검색 트리를 구성하는 요소들이 전위 순회 방식으로 주어지고, 이를 후위 순회 방식으로 컨버팅하는 문제입니다. 따라서 입력으로 요소들이 들어오게 되는데, 문제는 얼마만큼의 요소가 들어오는지 알 수 없다는 점입니다. 위처럼 10,000개 이하의 요소가 들어온다는 점만 알고 있을뿐, 각 케이스에 얼마 만큼의 요소가 들어오는지는 정확히 알 수 없기 때문에 입력이 더 이상 들어오지 않을때까지 계속해서 받아줘야합니다. 처음에는 cin.eof() 를 이용하여 문제를 해결하려고 하였으나 .. 2021. 8. 24.