티스토리 뷰
Algorithm/[Java+Python+JavaScript]BackJoon
[Java+Python]12015번, 가장 긴 증가하는 부분 수열 2
Vagabund.Gni 2023. 7. 2. 13:32728x90
반응형
목차
이진 탐색
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에
가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 $A_i$가 주어진다. ($1 ≤ A_i ≤ 1,000,000$)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
풀이
전에 동적계획법으로 푼 적이 있는 LIS(Longest Incresing Subsequence) 문제이다.
솔직하게 말하자면 동적계획법으로 풀었던 것도 가물가물한데.. 이 문제를 이진 탐색으로 어떻게 풀어야 하나
방법 자체가 떠오르지 않아 시간을 꽤 사용했다.
그러다 여전히 잘 모르겠어서 여기저기 검색 해보고, 다른 사람의 풀이를 보고 그제야 이해를 했는데,
이 문제를 이진 탐색으로 푸는 핵심 아이디어는
배열의 각 요소를 순회하며 해당 요소가 LIS의 마지막 원소보다 크면 추가하고,
그렇지 않다면 LIS에서 해당 요소보다 큰 요소 중 가장 작은 것을 빼고 해당 요소를 넣어주는 것이다.
이 과정, 즉 주어진 요소의 위치를 찾는데 이진 탐색을 사용하면 된다!
구체적인 알고리즘은 아래와 같다.
- 입력받은 요소를 수열의 크기 n과 배열 numbers에 넣어 초기화해 준다.
- 답을 저장할 배열 lis와 lis의 길이를 저장할 length를 빈 배열과 0으로 초기화해 준다.
- numbers의 각 요소를 순회하며 이진 탐색을 한다. 그 과정은 아래와 같다.
- left = 0, right = length로 초기화한다.
이 조건 덕분에 처음 숫자는 일단 lis에 들어가고 시작한다. - left가 right보다 작은 경우에 한해 다음의 과정을 반복한다.
- mid = (left + right) / 2로 설정한다.
- lis[mid]가 해당 순서의 numbers[i]보다 작다면 left = mid + 1로, 그렇지 않다면 right = mid로 갱신한다.
- 이런 식으로 해당 숫자보다 크거나 같은 수 중 가장 작은 수의 위치를 찾는다.
- lis[left] = numbers[i]로 갱신해 주고, 삽입된 위치가 현재 길이와 같다면 길이를 1 늘려준다.
- left = 0, right = length로 초기화한다.
- n까지 모두 순회하고 나면 lis는 완성되고 length에는 해당 배열의 크기가 담기므로, 출력해 준다.
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Prob12015 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] numbers =
Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
int[] lis = new int[n];
int length = 0;
for (int i = 0; i < n; i++) {
int left = 0;
int right = length;
while (left < right) {
int mid = (left + right) / 2;
if (lis[mid] < numbers[i]) {
left = mid + 1;
} else {
right = mid;
}
}
lis[left] = numbers[i];
if (left == length) {
length++;
}
}
System.out.println(length);
}
}
Python
import sys
n = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().rstrip().split(' ')))
lis = [0] * n
result = 0
for i in range(n):
left = 0
right = result
while left < right:
mid = (left + right) // 2
if lis[mid] < numbers[i]:
left = mid + 1
else:
right = mid
lis[left] = numbers[i]
if left == result:
result += 1
print(result)
Performance
반응형
'Algorithm > [Java+Python+JavaScript]BackJoon' 카테고리의 다른 글
[Java+Python]11286번, 절댓값 힙, Comparator (0) | 2023.07.04 |
---|---|
[JavaScript]3052번, 나머지, 배열에서 중복 제거, Set (0) | 2023.07.04 |
[JavaScript]5597번, 과제 안 내신 분..?, 배열 다루기 (0) | 2023.07.03 |
[JavaScript]10813번, 공 바꾸기, 배열 초기화, 요소 위치 바꾸기 (0) | 2023.07.01 |
[JavaScript]10810번, 공 넣기, 배열 선언 및 초기화, process.stdout.write() (0) | 2023.06.30 |
[Java+Python]2805번, K번째 수 (0) | 2023.06.29 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 동적계획법
- 기술면접
- 중남미
- 세모
- 여행
- 칼이사
- 파이썬
- a6000
- 맛집
- Backjoon
- spring
- 백준
- 면접 준비
- 유럽
- RX100M5
- 알고리즘
- 유럽여행
- 야경
- BOJ
- java
- 남미
- 세계여행
- 스트림
- 지지
- 스프링
- 자바
- Algorithm
- Python
- 세계일주
- 리스트
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함