Now or Never

문제링크 ( https://www.acmicpc.net/problem/1699 ) 분류 - 동적계획법 1. 풀이 힌트 - 주어진 수 n에서 뺄 수 있는 가장 큰 제곱수를 뺀 결과값의 제곱수들의 합은 이미 구했던 어떤 수의 제곱수들의 합을 나타낸다. ex) n으로 11이 주어졌을 때 11에서 뺄 수 있는 가장 큰 제곱수는 9이고 11 - 9 = 2이다. 2의 제곱수들의 합은 1^ + 1^이며, 결과적으로 11의 제곱수들의 합은 [ 2의 제곱수들의 합 (1^, 1^) + 3^ ] 이다. 즉, 이미 구했던 2의 제곱수들의 합과 뺄 수 있는 가장 큰 제곱수(+1)를 더한 값이 11을 이루는 제곱수들의 합의 개수가 된다. 2. 풀이 과정 1) n을 13까지 해서 제곱수의 합들을 공책에 나열하여 규칙을 추론해본다...

문제링크 ( https://www.acmicpc.net/problem/2470 ) 분류 - TwoPointers Algorithm 1. 풀이 힌트 - 주어진 용액들을 오름차순으로 정렬한 뒤, 양쪽 끝에 포인터를 두어 두 용액의 합이 0보다 크면 오른쪽 포인터를 왼쪽으로 한칸, 0보다 작으면 왼쪽 포인터를 오른쪽으로 한칸 옮기면서 두 포인터가 만날때 까지 각각의 합을 구하고, 도출된 합 중에서 0과 가장 가까운 결과에 해당하는 포인터가 지목하는 용액의 값을 오름차순으로 출력하면 된다. 2. 풀이 과정 1) 밑과 같이 각 용액이 주어졌을 때 먼저 오름차순으로 정렬한다 -2 4 -99 -1 98 2) 오름차순으로 정렬된 용액들 -99 -2 -1 4 98 3) 양쪽 끝에 포인터를 둔다 - 왼쪽 끝의 포인터는 파..

1. 풀이 힌트 - 두 문자열의 문자들을 하나씩 비교하기 위한 격자형의 표를 그린 뒤 왼쪽에 기입한 문자를 기준으로 한 문자씩 위쪽의 문자열들과 비교하여 공통값을 찾아가면 된다. 2. 풀이 과정 1) 위 사진과 같이 문자열 ABCBDAB와 BDCABA를 비교한다고 가정했을 때, 열에는 ABCBDAB, 행에는 BDCABA를기입한 행렬을 만든다. (직접 공책에 그려가면서 따라해보면 이해하기 쉽습니다:) !!) 2) 열에 기입한 ABCBDAB 문자열 중에서 첫 번째 문자 A를 시작으로 행에 기입한 문자열 BDCABA와 하나씩 비교해 나아간다. 비교하여 값을 채우는 방법 - 비교하며 값을 채우는 방식은 2가지가 있다. 먼저, 같은 문자일 경우에는 값을 + 해준다. 현재 위치에서 대각선 왼쪽 위의 값(행과 열 한..

1. 풀이 힌트 - 백준 11053 - 가장 긴 증가하는 부분 수열과 비슷한 문제이다. 부분 수열을 고려 할 때, 증가하는 값과 이어지는 감소하는 값을 고려한 바이토닉 수열의 길이를 구해야 한다. 따라서 증가에서 감소로 가는 부분에서, 증가할 때 이어지던 수열의 길이를 감소할 때 이어서 카운트 해주어야 한다 2. 풀이 과정 - 기본적으로 이전에 작성한 '가장 긴 증가하는 부분 수열의 풀이'를 기준으로 설명하겠다. 1) 밑의 표와 같이 증가하는 부분 수열의 크기만을 기록한 기존의 dp 배열을 2차원으로 확장하여 저장된 값, 증가하는 부분의 수열의 크기, 감소하는 수열의 크기(+ 바이토닉 구간)을 저장하는 새로운 배열을 선언해야 한다 표1) 증가하는 부분수열만 고려한 배열선언 arr (저장된 값) 10 20..