반응형

https://www.acmicpc.net/problem/3745

 

3745번: 오름세

입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. lower_bound를 활용하여 LIS의 길이를 구합니다.

 

2. LIS.size()를 출력합니다.

 

3. n을 입력받는 scanf의 반환값이 1이 아닐 때 break로 나와줍니다.

 

[ 소스코드 ]

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
32
33
34
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main()
{
    while (1) {
        int n;
        vector<int> LIS;
        if (scanf("%d"&n) != 1) {
            break;
        }
        
        int num;
        scanf("%d"&num);
 
        LIS.push_back(num);
 
        for (int i = 1; i < n; i++) {
            scanf("%d"&num);
            if (LIS[LIS.size() - 1< num) {
                LIS.push_back(num);
            }
            else {
                auto idx = lower_bound(LIS.begin(), LIS.end(), num);
                *idx = num;
            }
        }
 
        printf("%d\n", LIS.size());
    }
}
cs
반응형
반응형

https://www.acmicpc.net/problem/12738

 

12738번: 가장 긴 증가하는 부분 수열 3

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. lower_bound를 활용하여 LIS의 길이를 구합니다.

 

2. LIS.size()를 출력합니다.

 

[ 소스코드 ]

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
32
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
vector<int> LIS;
 
int main()
{
    scanf("%d"&N);
 
    int n;
 
    scanf("%d"&n);
 
    LIS.push_back(n);
 
    for (int i = 1; i < N; i++) {
        scanf("%d"&n);
        if (LIS[LIS.size() - 1< n) {
            LIS.push_back(n);
        }
        else {
            auto idx = lower_bound(LIS.begin(), LIS.end(), n);
            *idx = n;
        }
    }
 
    printf("%d", LIS.size());
}
cs
반응형
반응형

https://www.acmicpc.net/problem/1818

 

1818번: 책정리

동혁이는 캠프가 끝나고 집에 가서 책꽂이 정리를 하고 있었다. 책들은 한 줄로 길게 꽂히 있었다. 동혁이의 책은 1번부터 N번까지 숫자로 표현되고  현재 뒤죽박죽 되어있는 순서를 왼쪽부터

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. lower_bound를 활용하여 LIS의 길이를 구합니다.

 

2. N - LIS.size()를 출력합니다.

 

[ 소스코드 ]

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
32
33
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N;
vector<int> LIS;
 
int main()
{
    scanf("%d"&N);
 
    int num;
 
    scanf("%d"&num);
 
    LIS.push_back(num);
 
    for (int i = 1; i < N; i++) {
        scanf("%d"&num);
 
        if (LIS[LIS.size() - 1< num) {
            LIS.push_back(num);
        }
        else {
            auto idx = lower_bound(LIS.begin(), LIS.end(), num);
            *idx = num;
        }
    }
 
    printf("%d", N - LIS.size());
}
cs
반응형
반응형

https://www.acmicpc.net/problem/12014

 

12014번: 주식

입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. lower_bound를 활용하여 LIS의 길이를 구합니다.

 

2. LIS의 길이가 K보다 크거나 같다면 1, 아니라면 0을 출력합니다.

 

[ 소스코드 ]

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
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main()
{
    int T;
    scanf("%d"&T);
 
    for (int t = 1; t <= T; t++) {
        int N, K;
        int num;
        vector<int> LIS;
 
        scanf("%d %d"&N, &K);
 
        scanf("%d"&num);
 
        LIS.push_back(num);
 
        for (int i = 1; i < N; i++) {
            scanf("%d"&num);
            if (LIS[LIS.size() - 1< num) {
                LIS.push_back(num);
            }
            else {
                auto idx = lower_bound(LIS.begin(), LIS.end(), num);
                *idx = num;
            }
        }
 
        printf("Case #%d\n", t);
 
        if (LIS.size() >= K) {
            printf("1\n");
        }
        else {
            printf("0\n");
        }
    }
}
cs
반응형
반응형

https://www.acmicpc.net/problem/1365

 

1365번: 꼬인 전깃줄

첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. lower_bound를 활용하여 LIS의 길이를 구합니다.

 

2. N - LIS.size()를 출력합니다.

 

[ 소스코드 ]

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int arr[100000];
vector<int> LIS;
 
//int lower_bound(vector<int> vect, int num)
//{
//    int lo = -1;
//    int hi = vect.size() - 1;
//
//    while (lo + 1 < hi) {
//        int mid = (lo + hi) / 2;
//        if (vect[mid] < num) {
//            lo = mid;
//        }
//        else {
//            hi = mid;
//        }
//    }
//
//    return hi;
//}
 
int main()
{
    scanf("%d"&N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d"&arr[i]);
    }
 
    LIS.push_back(arr[0]);
 
    for (int i = 1; i < N; i++) {
        if (LIS[LIS.size() - 1< arr[i]) {
            LIS.push_back(arr[i]);
        }
        else {
            auto idx = lower_bound(LIS.begin(), LIS.end(), arr[i]);
            *idx = arr[i];
        }
    }
 
    printf("%d", N - LIS.size());
}
cs
반응형

'백준' 카테고리의 다른 글

[ 백준 ] 6593번 - 상범 빌딩 (C++)  (0) 2022.12.18
[ 백준 ] 12014번 - 주식 (C++)  (0) 2022.12.17
[ 백준 ] 16397번 - 탈출 (C++)  (0) 2022.12.15
[ 백준 ] 2812번 - 크게 만들기 (C++)  (0) 2022.12.14
[ 백준 ] 9019번 - DSLR (C++)  (0) 2022.12.13
반응형

https://www.acmicpc.net/problem/2568

 

2568번: 전깃줄 - 2

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결

www.acmicpc.net

 

 

[ 문제풀이 ]

 

https://rudalsd.tistory.com/35?category=1064612 

 

[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,00..

rudalsd.tistory.com

 

위의 문제와 답을 구하는 과정은 똑같지만 결과를 출력하는 방법이 조금 달랐습니다. 이번 문제는 LIS에 포함되지 않는 수의 개수와 포함되지 않는 수들을 오름차순으로 출력하는 문제였습니다.

 

출력 전까지는 위의 문제와 똑같은 방법으로 문제를 풀어나가지만 마지막에 원하는 index가 아닐 때 ans에 숫자를 push 해줍니다.

 

[ 소스 코드 ]

 

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
 
using namespace std;
 
int N;
map<intint> A;        //전깃줄이 연결된 번호
map<intint> idx;        //LIS에서의 index를 저장할 map
vector<int> LIS;
vector<int> ans;
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d"&a, &b);
 
        A[a] = b;
    }
 
    for (auto it = A.begin(); it != A.end(); it++) {
        if (LIS.size() == 0) {
            LIS.push_back(it->second);
            idx[it->first] = 1;
        }
        else {
            if (*LIS.rbegin() < it->second) {
                LIS.push_back(it->second);
                idx[it->first] = LIS.size();
            }
            else {
                int a = lower_bound(LIS.begin(), LIS.end(), it->second) - LIS.begin();
                LIS[a] = it->second;
                idx[it->first] = a + 1;
            }
        }
    }
 
    int cnt = LIS.size();
 
    for (auto it = idx.rbegin(); it != idx.rend(); it++) {
        if (it->second == cnt) {        //뒤에서부터 LIS index를 하나씩 줄여가면서
            cnt--;
        }
        else {                    //원했던 index와 다르다면 ans에 push
            ans.push_back(it->first);
        }
    }
 
    printf("%d\n", ans.size());        //없애야하는 전깃줄의 개수 출력
 
    for (int i = ans.size() - 1; i >= 0; i--) {
        printf("%d\n", ans[i]);        //뒤에서부터 ans에 저장된 전깃줄 출력
    }
}
cs
반응형

+ Recent posts