[문제] https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net [풀이] DFS를 이용하여 풀었다. DFS의 과정은 아래와 같다. 테스트 케이스만 보고 이진트리라고 생각하면 안된다. 정답을 저장한 변수를 0으로 초기화를 한다. 1. 더 이상 이동할 자식 노드가 없다면 0을 반환해준다. 2. 자식이 하나만 있다면 자식의 가중치 + (자식을 기준으로 DFS) 의 값이 현재 노드 위치에서의 가장 긴 지름이다. 정답은, 지름을 찾아야 하므..
[문제] https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net [풀이] 가장 핵심은 진실을 아는 사람에게는 진실을 말해야 한다는 것이다. 이를 통해 추가적으로 알 수 있는 것은 진실을 아는 사람이 있는 파티에 있는 사람들도 진실을 알아야 한다는 것이다. 파티 배열을 순환하면서, 진실을 아는 사람이 있는 배열을 파티 배열에서 제거를 하고, 진실을 알고 있는 사람들이 담긴 배열에 추가를 한다. 파티 배열을 반복할 때 파티 배열이 더 이상 줄지 않으면, 더 이상 진..
[문제] https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net [풀이] 문제 푸는 과정은 2가지로 크게 나뉜다. 1. union-find를 이용하여, 경로 정보를 입력받아 spanning tree를 만든다. 2. spanning tree의 부모를 체크하여, 여행 경로가 같은 경로상에 존재하는지 확인한다. 입력받은 도시의 길을 기반으로 spanning tree를 만들기 위해 union-find를 사용했다. spanning tree를 만들었으면 여행 경..
[문제] https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net [풀이] 투 포인터를 통해 풀었다. 입력되는 용액의 순서가 오름차순으로 정렬이 되어져 있는 상태이다. 그렇기 때문에 왼쪽에서 오른쪽 방향, 오른쪽에서 왼쪽으로 값을 찾아나가며, 0에 가까운 용액을 찾는다. 왼쪽을 가리키는 포인터 left, 오른쪽을 가리키는 포인터를 right라고 가정했을 경우에 용액 배열의 left위치와 right위치를 더한 값이 0보다 작다면, left를 1만큼 ..
[문제] https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net [풀이] 지름길 배열을 우선순위 큐에 저정을 한다 (시작점 기준으로) 이동한 거리를 저장해두는 배열을 고속도로의 길이 D 크기만큼 생성해준다. 이때 초기값을 아래과 같이 설정해준다. var arr = IntArray(D+1){i -> i} 우선순위 큐에서 값을 하나씩 꺼내어서 값이 없을 때까지 다음 과정을 반복한다. 1. 끝에서 시작을 뺀 거리가 지름길의 거리보다 클 경우에 아..
[문제] https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net [풀이] 동전 교환 문제라고 볼 수 있다. 이 문제를 동전 교환 문제로 표현한다면, 1원,2원,3원으로 특정 금액 만드는 경우 수를 찾아야 한다. 문제에 만들어야 하는 수의 최대는 10000이므로, 0부터 10000까지 경우를 미리 찾아놓으면 된다. 동전 교환 알고리즘은 다음은 식으로 표현이 가능하다 . 비용을 저장해 놓은 배..
