Always Be Wise

▶ 문제 : https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net ##### 문제 ##### # 아침 산책을 즐기는 서현이는 서울과학고에 입학해서도 아침 산책을 즐기려고 합니다. # 서현이는 산책을 위해 서울과학고의 지리를 분석했고, # 그 결과 서울과학고를 N개의 장소를 N-1개의 길이 잇는 트리 형태로 단순화시킬 수 있었습니다. # 트리 구조이므로, 모든 장소를 몇 개의 길을 통해 오고 갈 수 있습니다. # 아침 산책은 시작점..

위상 정렬은 사이클이 없는 방향 그래프의 정점들을 방향성을 거스르지 않고 순서대로 나열하는 것을 의미한다. 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 위 그림과 같이 수강해야 할 과목이 세 가지 있다고 가정하자. 세 과목을 정상적으로 수강하기 위해서는 화살표의 방향대로 [자료구조 - 알고리즘 - 고급 알고리즘] 순으로 들어야 한다. 만약 [자료구조 - 고급 알고리즘 - 알고리즘] 순으로 듣고자 한다면, 해당 순서는 화살표의 방향을 거스르기 때문에 올바른 수강 순서가 아니다. 위상 정렬 알고리즘을 이해하기 위해서는 진입차수와 진출차수에 대한 개념을 알아야 한다. 진입차수(Indegree)는 특정한 정점으로 들어오는 간선의 개수를 의미..

이분 그래프는 아래 그림 처럼 그래프의 정점들이 두개의 그룹(빨간색 정점으로 이루어진 그룹, 파란색 정점으로 이루어진 그룹)으로 나뉘고, 같은 그룹의 정점들끼리는 서로 간선으로 이어지지 않는 경우를 의미한다. 간선이 없고 정점만 있는 경우도 이분 그래프이다.

▶ 문제 : https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net ##### 문제 ##### # 루트 없는 트리가 주어진다. # 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. # 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. ##### 출력 ##### # 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. ..

▶ 문제 : https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net ##### 문제 ##### # n가지 종류의 동전이 있다. # 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. # 그러면서 동전의 개수가 최소가 되도록 하려고 한다. # 각각의 동전은 몇 개라도 사용할 수 있다. # 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. ##### 입력 ##### # 첫째 줄에 n, k가..

▶ 문제 : https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net ##### 문제 ##### # 티떱숲의 지도는 R행 C열로 이루어져 있다. # 비어있는 곳은 '.'로 표시되어 있고, # 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. # 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다. # 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) # 물도 매 분마다 비어있는 칸으..

▶ 문제 : https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net ##### 문제 ##### # n×n 바둑판 모양으로 총 n2개의 방이 있다. # 일부분은 검은 방이고 나머지는 모두 흰 방이다. # 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. # 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. # 윗줄 맨 왼쪽 방은 시작 방으로서 항상 흰 방이고, # 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다. # 시작방에..

▶ 문제 : https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net ##### 문제 ##### # N개의 도시가 있다. # 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. # 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. # A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. # 도시의 번호는 1부터 N까지이다. ##### 입력 #####..

다익스트라 알고리즘(Dijkstra Algorithm)은 그래프 내 하나의 정점에서 다른 모든 정점까지의 최단 거리/경로를 구하는 알고리즘이다. BFS와 다른 점은 가중치 그래프에서도 사용 가능하다는 것이다. 다만, 그래프 내 엣지들은 모두 양수여야 한다. 다익스트라 알고리즘의 기본 동작 원리는 다음과 같다. 1. 출발 정점을 설정한다. 2. 최단 거리 테이블을 초기화한다. 이때, 초기 값은 출발 정점을 제외하고 모두 무한대 값을 가진다. 3. 출발 정점과 연결된 정점 가운데 방문하지 않는 정점들을 찾는다. 4. 그중 최단 거리가 가장 짧은 정점을선택한다. 이때, 최단 거리란 갱신하기 전 최단 거리를 의미하며 2번에서 초기화한 테이블의 값과는 다르다. 5. 해당 정점을 거쳐 다른 정점으로 가는 거리를 ..

▶ 문제 : 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번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. # 모든 도로의 거리는 1이다. # 이때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, # 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. # 또한 출발 도시 ..