DynamicProgramming

[99클럽 코테 스터디 32일차 TIL] 가장 긴 바이토닉 부분 수열 - 백준 11054

오늘은 조금 어려웠다. https://www.acmicpc.net/problem/11054수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.[입력]첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1..

[99클럽 코테 스터디 31일차 TIL] 줄세우기 - 백준 2631

LIS 변형 문제이다. https://www.acmicpc.net/problem/2631문제 내용KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다.선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다.선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다.이동 도중에 보니 아이들의 번호순서가 바뀌었다.그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다.그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.3 7 5 2 6 1 4아이들을 순서대로 줄을 세우기 위해, 먼저 4..

[Algotithm] Kadane’s Algorithm

오늘은 Kadane’s Algorithm에 대해 공부해봅시다.Kadane’s Algorithm은 Maximum Sum Subarray Problem(최대 부분합 문제)을 해결하는 기법으로 유명하며,Dynamic Programming(DP)의 여러 기법 중 하나입니다.또한 배열의 요소가 정수 범위라고 가정합니다.핵심배열을 순차적으로 순회하면서, 현재까지의 부분합과 최대 부분합을 유지하는 것이 핵심입니다.처음에는 의미를 한 번에 이해하지 못했는데요.아래 그림을 봅시다.위 그림은 [2, 3, -1, -20, 5, 10]의 최대 부분합을 구하는 과정을 시각화한 그림입니다.x축은 Index를, y축은 요소들의 합을 나타냅니다. 배열의 길이만큼의 그래프가 그려집니다. 그래프를 좀 더 자세히 그려봅시다.두 개의 그래..

[Algorithm] Dynamic Programming(DP; 동적계획법)

오늘은 알고리즘 기법 중 Dynamic Programming에 대해 알아보도록 하겠습니다. 동적 프로그래밍, 다이나믹 프로그래밍, DP, 동적 계획법 등 다양한 이름으로 불립니다.알고리즘의 핵심은 문제를 작은 하위 문제들로 나누고 하위 문제들의 값을 캐싱하고 활용하여 큰 문제를 해결한다는 점입니다. 접근법DP는 두 가지 접근법이 존재합니다.1. 탑다운(Top-Down) 방식: 재귀와 캐싱2. 바텀업(Bottom-Up) 방식: 반복문을 통한 DP DP의 활용 예제로는 피보나치(Fibonacci) 함수 구현이 있습니다.탑다운(Top-Down) 방식var cache = [Int: Int]()func fibonacci(_ n: Int) -> Int { if let result = cache[n] { ret..