- 문제 설명 - 문제 풀이 DFS를 사용해야 하는 문제이다. 그러나 단순히 DFS만 사용해서 풀면 탐색의 양이 무수히 많아지기 때문에 시간초과가 발생한다. 때문에 DFS + DP 메모제이션을 추가로 활용해줘야 하는 문제이다. 우선 상하좌우를 검색할때 현재 노드보다 값이 작은 곳만 향할 수 있어야 하기 때문에 배열의 크기를 arr[502][502]로 해주고, 최대값이 10000이므로 10001로 초기화 해주었다. 예제로 예시를 든다면 아래 표와 같이 나타낼 수 있다. 10001 10001 10001 10001 10001 10001 10001 10001 50 45 37 32 30 10001 10001 35 50 40 20 25 10001 10001 30 30 25 17 28 10001 10001 27 24..
- 문제 설명 - 문제 풀이 N의 수가 2 > N >> C; for (int i = 0; i > arr[i]; sort(arr, arr + N); s = 1; // 최소 거리 e = arr[N - 1] - arr[0]; // 최대 거리 while (s = mid) { router++; // mid만큼 인접거리가 늘어나면 공유기 설치 spot = arr[i]; // 인접거리 갱신을 위해 } } if (router >= C) { ans = max(ans, mid); s = mid + 1; } else { e = mid - 1; } } cout
- 문제 설명 - 문제 풀이 이분 탐색을 활용해야 하는 문제다. 예제 1과 같이 4개의 나무, 7의 길이 만큼 가져가야 할 때를 예로 들어보자. 이분 탐색을 위해 최소 잘라내는 수 1 = s, 최대 자를 수 있는 길이를 나무중에 제일 큰 나무(20 = e)라고 해보자. 그럼 그 중간값 mid = (s + e) / 2 를 기준으로 잘라낸다. 잘라낸 길이의 합이 가져가야 할 길이 7보다 크다면 mid값을 높여아 하기 때문에 s = mid + 1로 , ans = mid 갱신 (마지막은 항상 7만큼 혹은 그보다 더 가져가야 할 것이므로 정답을 mid로 갱신) 잘라낸 길이의 합이 가져가야 할 길이 7보다 작다면 mid값을 낮춰야 하기 때문에 e = mid - 1 s 가 e보다 커질때 까지 반복한 후 그 순간 mi..
- 문제 설명 - 문제 풀이 분할 정복을 이용한 거듭제곱을 활용해야 하는 문제이다. 우선 기본적으로 행렬의 곱셈을 어떻게 하는지를 이해하자면 그림과 같이 A행렬과 B행렬이 있다면 1.A행렬의 크기 (m x k) 2. B행렬의 크기 (k x n) 즉 A의 열의 갯수(k)와 B의 행의 갯수(k)가 같아야 곱셈이 성립된다. 그러면 새로운 행렬의 크기 (m x n)가 생기게 되고 이 행렬이 결과값이라고 할 수 있다. 즉 행렬의 거듭제곱은 하나의 행렬을 곱하는 것이므로 행과 열의 크기가 같아야 한다. 이 때 단순히 거듭제곱 수(B) 만큼 곱셈을 반복하게 되면, B의 범위는 1 > N >> B; for (int i = 0; i > A[..
- 문제 설명 - 문제 풀이 분할 정복을 활용해야하는 문제이다. 1. 검사하고자 하는 모든 영상(배열의 원소)들이 0만 있거나 1만 있으면 그 값만 출력하면 된다. 2. 만약 0과 1이 하나라도 섞여있으면 괄호 '(' 를 넣어 준 뒤 4개의 영역으로 재귀를 통해 분할하고, 그 뒤에 괄호 ')' 를 넣어준다. 3. 1, 2번을 반복한다. ex1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 예를 들면 이런 배열의 경우 1번 과정에서 끝이 나므로 답은 1이다. ex2 이런 경우 1번 과정이 안되므로 2번 과정을 거쳐야 하므로 괄..
- 문제 설명 - 문제 풀이 대표적인 그리디 알고리즘의 예시 문제이다. 그리디 알고리즘(greedy algorithm)이란 탐욕 알고리즘이라고도 불리는데 그리디 알고리즘의 모토는 "지금 당장 최적인 답" 을 이용하자는 것이다. 단 이 알고리즘은 지금 당장에 대해선 최적이지만 전체를 봤을 때 최적이라는 보장이 없다는게 특징이다. 이번 문제와 같은 거스름돈 문제는 무조건 최대한 가치가 높은 동전부터 나눠야하므로 그리디 알고리즘에 적합하다. 심지어 정렬이 된 상태로 주어지므로 역순으로 값이 나눠지는지를 보며 검사하기만 하면 된다. - 코드 #include using namespace std; int N, K, result = 0; int cnt[10]; int main() { ios_base::sync_wit..
- 문제 설명 - 문제 풀이 서브테스크가 있는 문제이다. 본래 문제에서는 문자열의 길이가 200,000자 이하, 질문의 수는 200,000개 이하를 조건으로 되어있는데 만약 문자열의 길이가 2,000개 이하, 질문의 수가 2,000개 이하에서만 만족하는 시간복잡도를 갖는다면 50점만 맞는다. 때문에 시간복잡도를 잘 고려해야 하는 문제이고 주의할 점은 O(n^2)을 넘지 않는 것이다. 문자열의 문자가 알파벳 소문자만 있다는 것을 이용해서 범위가 2차원이지만 arr[26][문자열의 길이]를 사용한다. 문자열의 길이만큼인 이유는 최악의 경우 문자열이 모두 같은 알파벳일 수도 있기 때문이다. 반복문을 통해 순차적으로 문자열의 문자들을 검색하고 아스키 코드 값을 이용해 arr[문자 - 97] 인 곳들을 누적합을 ..
- 문제 설명 - 문제 풀이 문제가 간단해 보이는듯 하면서도 배열을 적어보지 않으면 규칙을 찾기가 꽤 까다로웠다. 이 문제는 2차원 배열을 이용하여 풀어낼 수 있다. 이를 DP로 한다 하고 크기를 첫째 줄의 문자열의 길이 x 둘째 줄의 문자열의 길이로 해 선언해 준다. 이를 DP[i][j]라 했을때 0부터 i번째 문자열과 0부터 j번째 문자열 까지의 공통 부분 수열의 갯수를 넣어준다. 예제와 같이 ACAYKP, CAPCAK를 예로 든다면 아래 표와 같다. 행열의 첫째 줄은 0으로 한다고 가정하자. 형광칠 된 곳은 i번째 문자와 j번째 문자가 같은 지점이다. 표를 보면 규칙을 찾을 수 있는데 1. i번째 문자와 j번째 문자가 같다면 DP[i-1][j-1] + 1 을 한 것과 같다는 규칙 (대각선 위의 DP..
- 문제 설명 - 문제 풀이 처음에 문제 설명을 볼때 문제 자체를 이해하는데 은근 오래 걸렸다. 간단하게 설명해서, 길이가 1이면 1, 2, 3, 4, 5, 6, 7, 8, 9 로 9개 있다.(0으로 시작하는건 제외) 길이가 2이면 10, 21, 12, 32, 23, 43, 34, 54, 45, 65, 56, 76, 67, 87, 78, 98, 89로 총 17개가 있다. 여기서 중요하게 봐야할 점은 첫째 자리 수이다. 보면 0부터 시작해서 9로 끝나는 첫 째 자리 수를 순서대로 나열했는데, 이를 이용해 2차원 배열을 만들 수 있다. 길이 by 첫 째 자릿 수로 배열을 만들면 길이가 N이라고 할때 배열의 크기는 DP[N][10] 이 된다. 이때 편의상 코드에서는 DP[N+1][10]으로 해두겠다. 아래 그..
- 문제 설명 - 문제 풀이 백트랙킹의 가장 대표적인 문제 N-Queen이다. 기본적인 체스 룰을 알면 규칙은 쉽게 알 수 있다. 체스말 퀸은 같은 행, 열에는 위치할 수 없으므로 N*N 크기의 배열을 만들필요 없이 크키가 N인 일차원 배열을 만든 후 각 열에 몇번째 행에 퀸이 있는지 저장만 하면 된다. 한 행씩 퀸을 배치해가며 check 함수를 통해 배치한 퀸과 그 전에 배치했던 퀸들이 겹치지 않는다면 depth를 늘려간다. depth가 크기 N만큼 늘어났다면, 겹치지 않는 퀸의 경우의 수가 되었단 것이므로 경우의 수를 하나 늘려준다. 예를 들어, N = 4라면 아래와 같은 배치의 경우의 수 두 가지가 나온다. 같은 행과 열에 있는지에 대해서 체크하는건 간단하지만, 대각선에 대해서는 곧바로 생각해 내긴..
