개발자 모드

오늘은 정렬방법 중, 위상정렬에 대해서 알아보겠습니다. 위상정렬 위상 정렬(Topological Sort)는 사이클이 없는 방향 그래프에서 정점을 선형 순서로 나열하는 것입니다. 여기서 선형 순서란 일렬로 줄 세우는 것이라고 봐도 되겠습니다. 위상정렬 예제 그럼 위상정렬에 대해서 알아보기 전에!! 왜 위상정렬을 사용하는지, 어떤 경우에 사용하는지에 대해서 알아봅시다. 위와 같은 교과목 체계도가 있다고 해봅시다. 화살표는 선수과목을 의미합니다. 가령, 자료구조는 알고리즘의 선수과목인 것처럼 말이죠. 그런데 여기서 제가 어떤 순서로 들어야할지, 특정 과목부터 시작한다고 하면 무엇을 들을 수 있는지를 위상정렬을 통해서 알아볼 수 있습니다. 만약 위 교과목 체계도에서 위상정렬을 사용한다면, 많은 결과 중 아래와..

오늘은 이전 글에서 다룬 그래프에 대한 연장선으로 그래프에서 모든 정점을 탐색하는 방법 중 DFS를 다뤄보겠습니다. DFS란? DFS는 Depth-First Search의 줄임말로, 깊이를 우선으로 하여 탐색하는 방식을 의미합니다. 하나의 정점으로 시작하여, 그 정점과 이웃한 정점 중 하나를 방문합니다. 방금 방문한 정점에서 다시 이웃한 정점을 확인하고, 이웃한 정점들 중 하나를 방문합니다. 이와 같이 진행하는 방식을 DFS라고 합니다. 아래의 그림으로 확인해봅시다. 위와 같은 그래프가 있다고 가정해봅시다.(사실은 트리라고도 볼 수 있습니다.) 위 트리에서 가장 상위의 정점을 시작으로 DFS를 진행한다면 정점 내에 쓰여진 숫자 순서대로 방문합니다. DFS의 구현 자바로 구현한 DFS를 확인해보겠습니다. ..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중..

오늘은 기본적인 알고리즘인 DFS와 BFS에 대해서 알아보겠습니다. BFS란? BFS란 Breadth-First Search의 약자로 번역하면 너비 우선 탐색입니다. 이는 트리 구조에서 많이 사용되곤 합니다. 어떤 대상 노드로부터 가장 가깝게 연결된 노드들부터 탐색하며 순차적으로 트리의 전체를 순회하는 구조를 일컫습니다. (트리의 용어가 어색한 분들은, 아래의 그림을 보고 우선은 단순하게 이런 식으로 생긴 놈이구나 라고 생각하시면 좋을 것 같습니다.) 아래의 자료를 보면 금방 이해하실 수 있습니다. 루트 노드인 1로부터 가장 가깝게 연결된 3개를 순서대로 순회합니다. 그 후, 2와 연결된 노드를 방문하고, 최종적으로는 트리의 모든 노드를 방문하는 방법입니다. 그럼 BFS의 소스 코드를 살펴보겠습니다. 제..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 1. 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상..