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


나무위키 최장증가부분수열


사람들이 각각 번호를 가지고 있고 그 번호 순서에 맞춰서 일렬로 정렬하려고 한다. 이때 움직인 사람들의 총 수를 최소로 하고 싶다면 어떻게 해야 하는가? (단, 초기에 사람들은 무작위로 일렬로 섞여 있고, 'A씨, 맨 뒤 / 맨 앞으로 가세요', 'A씨, B씨와 C씨 사이로 가세요' 꼴의 명령으로 사람들을 이동시킨다고 하자.)


이 문제는 전형적인 LIS 응용 문제이다. 움직인 사람들의 총 수가 최소가 된다는 말은 움직이지 않은 사람들의 수가 최대가 된다는 것이다.

사람들의 번호들의 수열에서 이미 오름차순으로 정리된 쌍이 있다면 그들은 움직이지 않아도 된다. 따라서 그 수열의 LIS를 이루는 사람들은 움직이지 않고, 나머지 사람들이 그들 사이로 적절히 배열된다면 정렬할 수 있다. 


정렬 -> LIS -> 전깃줄 개수 - 수열 크기


난최고야!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


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
#include <iostream>
#include <algorithm>
 
struct wire
{
    int A;
    int B;
};
 
wire arr[101];
int dp[101];
 
bool cmp(wire& first, wire& second)
{
    if (first.A < second.A)
        return true;
    else
        return false;
}
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> arr[i].A >> arr[i].B;
    }
    std::sort(arr, arr + N, cmp);
    
    int back = 0;
    for (int i = 0; i < N; ++i)
    {
        int it = 0;
        for( ;dp[it] != 0; ++it)
        {
            if (dp[it] > arr[i].B)
            {
                dp[it] = arr[i].B;
                break;
            }
        }
        dp[it] = arr[i].B;
        back = back > it ? back : it;
    }
    std::cout << N - (back + 1);
    return 0;
}
cs


끼에에에에에에에에엒!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

저작자표시

'알고리즘' 카테고리의 다른 글

백준 1912: 연속합(DP)  (0) 2019.08.27
백준 9251: LCS(DP)  (0) 2019.08.26
백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22
백준 10844: 쉬운 계단 수(DP)  (0) 2019.08.19

nlogn으로 풀어본다고 개삽질하다가 지쳐서


n2으로 무식하게 오름차순 내림차순 다 계산해서 배열에 때려박은다음


계산된 배열 두개중 합친 값이 가장 큰걸 반환하게 했다.


솔찍히 시간초과 날줄알앗는데 으..응?으응???하니까 정답입니다!!...


아몰라 ㄹ풀었음댓지머


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
#include <iostream>
 
int seq[1010];
int highDp[1010];
int lowerDp[1010];
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> seq[i];
        int m = highDp[0];
        for (int j = 0; j < i; ++j)
            if (seq[i] > seq[j] && highDp[j] > m)
                m = highDp[j];
        highDp[i] = m + 1;
        
    }
 
    for (int i = N; i >= 1; --i)
    {
        int m = 0;
        for (int j = N + 1; j >= i; --j)
            if (seq[i] > seq[j] && lowerDp[j] > m)
                m = lowerDp[j];
        lowerDp[i] = m + 1;
    }
 
    int mx = 0;
    for (int i = 0; i <= N; ++i)
    {
        mx = lowerDp[i] + highDp[i] < mx ? mx : lowerDp[i] + highDp[i];
    }
    std::cout << mx - 1;
    return 0;
}
 
cs


으으 왤캐 깔끔하게 안풀리지?

저작자표시

'알고리즘' 카테고리의 다른 글

백준 9251: LCS(DP)  (0) 2019.08.26
백준 2565: 전깃줄(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22
백준 10844: 쉬운 계단 수(DP)  (0) 2019.08.19
백준 1463: 1로 만들기(DP)  (0) 2019.08.16

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


어제의 알고리즘 대실패는 나로 하여금 나 자신이 빡통이라는걸 절절히 인정하는 그러한 계기가 되었다.


그래서 오늘 문제는 바로 갓무위키를 찾아보았다.


부분수열이 뭔지 까먹었기도 하고ㅎ


꺼라위키 정의


어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다.

이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.


예를 들어 다음 수열이 주어졌다고 하자.


3 5 7 9 2 1 4 8


위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다.


3 7 9 1 4 8 (5, 2 제거)

7 9 1 8 (3, 5, 2, 4 제거)

3 5 7 8 (9, 2, 1, 4 제거)

1 4 8 (3, 5, 7, 9, 2 제거)


이들 중 세번째, 네번째 수열은 오름차순으로 정렬되어 있다. 이들을 '증가 부분 수열'이라고 한다.


그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다.

부분수열 3 5 7 8은 LIS이다.


한 수열에서 여러 개의 LIS가 나올 수도 있다. 예를 들어 수열


5 1 6 2 7 3 8


에서 부분수열


1 2 3 8

5 6 7 8


은 모두 길이가 4인 LIS이다. 


부분수열은 간단히 말해서 임의의 수열 A에서 A의 원소를 포함하는 또다른 수열 B라고 보면 된다.


여기서 수열이라고 해서 좀 혼란스러웠는데, 수열은 보통 일정한 규칙이 존재하는 수의 집합이라고 봐야 하지만 여기선 없다고 봐도 상관 없다.


즉 걍 숫자 집합인데, 부분수열은 그냥 부분집합이다. 대신 숫자의 순서가 보장되어있는 집합이지


꺼라위키도 설명을 그지같이 했다. 몇 개의 숫자를 제거한다니, 제거하는 규칙이 있어야하는것마냥 설명해놓곤


걍 수열 A의 숫자 몇개 추려서 다른 수열 B 만들면 그게 A의 부분수열이다.(순서는 반드시 보장되어야 한다. 자세한 예시는 꺼라위키 정의 참고)


암튼, 그런 부분수열중에 오름차순으로 되어 있는 수열 x중 사이즈가 가장 큰 수열의 사이즈를 반환하는 문제다.


꺼라에서는 n제곱으로 푸는 방법과, n로그n으로 푸는 방법 둘 다 설명해놨는데 n제곱으로 풀어봤더니 통과된다.


알고리즘 푸는 방법은 혼자서 생각 못할 것 같아 어쩔 수 없이 봤지만...그래도 코드 구현은 직접 했다...


나도 똑똑해졌으면 좋겠구만


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
#include <iostream>
#include <algorithm>
 
int seq[1010];
int dp[1010];
 
bool cmp(int first, int second)
{
    if (first > second)
        return true;
    else
        return false;
}
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> seq[i];
        int m = dp[0];
        for (int j = 0; j < i; ++j)
            if (seq[i] > seq[j] && dp[j] > m)
                m = dp[j];
        dp[i] = m + 1;
    }
    std::sort(dp, dp + N + 1, cmp);
    std::cout << dp[0];
    return 0;
}
cs


여기서 sort를 사용했는데, 사실 max 변수 하나 만들어서 dp중 가장 큰 수를 max에 담아 출력하기만 하면 더 빠를 것이다


나는 그냥 좀 더 깔끔해보이려고 이렇게 뺐다. 문제는 없이 통과되던데


nlogn으로 푸는 방법


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>
 
int seq[1010];
int dp[1010];
 
int main()
{
    int N;
    std::cin >> N;
    int back = 0;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> seq[i];
        int it = 1;
        while (dp[it] != 0)
        {
            if (dp[it] >= seq[i])
            {
                dp[it] = seq[i];
                break;
            }
            ++it;
        }
        if (dp[it] == 0)
        {
            dp[it] = seq[i];
            back = it;
        }
    }
    std::cout << back;
    return 0;
}
cs


설명은 귀찮아서 생략


일케 하면 빠른대신에 모든 데이터들의 증가부분수열을 저장할수는 없다.

저작자표시

'알고리즘' 카테고리의 다른 글

백준 2565: 전깃줄(DP)  (0) 2019.08.23
백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 10844: 쉬운 계단 수(DP)  (0) 2019.08.19
백준 1463: 1로 만들기(DP)  (0) 2019.08.16
백준 2579: 계단 오르기(DP)  (0) 2019.08.14
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
#include <iostream>
 
unsigned int dp[101][10];
 
int main()
{
    int N = 0;
    std::cin >> N;
    for (int i = 1; i <= 9; ++i)
        dp[1][i] = 1;
    for (int i = 2; i <= N; ++i)
        for (int j = 0; j < 10; ++j)
        {
            if (j == 0)
                dp[i][j] = dp[i - 1][j + 1];
            else if (j == 9)
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
        }
    unsigned long long ans = 0;
    for (int i = 0; i < 10; ++i)
        ans += dp[N][i];
    std::cout << ans % 1000000000;
    return 0;
}
cs


십억을 중간과정에서 나머지연산하면 오버플로는 막겠지만 값이 변하지 않나..


하... 모르겠다...


그냥 전체적으로 조졌다... 왜 일케 하는지는 알겠는데 내가 직접 로직을 세우지도 못했고... 아직도 나머지연산은 이해가 안대고... DP빡고수라고 자화자찬 하자마자 개뚜드려맞았다...

저작자표시

'알고리즘' 카테고리의 다른 글

백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22
백준 1463: 1로 만들기(DP)  (0) 2019.08.16
백준 2579: 계단 오르기(DP)  (0) 2019.08.14
백준 10814: 나이순 정렬 (병합 정렬)  (0) 2019.08.09

특별하게 어렵거나 쉽다기보단... DP 쥐뿔도 모르는 내가 꾸역꾸역 풀어본 문제라서 올려봄


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
#include <iostream>
 
int dp[1000010];
 
int main()
{
    int input, N;
    int cnt = 0;
    std::cin >> input;
    dp[2] = dp[3] = 1;
    N = 4;
    while (N <= input)
    {
        if (N % 3 == 0)
        {
            if (dp[N - 1] >= dp[N / 3])
                dp[N] = dp[N / 3] + 1;
        }
        if (N % 2 == 0)
        {
            if (dp[N - 1] >= dp[N / 2])
            {
                if (dp[N] == 0)
                    dp[N] = dp[N / 2] + 1;
                else if(N % 3 == 0)
                    if(dp[N] > dp[N / 2])
                        dp[N] = dp[N / 2] + 1;
            }
        }
        if(dp[N] >= dp[N - 1] + 1 || dp[N] == 0)
            dp[N] = dp[N - 1] + 1;
        ++N;
    }
    int i = dp[input];
    std::cout << i;
    return 0;
}
cs


이건 겨우겨우 풀어댄 방법


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
int dp[1000010];
 
int main()
{
    int input, N;
    int cnt = 0;
    std::cin >> input;
    dp[2] = dp[3] = 1;
    for (int N = 4; N <= input; ++N)
    {
        dp[N] = dp[N - 1] + 1;
        if (N % 3 == 0)
            dp[N] = dp[N] > dp[N / 3] + 1 ? dp[N / 3] + 1 : dp[N];
        if (N % 2 == 0)
            dp[N] = dp[N] > dp[N / 2] + 1 ? dp[N / 2] + 1 : dp[N];
    }
    std::cout << dp[input];
 
    return 0;
}
cs


이건 훨씬 깔끔한 방법


DP의 핵심은, 반복문을 한큐에 끝낼 수 있는가


인듯.


브루트포스처럼 코드가 이리흐르고 저리흐르면 망한다는 것이다


그러기 위해선 이곳저곳으로 흘러흘러가는 코드보다는


처음부터 끝까지 우직하게 지나가는(저장하는) 방식이 동적배열에 더 맞지 않는가 싶다.



저작자표시

'알고리즘' 카테고리의 다른 글

백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22
백준 10844: 쉬운 계단 수(DP)  (0) 2019.08.19
백준 2579: 계단 오르기(DP)  (0) 2019.08.14
백준 10814: 나이순 정렬 (병합 정렬)  (0) 2019.08.09

계단: 2579


피보나치: 1003


그래서 동적계획법은 대체 머 어케하는건데??했던 지난날보다는 성장했지만


여전히 약간 꼬아놓은 문제는 간단하게 풀어내기 힘들다.


간단하게 풀었던 다른 문제들에 비해

(피보나치 함수는 내가 쉽게 풀었던 것에 비해 정답률이 생각보다 낮아서.. 너무 좋았따...크큭....)


계단문제에서 주춤했다. 사실 똑같이 간단한 문제인데... 정답에 접근하는 방법도 거의 근접했는데


어느 순간 생각이 산으로 가버리고...


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
#define max(a,b)            (((a) > (b)) ? (a) : (b))
 
int dp[301];
int stair[301];
 
int main()
{
    int N = 0;
    std::cin >> N;
    std::cin >> stair[1] >> stair[2];
    dp[1] = stair[1];
    dp[2] = stair[1] + stair[2];
    for (int i = 3; i <= N; ++i)
    {
        std::cin >> stair[i];
        dp[i] = max(dp[i - 2] + stair[i], dp[i - 3] + stair[i - 1] + stair[i]);
    }
    std::cout << dp[N];
    return 0;
}
cs


코드를 짜면서도 '이렇게 풀면 될 것 같은데?' 하자마자


'음 아닌것같은데' (사실 정답이었다)




이건 개망한 접근방법

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
#include <iostream>
 
int dp[301];
 
int main()
{
    int N = 0;
    std::cin >> N;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> dp[i];
    }
    int sum = 0;
    --N;
    int i = 2;
    while(N >= 0)
    {
        sum += dp[N];
        if (i == 2)
        {
            i = dp[N - 1] > dp[N - 2] ? 1 : 2;
        }
        else if (i == 1)
        {
            i = 2;
        }
        N -= i;
    }
    std::cout << sum;
    return 0;
}
cs


개시발


저작자표시

'알고리즘' 카테고리의 다른 글

백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22
백준 10844: 쉬운 계단 수(DP)  (0) 2019.08.19
백준 1463: 1로 만들기(DP)  (0) 2019.08.16
백준 10814: 나이순 정렬 (병합 정렬)  (0) 2019.08.09

폰노이만...


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


병합 정렬은 무한 츠쿠요미 함수를 이용한 정렬 방식이다.


1. 쪼갤 수 있는 만큼 쪼개면서 배열을 쪼갠다.

(실제로 쪼개는건 아니고, 2개의 피봇으로 시작과 끝의 구분을 두었다.)


2. 그러면 배열의 시작과 끝이 같은 곳을 보거나 그럴텐데, 그건 건너뛴다.


3. start와 end가 같은 재귀함수(39 : start < end)는 건너뛰고, start와 end가 1차이나는 재귀는 병합한다.


4. 병합은 그 대진표 형식으로 정렬시킨다. 솔직히 이거 설명만 들으면 아~ 하는데 막상 코드 첨보면 이게 뭔가 싶다.


5. start와 end가 1차이나는 재귀 배열은 서로 정렬이 되어서 합쳐지고, 이제 start와 end가 2차이나는 배열이 남는다.


6. 이제 1:1이 아니라 2:2 태그매치다. 누가 더 숫자가 낮은지 겨뤄서 다시 정렬한다.


7. 4:4... 8:8... 올라가면서 계속 정렬한다.


8. 홀수인 경우? 하나는 겨뤄봄직한 상대가 없어서 부전승을 치지만, 다음 매치에서 결국 정렬당한다.


9. 폰노이만....


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
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <string>
#include <vector>
 
struct member
{
    int age = 0;
    std::string name;
};
 
std::vector<member> tmpVec;
 
void _merge(std::vector<member>& members, int start, int end)
{
    int mid = (start + end) / 2;
    int i = start;
    int j = mid + 1;
    int k = start;
 
    while (i <= mid && j <= end)
    {
        if (members[i].age <= members[j].age)
            tmpVec[k++] = members[i++];
        else
            tmpVec[k++] = members[j++];
    }
 
    int tmp = i > mid ? j : i;
 
    while (k <= end)
        tmpVec[k++] = members[tmp++];
 
    for (int i = start; i < k; ++i)
        members[i] = tmpVec[i];
}
 
void _mergesort(std::vector<member>& members, int start, int end)
{
    if (start < end)
    {
        int m = (start + end) / 2;
        _mergesort(members, start, m);
        _mergesort(members, m + 1, end);
        _merge(members, start, end);
    }
}
 
int main()
{
    std::ios::sync_with_stdio(false);
    std::cout.tie(0);
    std::cin.tie(NULL);
    std::ios_base::sync_with_stdio(false);
    int N;
    std::cin >> N;
    std::vector<member> members;
    members.reserve(N);
    tmpVec.reserve(N);
    member input;
    for(int i = 0; i < N; ++i)
    {
        std::cin >> input.age >> input.name;
        members.push_back(input);
        tmpVec.push_back(input);
    }
    _mergesort(members, 0, N - 1);
    for (auto it : members)
        std::cout << it.age << ' ' << it.name << '\n';
    return 0;
}
cs



자매품.

stable_sort 함수

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 <string>
#include <vector>
#include <algorithm>
 
bool cmp(std::pair<int, std::string> first, std::pair<int, std::string> second)
{
    if (first.first < second.first)
        return true;
    else
        return false;
}
 
int main()
{
    int N;
    std::cin >> N;
 
    std::vector<std::pair<int, std::string>> members;
    members.reserve(N);
 
    std::pair<int, std::string> input;
    for(int i = 0; i < N; ++i)
    {
        std::cin >> input.first >> input.second;
        members.push_back(input);
    }
 
    stable_sort(members.begin(), members.end(), cmp);
 
    for (auto it : members)
        std::cout << it.first << ' ' << it.second << '\n';
    return 0;
}
cs


비교함수만 만들면 되는 간단한 문제이지만 그래서는 공부라고 할 수 없다


암기...암기가 최고야...

저작자표시

'알고리즘' 카테고리의 다른 글

백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22
백준 10844: 쉬운 계단 수(DP)  (0) 2019.08.19
백준 1463: 1로 만들기(DP)  (0) 2019.08.16
백준 2579: 계단 오르기(DP)  (0) 2019.08.14

+ Recent posts

티스토리툴바