'알고리즘' 카테고리의 글 목록

[알고리즘] LIS

LIS는 대표적으로 두 가지 방법을 통해 풀 수 있다. 1️⃣ N이 크지 않을 때 (N^2의 시간복잡도가 허용될 때) DP[i] -> 주어진 배열의 i번째 인덱스의 수를 포함했을 때 가장 긴 수열의 크기로, 이는 이중 반복문을 사용한다. 크기 뿐만 아니라 수열을 구해야한다면 DP 역추적을 통해 구할 수 있다. 2️⃣ N이 클 때 (NlogN의 시간복잡도까지 허용될 때)이분탐색을 사용한다. 주어진 배열을 순회하면서 아래의 경우에 따라 DP의 요소를 추가 또는 변경한다. 수열을 구해야 할 경우, 주어진 배열의 각 요소가 DP 리스트에 추가 또는 변경된 인덱스를 저장하는 배열을 추가적으로 관리한다. 그 후 해당 배열의 마지막 요소부터 탐색하면서 역추적을 통해 수열을 추출한다. 1. DP의 마지막 요소보다 타겟..

알고리즘 2024.07.01

📑 로그

알고리즘 1

티스토리툴바