일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
- 5월
- 백준
- 코딩 테스트
- 2022년
- 자료 구조
- 6월
- C/C++
- 2025년
- 유니티
- 2월
- 게임 엔진 공부
- 프로그래머스
- todolist
- 입문
- c++
- 2023년
- 코딩 기초 트레이닝
- 1월
- 다이나믹 프로그래밍
- 7월
- 수학
- 기초
- 개인 프로젝트
- 2024년
- 개인 프로젝트 - 런앤건
- 4월
- 유니티 심화과정
- 3월
- 단계별로 풀어보기
- 골드메탈
- Today
- Total
기록 보관소
[Baekjoon/백준] 12015번: 가장 긴 증가하는 부분 수열 2(C/C++) 본문
단계별로 풀어보기 21단계(이분 탐색) 7번 문제
https://www.acmicpc.net/step/29
이분 탐색 단계
흔히 parametric search라고도 부르는, 이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 테크닉을 배우는 문제
www.acmicpc.net
백준 12015번: 가장 긴 증가하는 부분 수열 2
https://www.acmicpc.net/problem/12015
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
문제 설명
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력과 출력
입력: 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
출력: 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

접근 방법
이번 문제는 수열 A의 크기 N을 입력받고 수열 A 숫자들을 입력받아 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제다.
이미 지난 번에 풀어봤던 가장 긴 증가하는 부분 수열 문제에서 수열 크기 N의 범위가 1,000에서 1,000,000으로 늘어났다. 그래서 이전 문제를 풀던것 처럼 이중 반복문을 이용해 값을 비교해 수열 크기를 출력하는 것은 시간초과가 발생할 것이다.
따라서 이분 탐색으로 문제를 풀어야한다. 일단 문제 풀이는 입력 받은 값을 수열 마지막 값과 비교해 더 크다면 수열에 넣고, 크지 않다면 그 값보다 더 큰 값이 먼저 나타나는 위치를 찾아서 넣는 방식으로 하면 된다. 이렇게하면 그 값보다 더 작은 값들이 나오면 그 값들로 길이를 더 늘릴 수 있고, 혹은 그 숫자 하나만 바뀌더라도 결국 전체 길이 자체는 같은 값이므로 문제 해결을 할 수있다. 이를 위해서 lower_bound를 이용하여 문제를 풀면 된다.
앞 설명이 조금 까다로워서 예제를 통해서 문제를 설명한다면 아래와 같다.
9
10 11 12 13 19 14 15 20 21 입력시
10 11 12 13 19 까지는 문제가 없다. 다만 14 15를 넣는다면 더 긴 길이의 증가하는 부분 수열을 찾을 수 있다.
따라서 19보다 더 작은 값인 14를 19위치에서 바꿔주면, 15도 수열에 추가되어 가장 긴 증가하는 부분 수열을 만들 수 있다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 1000000
vector<int> v;
int main(int argc, char * argv[]) {
int N, A, index;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A;
if (v.empty() || v.back() < A)
v.push_back(A);
else {
index = lower_bound(v.begin(), v.end(), A) - v.begin();
v[index] = A;
}
}
cout << v.size() << endl;
return 0;
}
결과

'코딩 테스트 > 백준' 카테고리의 다른 글
[Baekjoon/백준] 1927번: 최소 힙(C/C++) (0) | 2022.06.01 |
---|---|
[Baekjoon/백준] 11279번: 최대 힙(C/C++) (0) | 2022.05.29 |
[Baekjoon/백준] 1300번: K번째 수(C/C++) (0) | 2022.05.22 |
[Baekjoon/백준] 2110번: 공유기 설치(C/C++) (0) | 2022.05.21 |
[Baekjoon/백준] 2805번: 나무 자르기(C/C++) (0) | 2022.05.20 |