티스토리 뷰

PS/Algorithm

[Inflearn] 공주 구하기(Josephus)

Aaron 2020. 4. 27. 17:16
반응형


#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn


#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it


#. Solve

  1. 재미있는 문제네

     8 3 이 입력으로 주어질 때,

     8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 한다.

     왕자는 동그랗게 앉아 있다.

     

     start = 1

     1 2 3 4 5 6 7 8 에서

     3 번 왕자 제외


     start = 4

     1 2 4 5 6 7 8

     6 번 왕자 제외


     start = 7

     1 2 4 5 7 8

     1번 왕자 제외


     start = 2

     2 4 5 7 8

     5번 왕자 제외


     start = 7

     2 4 7 8 

     2번 왕자 제외

    

     start = 4

     4 7 8

     8번 왕자 제외

     

     start = 4

     4 7

     4번 왕자 제외


     마지막으로 7이 남으므로 7번 왕자가 공주를 구하러 가게 된다.


     1 2 3 4 5 6 7 8 에서

     3 6 1 5 2 8 4 7 이라는 결과가 나왔는데 

     

     우선 이 문제는 조세푸스라는 알고리즘으로 해결할 수 있다.

     <wikipedia>

     n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.


     M = 1,

     1 2 3 4 5 6 7 => 2 3 4 5 6 7 1

     M = 2,

     2 3 4 5 6 7 1 => 3 4 5 6 7 1 2

     M = 3

     3 4 5 6 7 1 2 => M 이 3일 때, 맨 앞에 수를 pop() 하여 rst 배열에 push 해준다. rst = [ 3 ]


     M = 1,

     4 5 6 7 1 2 => 5 6 7 1 2 4

     M = 2,

     5 6 7 1 2 4 => 6 7 1 2 4 5

     M = 3,

     6 7 1 2 4 5 => M 이 3일 때, 맨 앞에 수를 pop() 하여 rst 배열에 push 해준다. rst = [ 3, 6 ] 


     M = 1,

     6 7 1 2 4 5 => 7 1 2 4 5 6

     M = 2,

     7 1 2 4 5 6 => 1 2 4 5 6 7

     M = 3,

     1 2 4 5 6 7 => M 이 3일 때, 맨 앞에 수를 pop() 하여 rst 배열에 push 해준다. rst = [ 3, 6, 1 ] 

     ...

     앞 뒤로 연산이 많이 일어나므로 queue 를 잘 활용하면 쉽게 풀어낼 수 있을 것 같다.


#. Code

1. Queue 사용 코드

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 <cstdio>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, k, i, j;
 
    scanf("%d %d", &n, &k);
    queue<int> in, rst;
    for (i = 1; i <= n; i++)
        in.push(i);
 
    for (i = 0; i < n - 1; i++)
    {
        for (j = 0; j < k - 1; j++)
        {
            in.push(in.front());
            in.pop();
        }
 
        rst.push(in.front());
        in.pop();
    }
 
    printf("%d\n", in.front());
        
    return 0;
}
cs

2. 강사님 풀이대로 배열로 문제를 해결하는 방법으로 다시 풀어본 코드

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 <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, k, i, pos = 1, cnt = 0;
 
    scanf("%d %d", &n, &k);
    vector<int> vt(n+1);
 
    while (cnt < n - 1)
    {
        for (i = 1; i <= k; i++)
        {
            if (vt[pos] == 0)
                pos++;
            else
            {
                pos++;
                i--;
            }
 
            if (pos == (n + 1))
                pos = 1;
        }
 
        if (pos == 1)
            vt[n] = 1;
        else
            vt[pos-1] = 1;
 
        cnt++;
    }
 
    for (i = 1; i <= n; i++)
    {
        if (vt[i] == 0)
        {
            printf("%d\n", i);
            break;
        }
    }
 
    return 0;
}
cs

이 코드에서 line 32 는 위험한 코드이다.

pos가 정말 1이었을 경우, vt[pos] 값을 1로 치환해주지 못한다는 것이다.


3. 2번 코드 정리 및 안정화

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 <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, k, i, pos = 0, cnt = 0;
 
    scanf("%d %d", &n, &k);
    vector<int> vt(n+1);
 
    while (cnt < n - 1)
    {
        for (i = 1; i <= k; i++)
        {
            pos++;
 
            if (pos > n)
                pos = 1;
 
            if (vt[pos] == 0)
            {
                if (i == k)
                {
                    vt[pos] = 1;
                    cnt++;
                }
            }
            else
                i--;
        }
    }
 
    for (i = 1; i <= n; i++)
    {
        if (vt[i] == 0)
        {
            printf("%d\n", i);
            break;
        }
    }
 
    return 0;
}
cs


#. Other code

1. while문만 사용

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
#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(){
    int n, k, p=0, i, bp=0, cnt=0;
 
    scanf("%d %d", &n, &k);
    vector<int> prince(n+1);
 
    while(1){
        p++;
 
        if(p>n) 
            p=1;
 
        if(prince[p]==0){
            cnt++;
 
            if(cnt==k){
                prince[p]=1;
                cnt=0;
                bp++;
            }
        }
 
        if(bp==n-1) 
            break;
    }
 
    for(i=1; i<=n; i++){
        if(prince[i]==0){
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}
cs

구현에 정답은 없지만 역시나 강사님의 코드는 Sooo 깰꿈하시당..

무한 루프를 돌려놓은 후 

position 위치 증가, prince[pos] 가 0이라면 cnt 시켜주고,

cnt 가 k 와 같다면 prnce[pos] 를 1로 치환, cnt 초기화, dp++

절차적으로 진행되도록 구현하셨다.

나도 좀 왔다리 갔다리 코딩하지 말고, 기능을 하나씩 만들어나가도록 노력해야겠다...


2. while & for문 사용

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
#include<stdio.h>
#include<vector>
 
using namespace std;
 
int main(){
    int n, k, pos=0, i, cnt=0;
 
    scanf("%d %d", &n, &k);
    vector<int> prince(n+1);
 
    while(1){
        for(i=1; i<=k; i++){
            while(1){
                pos++;
 
                if(pos>n) 
                    pos=1;
 
                if(prince[pos]==0) 
                    break;
            }
        }
 
        prince[pos]=1;
        cnt++;
 
        if(cnt==n-1) 
            break;
    }
 
    for(i=1; i<=n; i++){
        if(prince[i]==0){
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}
 
 
 
cs

내가 다시 짠 코드보다 더 깔끔하다..

나는 for문 안에서 for 문의 증감 변수를 조작하면서 했는데

for문 안에 무한루프와 break 를 사용한 방법이 훨씬 좋은 것 같다. 

더 분발하자!!!


#. Result

  - Input --------------------------------------------------------

8 3

------------------------------------------------------------------


  - Output --------------------------------------------------------

7

------------------------------------------------------------------




반응형
저작자표시

'PS > Algorithm' 카테고리의 다른 글

[Inflearn] 영지(territory) 선택(large) - DP  (0) 2020.04.29
[Inflearn] 영지(territory) 선택(small) : 브루트포스  (0) 2020.04.28
[Algorithm] 이분검색(Binary Search)(c/c++)  (0) 2020.04.26
[Algorithm] 교집합(투포인트 알고리즘) (MS interview source)  (0) 2020.04.26
[Inflearn] Least Recently Used  (0) 2020.04.24
댓글
최근에 올라온 글
최근에 달린 댓글
링크
Total
Today
Yesterday
TAG more