sncap Style

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 증가하는 부분수열을의 개수를 구하는 문제이다. 그동안 DP나 TreeSet.ceiling 을 이용해서 구했는데.. ArrayList를 이용해서 구하면 많이 바르다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.C..

www.acmicpc.net/problem/15653 15653번: 구슬 탈출 4 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 많이 어렵다... 훕냐.. 손으로 해보는게 더 쉬운듯 했다. 문제는 그냥... 그냥 반복해서 풀면 된다.. BFS 문제.. import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import ja..

www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 어렵게 생각했는데.. 위상정렬 최대 값으로 해결함. DP import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public clas..

https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 문제 위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다. 창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 �� www.acmicpc.net 문제가 어렵거나, 구현이 어려운 문제는 아니지만. 제출시 오류가 났다... 한참 오류난 포인트를 찾았는데.. 핵심은 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다. 이렇게 정렬하는 방법을 빈도 정렬이라고 한다. '만약, ~~' 부터가 오류의 원인이다. 수열내 등장한 개수..

간선으로 연결하려는 두 노드가 이미 같은 집합으로 포함된 것인지를 판단해줌. 간략 코드 static class DJS { int[] mom; DJS(int n) { mom = new int[n+1]; for (int i = 1; i

다이나믹 프로그래밍(Dynamic Programming) DP, 동적 계획법 Overlapping Subproblem 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다 문제를 작은 문제로 쪼갤 수 있다 Optimal Substructure 문제의 정답을 작은 문제의 정답에서 구할 수 있다 두 번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법 기본 전략은 문제를 작은 부분 문제로 나누는 것에서 부터 시작한다 작은 부분 문제를 해결한 결과로 큰 문제를 해결할 수 있다 특징은 중복되는 부분 문제들이 있다는 것 적용 방법 문제를 더 작은 부분 문제로 나눈다 중복되는 작은 부분 문제는 한 번만 계산해서 그 결과를 저장 중복되는 작은 부분 문제들은 여러 번 계산하..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 일반적인 배낭 문제로 1차원 DP로 풀이가 가능했다. D[무게] = {최대Value} 입력받은 V, W 값을 기준으로 각 무게별 Item을 추가했을때 최대 가치를 구하도록 했음. 코드 import java.io.BufferedReader; import java.io.FileInpu..

https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄부터 M+1개의 줄에는 A, B(1≤ A,B ≤ N), C 가 주어진다. 이는 A와 B 건물에 연결된 도로가 있다는 뜻이며, C는 0(오르막길) 또는 1(내리막길)의 값을 가진다. 같은 경로 상에 2개 이상의 도로가 주어지는 경우는 없으며, 입 www.acmicpc.net 문제를 이해하는데 한참 걸렸다. 그냥 MST(크루스칼)로 푸는 문제인데.. 단 예외 조건이 있다, 오르막이 0, 내리막이 1로 ..

절단점(cut vertex): 어떤 무향 그래프의 절단점이란 이 점과 인접한 간선들을 모두 지웠을 때 해당 컴포넌트가 2개 이상으로 나뉘어지는 정점을 말한다. 위 그래프에서 1, 3, 5 정점이 각각 절단점이다. 각 지점 별로 탐색하면서, 자식의 depth가 자신의 depth보다 크거나 같다면 단절점이다. root의 경우 child node가 2이상이면 단절점이다. DFS static int dfs(int here, int d, boolean root) { D[here] = d; int ret = D[here]; int child = 0; for (int there: VT[here]) { if(D[there]==0) { child++; int df = dfs(there, d+1, false); if(!r..

https://algospot.com/judge/problem/read/FIRETRUCKS algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 위해 가능한 한 빠르게 소방차를 파견해야 합니다. 서울 시내에는 m개의 소방서가 있습니다. 화재 장소에서 가장 가까운 소방서에서 소방차를 보낸다고 할 때, 각 화재 장소에 소방차가 도달하기까지 걸리는 시간의 합을 계산하는 프로그램을 작성하세요. 각 소방서에는 소방차가 충분 algospot.com 다익스트라의 다른 시각을 볼수 있는 문제로, 기본 사상인 : 한 점에서 시작하여, 여러점의..