Hello, Freakin world!

www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 단순히 DFS 한 번에 풀 수 있는 문제인 줄 알았지만, 처리해야될 예외 사항이 좀 있습니다. 각 서브트리 루트에 리프노드의 개수를 저장하는 알고리즘이 있다고 합시다. 그 알고리즘을 이용해 위와 같은 결과를 만들어 냈습니다. 여기서 2번 노드를 지우려면 루트 노드의 값(3)에서 2번 노드의 값(1)을 빼면 답이 됩니다. 하지만... 다음의 경우는 어떨까요? 위에서 1번 노드를 제거하면 값이 0이 되어버립니..

www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이 문제를 풀면서 너무 아쉬웠다. 아마 10월 코드 챌린지 3번과 비슷한 문제가 아닌가 싶었다. 트리 부분을 너무 소홀히했다. 크 3솔이 눈에 아른거린다. 풀이 방법은 트리를 순회하면서 현재 노드를 기점으로 가장 긴 간선을 계산하고 자손의 수에 따라 가장 큰 2개나 한개를 현재 노드가 중심이 되는 지름이라고 한다. 아 이게 말로 설명하기는 조금 버겁다. 재귀를 이해한다면 코드를 보는게 낫다...

www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 방법 전체 배열을 반으로 나눠 완전탐색을 통해 모든 부분수열의 합을 찾아내 각각 leftList, rightList에 저장합니다. 그리고 부분수열의 합이 저장된 leftList, rightList를 크기순으로 정렬합니다. (저는 하나는 오름차순, 다른 하나는 내림차순 정렬했습니다.) 인덱스를 조정해가면서 N^2 복잡도로 모든 합을 검색하는게 아니라 스위핑 방식으로 N..

www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻�� www.acmicpc.net 문제 이름이 뭔가 엄청나보이지만 그냥 전형적인 플로이드 와샬 문제였다. 모든 정점에 대해서 BFS를 수행해서도 풀 수 있는 듯 보인다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer..

www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; /* 경로 찾기 */ public class Main { static int n; static int[][] adj; public static void main(String[] args) throws IOException { /..

www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0� www.acmicpc.net 물론 언어에서 제공하는 우선순위 큐를 이용할 수도 있겠지만... 그닥 재미는 없어보인다. 구현 방식에 특별하게 추가하는 건 없다. 기존의 전형적인 힙 구현 코드에 요소가 같을 경우 작은 수를 반환한다는 조건을 추가하면 된다. (그럼에도 불구하고 8번 틀렸다 ㅋㅋㅋㅋㅋ. >= 와 > 차이로 인한 차이였는데 왠만한 테스트케이스가 다 맞게 나와서 더 애를 먹었다. 테스트 케이스 찾기는 포기하고..

www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색시 종결 조건에 대해서 정리하려고 합니다. 우선 위의 상황을 간단하게 설명하겠습니다. 우리는 이 문제와 같이 어떤 특정 값(max)에 최대한 근접하는 최대값을 찾고 싶습니다. 위 사진은 이분 탐색을 통해 범위를 2개까지 좁힌 상태이고 a < max < b 이므로 답은 a가 나와야 합니다. 범위를 이분하는 방식은 (low + high)/2 에서 계산한 값을 기준으로 max보다 클 경우 왼쪽 범위, ..

www.acmicpc.net/problem/17827 17827번: 달팽이 리스트 첫째 줄에 노드의 개수 N(2 ≤ N ≤ 200,000), 질문의 횟수 M(1 ≤ M ≤ 200,000), N번 노드가 가리키는 노드의 번호 V(2 ≤ V ≤ N)가 공백으로 구분되어 주어진다. 둘째 줄에 N개의 정수 C1, C2, …, CN이 공백 www.acmicpc.net 전체 배열에서 어느 부분만 순환하는 부분 구조를 지니는 부분에서 K번째 요소를 찾으려고 합니다. 순환하는 크기만큼만 나머지 연산을 해주고 순환하지 않는 부분만큼 자리 이동해주면 해당 요소를 찾을 수 있습니다. 자세한 건 코드 주석을 확인하세용 팁) 개인적으로 배열에 나머지 연산을 할 때, 처음 인덱스를 1로 하는것보다 0으로 하는게 더 편했습니다. ..

www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net V-A 거리에 대해 자면서 이동한 날을 구해 범위를 좁힌 다음, 이동한 날을 계산합니다. 코드의 주석을 참고하세요. import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; /* 달팽이는 올라가고 싶다 https://www.acmicpc.net/problem/2869 */ public class Main { static long a,b,v; p..

www.acmicpc.net/problem/1959 1959번: 달팽이3 첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다. 둘째 줄에 끝나는 점의 좌표를 출력한다. 왼쪽 위 칸의 좌표를 (1, 1), 오른쪽 아래 칸의 좌표를 (M, N)이라고 하자. www.acmicpc.net 입력의 크기가 어마어마하기 때문에 직접 그리면서 화살표가 꺾이는 부분을 일일이 체크할 수 없다(꺾이는 부분을 curve point라고 부르기로 하자). 이럴 경우 규칙을 찾아내 복잡도를 줄이든지 답을 내는 식을 찾든지 해야 된다. 자, 이제 다음과 같은 M,N 크기의 사각형이 있다고 하자. 사각형의 가장 자리를 다 돌고 이제 빨간색 사각형으로 순회를 시작하려고 한다. 위 그림처럼 내부에 빨간색 사각형처럼 내..