[최장 증가 부분 수열(LIS)]
최장 증가 부분 수열(Longest increasing subsequence) 알고리즘은 주어진 수열에서 제일 길게(=최장) 증가하는 부분적인 수열을 의미합니다.
문제를 해결할 수 있는 방법은 다양하지만, 보통 DP(동적 프로그래밍)와 Binary Search(이분 탐색)를 사용합니다.
DP는 이중 for문을 사용하므로 시간복잡도가 O(n^2)이고 Binary Search는 O(nlogn) 시간복잡도를 가집니다. 그렇기 때문에 DP로 구현하지 않고 Binary Search로 구현하는 감각을 익혀야 합니다!
최장 증가 부분 수열 알고리즘으로 문제를 풀 수 있다는 가정 하에, Binary Search로 구현하면 n의 범위에 상관없이 해결할 수 있기 때문입니다.
[DP를 활용한 접근]
파이썬을 사용한다면 LIS 알고리즘을 쉽게 구현할 수 있습니다. 만약, C++이나 swift 언어를 사용할 경우에는 binary search를 직접 구현했어야 했는데 말이죠... 너무 좋은 언어인 거 같습니다ㅋㅋㅋ
import sys, bisect
n = int(sys.stdin.readline().rstrip())
arr = list(map(int,sys.stdin.readline().rstrip().split()))
dp = [arr[0]]
for i in range(n):
if(arr[i] > dp[-1]):
dp.append(arr[i])
else:
idx = bisect.bisect_left(dp,arr[i])
dp[idx] = arr[i]
print(len(dp))📌 배열의 길이를 입력받는다.
📌 배열을 입력받는다.
📌 각 배열의 요소를 순회하면서 dp 배열에 저장된 마지막 원소보다 크다면 dp에 추가한다.
📌 크지 않다면 해당 요소가 들어갈 위치를 binary serach로 찾아서 업데이트한다.
알고리즘 문제를 푸는데 아래와 같은 케이스에서 LIS 알고리즘을 생각해낼 수 있으면 됩니다.
첫 번째!! 정해진 기간동안 부분적으로 증가하거나 감소하는 길이를 찾으라는 개념이 있을 경우
두 번째!! 아래 그림과 같이 무언가 꼬인 선들이 존재하는 경우
[문제를 통한 감각 익히기]
알고리즘을 공부하면 그 알고리즘에 대한 문제를 집중적으로 푸는 것이 좋다고 생각해서 풀어보시는 걸 추천드립니다 ✨
https://www.acmicpc.net/problem/3745
3745번: 오름세
입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다.
www.acmicpc.net
https://www.acmicpc.net/problem/1365
1365번: 꼬인 전깃줄
첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가
www.acmicpc.net
https://www.acmicpc.net/problem/2352
2352번: 반도체 설계
첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주
www.acmicpc.net
https://www.acmicpc.net/problem/1818
1818번: 책정리
동혁이는 캠프가 끝나고 집에 가서 책꽂이 정리를 하고 있었다. 책들은 한 줄로 길게 꽂히 있었다. 동혁이의 책은 1번부터 N번까지 숫자로 표현되고 현재 뒤죽박죽 되어있는 순서를 왼쪽부터
www.acmicpc.net
https://www.acmicpc.net/problem/18353
18353번: 병사 배치하기
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
https://www.acmicpc.net/problem/12014
12014번: 주식
입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두
www.acmicpc.net
https://www.acmicpc.net/problem/3066
3066번: 브리징 시그널
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에 포트의 개수 N(1 ≤ N ≤ 40000)이 주어지고, 두 번째 줄부터는 왼쪽 블록의 포트와 연결되어야 하는 오른쪽
www.acmicpc.net
[최장 증가 부분 수열(LIS)]
최장 증가 부분 수열(Longest increasing subsequence) 알고리즘은 주어진 수열에서 제일 길게(=최장) 증가하는 부분적인 수열을 의미합니다.
문제를 해결할 수 있는 방법은 다양하지만, 보통 DP(동적 프로그래밍)와 Binary Search(이분 탐색)를 사용합니다.
DP는 이중 for문을 사용하므로 시간복잡도가 O(n^2)이고 Binary Search는 O(nlogn) 시간복잡도를 가집니다. 그렇기 때문에 DP로 구현하지 않고 Binary Search로 구현하는 감각을 익혀야 합니다!
최장 증가 부분 수열 알고리즘으로 문제를 풀 수 있다는 가정 하에, Binary Search로 구현하면 n의 범위에 상관없이 해결할 수 있기 때문입니다.
[DP를 활용한 접근]
파이썬을 사용한다면 LIS 알고리즘을 쉽게 구현할 수 있습니다. 만약, C++이나 swift 언어를 사용할 경우에는 binary search를 직접 구현했어야 했는데 말이죠... 너무 좋은 언어인 거 같습니다ㅋㅋㅋ
import sys, bisect
n = int(sys.stdin.readline().rstrip())
arr = list(map(int,sys.stdin.readline().rstrip().split()))
dp = [arr[0]]
for i in range(n):
if(arr[i] > dp[-1]):
dp.append(arr[i])
else:
idx = bisect.bisect_left(dp,arr[i])
dp[idx] = arr[i]
print(len(dp))📌 배열의 길이를 입력받는다.
📌 배열을 입력받는다.
📌 각 배열의 요소를 순회하면서 dp 배열에 저장된 마지막 원소보다 크다면 dp에 추가한다.
📌 크지 않다면 해당 요소가 들어갈 위치를 binary serach로 찾아서 업데이트한다.
알고리즘 문제를 푸는데 아래와 같은 케이스에서 LIS 알고리즘을 생각해낼 수 있으면 됩니다.
첫 번째!! 정해진 기간동안 부분적으로 증가하거나 감소하는 길이를 찾으라는 개념이 있을 경우
두 번째!! 아래 그림과 같이 무언가 꼬인 선들이 존재하는 경우
[문제를 통한 감각 익히기]
알고리즘을 공부하면 그 알고리즘에 대한 문제를 집중적으로 푸는 것이 좋다고 생각해서 풀어보시는 걸 추천드립니다 ✨
https://www.acmicpc.net/problem/3745
3745번: 오름세
입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다.
www.acmicpc.net
https://www.acmicpc.net/problem/1365
1365번: 꼬인 전깃줄
첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가
www.acmicpc.net
https://www.acmicpc.net/problem/2352
2352번: 반도체 설계
첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주
www.acmicpc.net
https://www.acmicpc.net/problem/1818
1818번: 책정리
동혁이는 캠프가 끝나고 집에 가서 책꽂이 정리를 하고 있었다. 책들은 한 줄로 길게 꽂히 있었다. 동혁이의 책은 1번부터 N번까지 숫자로 표현되고 현재 뒤죽박죽 되어있는 순서를 왼쪽부터
www.acmicpc.net
https://www.acmicpc.net/problem/18353
18353번: 병사 배치하기
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
https://www.acmicpc.net/problem/12014
12014번: 주식
입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두
www.acmicpc.net
https://www.acmicpc.net/problem/3066
3066번: 브리징 시그널
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에 포트의 개수 N(1 ≤ N ≤ 40000)이 주어지고, 두 번째 줄부터는 왼쪽 블록의 포트와 연결되어야 하는 오른쪽
www.acmicpc.net
