문제 설명https://www.acmicpc.net/problem/1504 ▸ 문제방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. ▸ 입력첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,..
다익스트라(Dijkstra) 알고리즘에 살펴보기 전, 먼저 최단 거리(Shortest Path) 알고리즘에 대해 알아보자. 최단 거리 알고리즘(Shortest Path) 최단 거리 알고리즘은 그래프에서 두 정점 간의 최단 거리를 구하는 대표적인 알고리즘은 다음과 같다.다익스트라(Dijkstra)시작 정점에서 다른 모든 정점까지의 최단 거리를 구한다.가중치가 음수가 아닌 경우에만 사용 가능하다.벨만-포드(Bellman-Ford)시작 정점에서 다른 정점까지의 최단 거리를 구한다.음수 가중치가 존재해도 적용 가능하며, 음의 사이클이 있으면 이를 탐지할 수 있다.플로이드-워셜(Floyd-Warshall)모든 정점 쌍 사이의 최단 거리를 구한다.DP 기반의 알고리즘이다. 이 중 이번에는 다익스트라 알고리즘에 대해..
문제 설명https://www.acmicpc.net/problem/2961 ▸ 문제도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오. ▸ 입력첫째 줄에 재료의 ..
부분집합(Subset)부분집합이란 어떤 집합의 원소들로만 이루어진 집합을 말한다.집합의 원소가 총 n개라면, 공집합을 포함한 부분집합의 개수는 2ⁿ개이다.이는 각 원소를 부분집합에 포함할지/포함하지 않을지 두 가지 경우로 나눌 수 있고, 이 선택을 모든 원소에 대해 적용한 경우의 수가 2ⁿ이 되기 때문이다. 재귀를 이용한 부분집합 구현재귀 함수를 이용해 부분집합을 생성할 때는, 각 단계(인덱스)에서 다음 두 가지 선택지를 고려한다.현재 인덱스의 원소를 부분집합에 포함하는 경우현재 인덱스의 원소를 부분집합에 포함하지 않는 경우이 과정을 모든 인덱스에 대해 수행하고, 인덱스가 n에 도달하면 하나의 부분집합 구성이 완성되므로 출력한다. Java 구현 예시public class Main { public stat..
백트래킹을 이해하기 위해 먼저, 그 기반이 되는 깊이 우선 탐색(DFS)에 대해 간단히 알아보자. 깊이 우선 탐색(DFS, Depth-First Search)깊이 우선 탐색은 가능한 모든 경로를 끝까지 탐색하는 방식이다.하지만 DFS는 불필요할 것 같은 경로를 미리 차단하지 못하므로, 탐색해야 하는 경우의 수가 매우 많을 수 있다.따라서, 가능한 경우의 수가 N! 수준으로 급격히 증가하는 문제에서는 단순히 DFS만으로는 시간 안에 처리가 어려운 경우가 많다. 따라서, 모든 경우를 탐색하는 DFS의 한계를 보완하기 위해, 불필요한 경로를 미리 차단하는 백트래킹(BackTracking) 기법이 사용된다. 백트래킹(BackTracking)백트래킹은 DFS를 기반으로 한 탐색 기법으로, 해를 찾아가는 도중 현재..
문제 설명https://www.acmicpc.net/problem/11286 ▸ 문제절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.배열에 정수 x (x ≠ 0)를 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다. ▸ 입력첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는..
