SH

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..

https://www.acmicpc.net/problem/2118 누적 합 + 투 포인터 시계 방향이 반시계 방향보다 짧은 거리일 동안답을 시계 방향과 비교한다. 다음 포인터는 반시계 방향이 시계 방향보다 짧은 거리임이 보장되므로답을 반시계 방향과 비교한다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int N, total, ans; static int[] sum; public static ..

https://www.acmicpc.net/problem/2230 바킹독 보고 풀음 이분 탐색을 위해 꼭 while문을 사용할 필요는 없었고,엔드 포인터의 경계조건을 2번 체크하는 것이 딜레마였는데 원래 필요한 것이라고 한다. arr[j] - arr[i] >= M 일 때, j--; 처리가 불필요한 이유는arr[i]보다 arr[i+1]은 무조건 크거나 같으므로,i에서 전처리를 했다면 j++; 동작만 필요하기 때문이다. 또한, arr[N] = Integer.MAX_VALUE로 padding해도 로직 상 AIOOB 에러가 뜨는 문제였다. (쓰려면 잘 써야한다는걸 깨닫게 해줌) import java.io.BufferedReader;import java.io.IOException;import java.io.Inp..

https://www.acmicpc.net/problem/8979 rank 구현은 맨날 헷갈림import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Comparator;import java.util.StringTokenizer;class Main { static class Country { int key, g, s, b; Country(int key, int g, int s, int b) { this.key = key; this.g = g; this.s = s; this.b = b..

https://www.acmicpc.net/problem/25395 첫 코드 야매로 푼 것 같아서 총 두번 풀어봄(왼쪽 오른쪽을 매 순간 비교해서 둘다 새로운 자동차가 연결되지 않았으면 탐색 종료) 이전 풀이더보기import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; class Main {   public static void main(String[..

https://www.acmicpc.net/problem/31230 다익스트라로 최단 경로를 구하고, 최단 경로에서 거쳐간 노드 번호를 출력하는 문제다.  접근 방법의 실패더보기더보기dist(A-> i, B -> i)는 dist(i -> A, i -> B)와 동치다. 그래서 모든 정점 Vi에 대해 dist(Vi -> A, Vi -> B)를 구하려 했다. 이는 불필요하다.정점 A, B의 탐색 2번 만으로 구할 수 있다. 이후 해당 글을 참고했다.https://cjh970422.tistory.com/entry/BOJ%EB%B0%B1%EC%A4%80-31230-%EB%AA%A8%EB%B9%84%EC%8A%A4%ED%84%B0%EB%94%94 배운 것 1. 거쳐간 노드를 찾기 위해 탐색에 경로를 같이 저장할 필..

https://www.acmicpc.net/problem/25969 그리디한 방법은 없으므로 완전 탐색을 한다.맵이 200 * 200 크기이므로, 재귀를 통한 DFS는 아마 시간초과가 날 것 같다.대신, BFS를 통해 dis(주행 거리)가 낮은 순으로 탐색하면 처음 도착했을 때 최단 거리임이 보장된다. 고려 사항[중간 지점의 방문 여부 / 패턴 사용횟수 k]에 따라 더 많은 dis를 주행했더라도 최적해일 수 있다.따라서, vst[N][M][K+1][2] 배열로 기록한다. r, c, k, vstMid가 같은데도 더 많은 dis를 주행했다면 이를 가지치기하며 탐색한다. 모호한 조건한번의 패턴 사용으로 총 n칸을 이동했더라도, dis를 1만 사용한 것으로 가정한다. (문제에 명시x 예제로 유추해야 함)impo..

https://www.acmicpc.net/problem/31091 애드 혹 문제다.문제에 대한 이해(명제), 이상/이하 조건 분리, O(N^2)미만의 접근 모두 어려웠다.  누적합으로 해당 배열을 기록한다.p[i] : 거짓말을 한 사람이 i명이라고 가정했을 때, 조건( k명 이상이다)을 만족하는 사람의 수m[i] : 거짓말을 한 사람이 i명이라고 가정했을 때, 조건( k명 이하이다)을 만족하는 사람의 수  n명 이상이 거짓말을 하고 있다면,  0~n-1명 이상이 거짓말을 하고 있다는 명제도 참이다.p[n] = p[0~n-1] + p[n] n명 이하가 거짓말을 하고 있다면,  N~n+1명 이하가 거짓말을 하고 있다는 명제도 참이다.m[n] = m[N~n+1] + m[n] import java.io.Buf..