1. 문제 2. 접근 방법 https://kbw1101.tistory.com/27 [백준/10816] 숫자 카드 2 (이분 탐색) 1. 문제 2. 접근 방법 이분 탐색 알고리즘으로 접근하되, 찾고자 하는 숫자가 시작하는 지점, 끝나는 지점을 찾아야 한다. 즉, 변형된 이분 탐색 알고리즘이라고 생각하면 된다. 찾고자 하는 숫자 kbw1101.tistory.com 위의 문제와 비슷하게, 이분 탐색을 응용한 알고리즘인 Lower Bound를 이용하여 푸는 문제이다. 여기에서 Lower Bound 의 의미는 다음과 같다. "찾고자 하는 수 이상의 값이 처음으로 등장하는 위치" 그렇다면 문제를 푸는 소개하겠다. 우선 LIS을 담을 배열을 만들고, 가장 첫 번째 원소의 값은 입력 배열의 첫 번째 원소와 동일하게 설..

1. 문제 2. 문제 풀이 다이나믹 프로그래밍(DP)의 대표적인 유형 중 하나인 LIS 문제이다. 현재의 상태를 지속적으로 저장시켜서 문제를 푸는 DP의 특성을 이용하여 문제에 접근한다. 나의 경우에는 다음과 같은 방법을 고안했다. 각 값들에 대해서, 그 값까지 만들어지는 LIS를 지속적으로 저장시켜 나간다. 이 때, 현재의 LIS를 구하는 방법은 다음과 같다. '자신보다 작은 이전의 Value들에 대해서, 그때까지의 LIS가 가장 큰 값에 1을 더한다.' 즉, 각 LIS 값은 다음과 같은 조건으로 구한다. (1) 현재 LIS 값보다 이전의 값들에 대해서 (2) 현재 자신의 Value보다 작은 값들에 대해서 (3) LIS 값이 가장 큰 값을 구한 후, 그 값에 1을 더한 값으로 구한다. (4) 만약 조건..