SH

https://www.acmicpc.net/problem/1361 브루트포스 + 문자열 처리 문제 핵심 조건1. 그리디 or 많은 조건 분기로 푸는 방법은 없거나 매우 까다롭다.2. A 혹은 B보다 더 긴 문자열을 집어넣어서 최적인 경우는 없다. 접근법 세우기1번에 의해 브루트포스를 해야하며,2번에 의해 N=50일 때 복잡도를 O( 50(50-1)/2 * 50(50-1)/2) == O(150만) 정도로 잡아서 적용할 수 있다고 생각했다. 아이디어1. str1, str2에 대해 *을 기준으로 head와 tail을 나눈다. 2.String comp1 = head1 + sub2 + tail1;String comp2 = head2 + sub1 + tail2; comp1 == comp2라면, 정답을 갱신한다.  ..

https://www.acmicpc.net/problem/1277 1번째 노드 -> N 번째 노드 (발전소) 의 최단경로(전선 길이)를 구하는 다익스트라 문제 모호한 조건, 조건을 무시해야 ac인 기이함, BFS로 비비기 시도가 겹쳐서 한 페이지 다 채울정도로 틀렸다.https://www.acmicpc.net/board/view/156457 "연결된 발전소"의 처리가 중요하다. 연결된 발전소란, 현재 발전소에서 전선 길이 0으로 도달할 수 있으며, x/y좌표 값이 바뀜을 의미한다. 두 가지 탐색을 진행한다. 1. "연결된 발전소"에 대해 비용 갱신이 발생한다면, (현재 값)을 기록하고 pq에 넣는다.2. "자신이 아닌 모든 발전소"에 대해 비용 갱신이 발생한다면, (현재 값 + 필요한 전선 길이)을 ..

https://www.acmicpc.net/problem/1238 다익스트라 문제그래프가 단방향이므로, X에 가는 경우와 갔다가 돌아오는 경우 두 번을 탐색해야 한다. 접근법 1. 돌아오는 경로 X -> ALL 탐색을 한 번 한다.2. 가는 경로 모든N -> ALL 탐색을 N번 한다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.PriorityQueue;import java.util.StringTokenizer;class Main ..

https://www.acmicpc.net/problem/1240 일반적인 그래프탐색 문제다. 플로이드-워셜도 시간복잡도 아슬하게 적용 가능하다.(단, 트리이므로 경로가 유일해서 최단 경로 알고리즘은 비효율적이다.) 그래프 탐색간 틀린 이유cost[][] 배열을 썼는데, 메모리 제한이 짠 문제여서 초과함 (경로가 유일하므로 min cost 배열 필요 없음) 풀이 1. BFSimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queu..

https://www.acmicpc.net/problem/1132 기본 아이디어1. 알파벳별로 자릿수 가중치를 기록한다. (dp로 기록했는데, 하나의 변수만 써도 충분할 것 같다.)2. 가중치가 높은 순서대로 9, 8, ... 1을 곱해서 정답에 더한다. (그리디)  0으로 시작하는 수는 없다. 이 조건을 "입력에 0으로 시작하는 수는 주어지지 않는다."로 잘못 해석했다.문제의 의도는 "0으로 시작하는 수는 사용하면 안된다." 이다. (예제랑 입력 조건으로 유추가능) 기댓값이 높은 것부터 탐색하면, 0만 남았을 때 0을 쓸 수 없으면(앞자리가 0인 수가 존재하게 되면) 답이 아니게 된다. 따라서, 기댓값이 낮은 것부터 탐색하는게 낫다. 나는 조건을 잘못봐서 전처리로 0체크만 따로 추가했다. (그래서 스파..

https://www.acmicpc.net/problem/1068 트리에서 노드를 하나 끊었을 때 리프 노드의 개수를 구하는 문제 1. 루트 노드 정하기트리에서 부모가 없는 노드는 유일하며, 루트 노드가 된다 (루트 노드를 어디로 잡냐에 따라 리프 노드 개수 또한 달라진다.)(어디던 루트로 잡아도 되지않나 해서 모호했는데, 문제에서 "연결된 노드" 가 아니라 "부모 노드" 목록이 주어진다.) 2. 노드 끊는법 정하기단순히 방문처리(vst[REMOVE] = true)한다.이러면 끊은 노드 및 서브 트리를 방문하지 않게된다. + 문제에선 한 개의 노드만 끊는다. 3. 리프 노드 기준 정하기vst[next] = false 일 때만 다음 탐색을 진행한다.다음 탐색을 한 번도 하지 않았다면 이는 곧 리프 노드다...

https://www.acmicpc.net/problem/1654 이분 탐색 문제다.난이도는 낮은데 정답률이 처참하다.이유는 함정? 디테일?이 있기 때문이다. 1. low = 0 일 때, midVal을 구하는 과정에서 divide by zero 발생(이분 탐색에서는 low까지는 탐색하므로, 1로 놓아도 된다.)2. mid가 int형일 때, mid = (high+low)가 int 범위 초과 시간 초과가 발생한다면 2번 요인으로, 오버플로 발생 및 high, low가 꼬여 의미없는 탐색을 계속 하는 경우이다.애꿏은 가지치기만 계속했다. 안해도 통과하며, K  import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arra..

https://www.acmicpc.net/problem/9024 이분 탐색으로 풀었다. (투 포인터가 나을 것 같다.) 예제 및 설명에서, K = 4 에 그 합이 가장 가까운 두 정수는 {-7, 12}, {9, -4}, {5, -2}, {5, 0}, {1, 2} 등의 다섯 종류가 있다.이 때 "가장 가까운 값"은 3, 5 둘 다 될 수 있다. 음수도 고려해야 하므로 탐색 기준을 세우는게 까다로웠다. 1. 포인터를 옮기는 기준 세우기이분 탐색을 적용하려면, 값을 순차적으로 좁힐 수 있는 기준이 필요하다.  diff = 두  원소의 합과 K의 거리 = Math.abs(K - 원소의 합) 로 놓으면, 원소의 합 원소의 값을 올려야한다. 원소의 합 > K일 때원소의 값을 내려야 한다. 2. 이분탐색 적용하기한..

https://www.acmicpc.net/problem/1749 2차원 누적 합 배열을 초기화하고, 완탐으로 모든 부분 행렬을 탐색한다.정답으로 부분 행렬 원소들의 합이 최대인 값을 출력한다. 기본 이론(누적 합 및 완탐에 둘 다 쓰임)초록 영역을 구하기 위해선 파란 영역 두개를 빼준 후, 공통 영역인 빨간 영역을 더한다.s를 누적합으로 치환하면,  이다. 해당 방식으로 누적합 배열을 초기화하고, 4중 for문을 돌며 모든 부분행렬에 대해 완탐한다.padding을 주면 경계 조건 체크를 안해도 되므로 더 효율적이다. (안했음)  오답 기록1. 정답이 음수인 경우가 있으므로, ans = 0으로 초기화하면 안된다.2. a1이 a2를 넘어가면 안된다. (구현 실수) import java.io.Buffered..

https://www.acmicpc.net/problem/6503 투 포인터 사용한 문자의 개수 n이 N이하일 동안 r++ 하며 탐색 r값을 포함했을 때 n > N이 된다면, r을 포함하지 않고 l 정보를 제외한 후 l++ 이 과정을 r이 N에 닿을 때 까지 반복 (이 때 l++해서 최적인 경우는 없으므로 종료)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int N; public static void mai..