알고리즘
-
외판원 순회(TSP : Traveling Salesperson Problem) 알고리즘알고리즘/알고리즘 2022. 3. 21. 00:16
외판원 순회란? 도시들이 존재하며 도시로 이동할 때 드는 비용이 주어졌을 때 불특정 한 도시에서 출발하여 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제입니다. 외판원이 가장 적은 비용으로 모든 도시를 방문하면서 자기 집으로 돌아온다고 하여 외판원 순회라는 이름이 붙었습니다. 이 문제의 특징은 비트 연산, DFS, DP를 모두 활용해서 해결해야 합니다. 만약 해당 개념을 활용하지 않고 가장 일반적으로 떠오르는 '각 도시를 잇는 모든 경로를 탐색하고 그중 최솟값을 찾자'라는 완전 탐색으로 푸는 방법도 있지만 이는 O(N!)의 시간 복잡도로 인해 시간 초과가 발생할 수 있습니다. 만약 0번째 도시에서 출발하고 남은 도시들을 어떤 순서로 방문할지만 정하면 되기 때문에 남은 n-1..
-
[백준] 2964번 : 도영이가 만든 맛있는 음식 - 자바 (JAVA)알고리즘/백준 2022. 3. 21. 00:01
https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 문제 해석 N개의 재료가 있고 각 재료는 신맛 S과 쓴맛 B가 존재한다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 재료의 신맛의 곳이고 쓴맛은 합이다. 시거나 쓴 음식을 좋아하는 사람은 많지 않기 때문에 신맛과 쓴맛의 차이를 작게 만드려고 한다. 재료는 적어도 하나 사용해야 한다. 문제 풀이 전 설계 부분집합 (조합을 사용해서 해결) 곱셈을 하며 숫자의 범위가 커질..
-
6808. 규영이와 인영이의 카드게임 - 자바(JAVA)알고리즘/SW Expert Academy 2022. 3. 19. 00:01
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWgv9va6HnkDFAW0 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 1~18까지의 수가 적인 18장의 카드가 존재한다. 아홉 라운드에 걸쳐 게임이 진행하며 한 번의 게임에 둘은 카드를 잘 섞어 9장씩 나눈다. 한 라운드에는 한 장씩 카드를 낸다. 카드의 수를 비교해서 점수를 계산한다. 높은 수가 적힌 카드를 낸 사람은 두 카드에 적힌 수의 합만큼 점수를 얻는다. 낮은 수가 적힌 카드를 낸 사람은 아무런 점수도 얻을 수 없다. 두 사람의 총점이 같으면 무승..
-
[백준] 5639 : 이진 검색 트리 - 자바(JAVA)알고리즘/백준 2022. 3. 18. 00:01
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 해석 이진트리는 다음의 조건을 만족한다. 노드의 왼쪽 서브 트리에 있는 모든 노드의 키는 부모 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 부모 노드의 키보다 크다. 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 후위 순회한 결과를 구하는 프로그램을 작성하라. 문제 풀이 전 설계 이진 검색 트리를 전위 순회한 결과를 통해 이진트리를 생성한다. 생성한..
-
[백준] 1753 : 최단경로 - 자바(JAVA)알고리즘/백준 2022. 3. 17. 23:46
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 풀이 전 설계 방향 그래프 탐색 문제이며 시작점에서 다른 모든 정점으로의 최단 경로를 구해야 합니다. 정점의 개수가 20,000개 이고 간선의 개수가 300,000이다 보니 완전 탐색은 불가능하고 정점과의 거리를 갱신시키는 다익스트라 알고리즘을 그대로 적용하면 될 것 같습니다. 정점의 개수가 많기 때문에 인접행렬보다는 인접 리스트를 이용합니다. 또는 fr..
-
[백준] 1238번 : 파티 - 자바(JAVA)알고리즘/백준 2022. 3. 17. 23:46
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 해석 N명의 학생이 X번 마을에 모여서 파티를 벌이기로 했다. 마을 사이에는 총 M개의 단방향 도루들이 있고, i번째 길을 지나는데 T(i)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 이때 최단거리를 원하며 도로들은 단방향이다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은? 문제 풀이..
-
다익스트라(Dijkstra) 알고리즘알고리즘/알고리즘 2022. 3. 17. 18:44
다익스트라 알고리즘이란? DP를 활용한 최단 경로 탐색 알고리즘입니다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다. 이때 음의 간선은 포함할 수 없습니다. 다익스트라 알고리즘이 DP 문제인 이유는 ' 최단거리는 여러 개의 최단 거리로 이루어져 있기 때문입니다.' 예제 1 예를 들어 다음 그림과 같이 1번 노드부터 다른 노드로 가는 최단 경로를 구한다고 가정해 보겠습니다. 우선 1번 노드와 인접한 2번, 3번, 4번 노드 간의 최단 거리를 구합니다. 경로 1 -> 2의 비용은 3 경로1 -> 3의 비용은 6 경로1 -> 4의 비용은 7 이후, 1번 노드와 인접하면서 가장 비용이 적은 2번 노드를 방문합니다. 경로1 ->3의 비용은 원래 6이었는데 2를 경유해서 가는 경우 4로 ..
-
[백준] 18222 : 투에-모스 문자열 - 자바(JAVA)알고리즘/백준 2022. 3. 17. 00:01
https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 문제 해석 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 문자열 X는 다음과 같은 과정으로 만들어진다. 1. X는 맨 처음에 0으로 시작한다. 2. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. 3. X의 뒤에 X'을 붙인 문자열을 X로 다시 정의한다. 4. 2~3의 과정을 무한히 반복한다. 입력 첫 번째 줄에 자연수 k (1 ≤ k ≤ 10^18..