개인용 뇌 도서관

1. 재귀함수 public static void dfs(int idx,int sum) { if(idx >= N){ if(sum == S) result++; return; } dfs(idx + 1, sum + arr[idx]); dfs(idx + 1, sum); } 고르고 안고른 1/2 의 모든 부분집합을 따져본 방법이다. [1,2,3,4]가 있을 경우, 1 2 3 4 (O,X) (O,X) (O,X) (O,X) 의 경우를 생각해서 고른 경우와 안고른 경우를 생각해보면 된다. public static void dfs(int[] array, int idx, int choiceCnt, String result, int K){ if(choiceCnt == 6){ System.out.println(result); ..

C++의 next_permutation 구현 static boolean next_permutation(int[] a) { int i = a.length-1; while (i > 0 && a[i-1] >= a[i]) { i -= 1; } if (i

[Gold III] 두 배열의 합 - 2143 문제 링크 성능 요약 메모리: 50704 KB, 시간: 920 ms 분류 이분 탐색(binary_search), 누적 합(prefix_sum) 문제 설명 한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오. 예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인..

[Gold III] 소수의 연속합 - 1644 문제 링크 성능 요약 메모리: 22888 KB, 시간: 1988 ms 분류 수학(math), 정수론(number_theory), 소수 판정(primality_test), 에라토스테네스의 체(sieve), 두 포인터(two_pointer) 문제 설명 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기..

[Gold IV] 부분합 - 1806 문제 링크 성능 요약 메모리: 25712 KB, 시간: 308 ms 분류 누적 합(prefix_sum), 두 포인터(two_pointer) 문제 설명 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면..

[Gold II] 2048 (Easy) - 12100 문제 링크 성능 요약 메모리: 20500 KB, 시간: 188 ms 분류 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing), 구현(implementation), 시뮬레이션(simulation) 문제 설명 2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추..

[Gold IV] 가르침 - 1062 문제 링크 성능 요약 메모리: 15372 KB, 시간: 320 ms 분류 백트래킹(backtracking), 비트마스킹(bitmask), 브루트포스 알고리즘(bruteforcing) 문제 설명 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다. 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극..

[Gold IV] 스도쿠 - 2580 문제 링크 성능 요약 메모리: 22056 KB, 시간: 424 ms 분류 백트래킹(backtracking) 문제 설명 스도쿠는 18세기 스위스 수학자가 만든 &#39;라틴 사각형&#39;이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우..

[Silver II] 가장 긴 증가하는 부분 수열 - 11053 문제 링크 성능 요약 메모리: 11944 KB, 시간: 100 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이 dp문제는 항상 그렇듯,..

[Silver I] 스티커 - 9465 문제 링크 성능 요약 메모리: 142120 KB, 시간: 672 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점..