혼자 공부하는 공간

안녕하세요 GODZ입니다. 오늘은 동적 프로그래밍을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 동적 프로그래밍에서 가장 중요한 것은 해결했던 문제에 대해서 다시 문제를 풀지 않는 것이다. 이전에 풀었던 문제를 메모이제이션(Memoization)을 통해 다시 계산하지 않고 결과 값만 가져온다. * res[k] : k원을 만들 수 있는 경우의 수 * cArr[i] : i번 째 동전의 값 * res[k] += res[k - cArr[i]] : k원을 만들 수 있는 경우의 수에 k - cArr[i]원을 만들 수 있는 경우의 수의 합 [설명] * cArr[i]가 1원일 때, 10원을 만들기 위해서는 res[10] += res[9] ---> cArr[i]가 1원일 때의 res[10] ..

안녕하세요 GODZ입니다. 오늘은 이분 탐색을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 정렬한 뒤, 최대값에서 빼가면서 총 예산(M)을 맞추는 것은 각 예산 값들이 100,000 이하인 것을 감안하면 시간 제한(1초)를 맞출 수 없다. 따라서 이분 탐색을 통해 시간 복잡도를 log로 변환하여 작업을 줄이도록 한다. 예산의 값 중 최대값을 찾는다. 최소값과 최대값의 평균값(mid)을 구해 각 예산에 상한선을 적용한 뒤, 총 예산과 비교한다. 총 예산보다 작으면, mid값을 저장하고 mid값을 최소값으로 설정한 뒤 4번 작업 반복. 총 예산보다 크면, mid값을 최대값으로 설정한 뒤 4번 작업 반복. 최대값과 최소값이 같으면 반복을 종료하고, 저장된 mid값 중 가장 큰 값을..

안녕하세요 GODZ입니다. 오늘은 이분 탐색과 투 포인터를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 N개의 수를 하나씩 입력 받으면서 합 sum을 구한다. sum >= S 일 때, 길이 len을 저장하고 0번 인덱스부터 S보다 작아질 때까지 sum에서 뺀다. sum = S 일 때, 2번 작업 반복. 모든 수를 다 입력 받았으면 저장한 길이 len 중 최소값을 찾는다. 만약 저장한 길이 len이 존재하지 않는다면 0을 출력한다. 4. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..

안녕하세요 GODZ입니다. 오늘은 문자열을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 원본 문자열의 길이 N(1이상 1백만 이하), 비교 문자열의 길이 M(1이상 36이하) 일 때, 원본 문자열을 한 번 순회하면서 비교 문자열을 지우는 작업은 O(NM)의 시간 복잡도를 가진다. O(NM)의 복잡도가 수없이 반복되기 때문에 제한시간을 맞출 수 없다. 따라서 문자열을 순회하면서 비교 문자열과 비교하는 작업을 병행한다. 원본 문자열을 저장할 자료구조는 StringBuilder나 Stack 그 외 List와 같은 mutable 구조를 사용하면 된다. 어떤 자료구조를 사용하든 간에 남은 원본 문자열을 출력해야 하므로 StringBuilder가 다른 자료구조에 비해 빠르다. 4. 코드..

안녕하세요 GODZ입니다. 오늘은 세그먼트 트리를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 개념 세그먼트 트리(Segment Tree)는 연속적인 여러 개의 데이터가 존재할 때, 특정 범위 데이터만 처리하기 위해 사용하는 자료구조 입니다. 예를 들어, 배열(arr)에 {10, 9, 8, 7, 6, 5, 4, 3, 2, 1} 이라는 원소가 선형구조로 존재합니다. 여기서 인덱스는 1부터 시작이라고 가정하고 1부터 4, 5부터 8, 3부터 9, 7부터 9 에서의 최솟값을 구하는 기능을 하게끔 만들어야 한다고 합시다. 구현할 때 해당 인덱스(1, 4 // 5, 8 // 3, 9 // 7, 9)를 모두 순회하면서 구해야할 것입니다. 이때 배열 크기가 N, 최솟값을 구하는 횟수가 M 이라..