본문 바로가기
반응형

PS 문제 풀이/Jungol101

[Jungol] 정올 1156 책 복사하기2 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=436&sca=40 Approach Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com [탐색] Parametric Search [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 .. 2021. 3. 2.
[Jungol] 정올 2306 두 용액 출처: [Jungol] 2306 두 용액 Input 5 -2 4 -99 -1 98 Output -99 98 같은 문제 다른 풀이: [BOJ] 2470 두 용액 [BOJ] 백준 2470 두 용액 출처: https://www.acmicpc.net/problem/2470 Input 5 -2 4 -99 -1 98 Output -99 98 ※ 같은 문제 다른 풀이: [Jungol] 2306 두 용액 [Jungol] 정올 2306 두 용액 출처: [Jungol] 2306 두 용액 Input 5 -.. zoosso.tistory.com ① 실제로 채점되는 Input Data는 정렬되어 있지 않기 때문에 주어진 숫자 정렬 ex) {-2 4 -99 -1 98} → {-99 -2 -1 4 98} ② 두 개의 인덱스 low.. 2021. 2. 28.
[Jungol] 정올 3429 로봇 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2751 Input 3 2 10 1 2 5 Output 1 로봇의 이동거리를 최소화하는 것이기 때문에 몇대의 로봇이든 움직이든 이동거리만 최소화하면 상관없습니다. 이 문제를 해결하기 위해서는 로봇의 감시 영역에 대한 구간합을 통해서 해결할 수 있습니다. 특정 지점에 두 개의 로봇이 놓일 수 없으며, 감시 영역을 최적화하기 위해 인접한 두 로봇의 감시 영역을 생각해보자. ▶ arr[i] = robot[i] - robot[i-1] - 2*R ex) 2 - 1 - (2×2) = -3 두 영역은 『-1』 만큼 겹처서 감시를 하고 있습니다. 감시 거리 R = 2인 상태에서 최적의 구간은 아래와 같습니다.. 2021. 2. 28.
[Jungol] 정올 3263 연속구간최대합(Circular) 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2556&sca=50&page=22 Input 10 4 5 -10 3 4 -7 -2 8 -6 -1 Output 10 * 대부분의 원형 문제는 직선으로 바꾸어 해결할 수 있다. 직선 구간에서 연속 구간의 최대합을 구하는 것은 DP를 이용해 빠르게 구할 수있습니다 원형으로 이루어져 있기에 해가 나올 수 있는 부분은 2가지 입니다. ① 중간 부분의 연속된 합 (DP로 빠르게 구할 수 있음) ② 끝 지점과 시작 시점이 포함되는 영역 즉, 직선에서의 연속구간 최대합은 ①만 고려해주면 되지만 원형이기 때문에 ②도 고려해주어야 합니다. ▶ ①과 ② 중 더 큰 값이 원형구간에서 최대값이 됩니다. Q. 시작과 끝이 .. 2021. 2. 28.
[Jungol] 정올 1836 연속부분합 찾기 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1109&sca=20 Input 4 1 2 -2 4 Output 5 #include const int LM = 100005; int N, ans, sum; int main(void) { // freopen("input.txt", "r", stdin); int i, num; scanf("%d", &N); for (i = 0; i 0) sum += num; else sum = num; if (ans < sum) ans = sum; } printf("%d\n", ans); return 0; } 2021. 2. 28.
[Jungol] 정올 2497 수열 출처: http://www.hancom.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1758&sca=50 Input 10 2 3 -2 -4 -9 0 3 7 13 8 -3 Output 21 psum[i] = 첫번째 원소부터 i번 원소까지의 구간합 ▶ A[i] = psum[i] - psum[i-1] ex) A[3] = -4 = psum[3] - psum[2] = -3 - 1 = -4 ▶ (K ≤ i) K 길이의 구간 합 = psum[i] - psum[i - K] ex) 구간 [8, 9] 합 = psum[9] - psum[7] = 19 - (-2) = 21 = A[8] + A[9] = 13 + 8 psum[9] - psum[7] = (1~9까지의 합) - (1~7 까지.. 2021. 2. 28.
[Jungol] 정올 3706 합이 0이 되는 연속구간 세기 출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3055&sca=99&page=24 Input 4 5 -5 -7 7 Output 3 ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색, 삭제가 가능하다. - 매우 빠른 응답을 요구하는 상황에 유용 (Hash는 최소(최대) 원소를 찾는 것 zoosso.tistory.com 연속구간의 합을 구해야 한다는 점에서 prefix sum을 이용하면 좋을 것 같다는 생각이 듭니다. 간단하게 생각했을 때는 psum = 0인 개수만 찾으면 되지 않을까 생각할 수 있지만, psum = 0이 아니어도 문제에서 요구한 구간의 합 = 0.. 2021. 2. 28.
[Jungol] 정올 3136 const 구간의 합 구하기(2D) 출처: 정올(Jungol) Input 5 1 2 3 4 5 6 7 8 9 0 -1 2 1 1 1 5 2 3 1 4 1 0 1 0 1 3 2 1 2 1 3 3 5 5 1 1 5 5 Output 6 13 67 쿼리에서 묻는 (sri, sci) ~ (eri, eci)는 다음과 같습니다. ex) (3, 3) ~ (5, 5) ▶ 1 + 1 + 1 + 3 + 1 + 4 + 1+ 1 + 1 = 13 ★ DP[i][j] = (0, 0) ~ (i, j) 영역 합 각 영역을 구할 때, 이중 for문으로 구하면 TLE 발생 ▶ DP[i][j] = DP[i - 1][j] + DP[i][j - 1] - DP[i - 1][j - 1] + x; (x = 해당 위치의 숫자를 의미합니다.) ex) DP[3][3] = 29 구한다고 가.. 2021. 2. 28.
[Jungol] 정올 1437 같은 모양 찾기 출처: [Jungol] 정올 1437 같은 모양 찾기 Input 10 0000000001 1110011100 0100101000 0100101000 1111111111 0000101000 0000001000 0010010000 1111110000 0010010001 3 100 111 100 Output 2 ① 이중 for문으로 좌측 상단을 기준으로 잡아서 주어진 패턴과 일치하는지 확인합니다. (+ 이중 for문) ② 90°, 180°, 270° 회전한 모양에 대해서도 동일하게 수행해야 하므로 패턴을 90° 회전하면서 과정 ①을 3번 더 수행합니다. #include const int MAX_M = 100 + 5; const int MAX_P = 100 + 5; int ans = 0; int M, P; in.. 2021. 2. 28.
[Jungol] 정올 2097 지하철 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1360&sca=4050 Input 5 5 0 2 2 5 9 2 0 3 4 8 2 3 0 7 6 5 4 7 0 5 9 5 6 5 0 Output 8 1 3 5 BFS 탐색할 때, 재방문 방지를 위해서 보통 visited[][] 배열을 두어서 재방문 여부를 확인합니다. 하지만 최단거리의 경우에는 재방문하더라도 더 나은 비용(cost)로 방문할 수 있습니다. 그렇기 때문에 vistied[][] 배열 값에 단순히 『0』, 『1』 로 방문 확인하지 않고 비용(cost)을 두어서 더 나은 경로인 경우 허용합니다. ※ 최단 거리의 경로 각 지점을 순회하면서 지금까지 온 경로를 누적할 수도 있지만 효율적이.. 2021. 2. 27.
반응형

티스토리툴바