블로그 이미지
Nehoy
경기대학교 / kknock

calendar

 «  » 2025.5
일 월 화 수 목 금 토
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

Notice

Tag

2017. 5. 20. 13:28 프로그래밍

[개인 공부] 하노이 타워

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/* 하노이 타워 [2017-03-28] */
/* 최적화가 필요합니다. */
 
#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
 
#define STACK_SIZE 100
 
template <typename T>
class Stack {
public:
    Stack() {
        memset(elementArr, 0, sizeof(T) * STACK_SIZE);
        m_size = 0;
    }
 
    void push(T elem) {
        if (m_size >= STACK_SIZE) {
            fprintf(stderr, "스택 - 용량이 부족합니다.\n");
            exit(-1);
        }
 
        elementArr[m_size++] = elem;
    }
    T pop() {
        if (m_size <= 0) {
            fprintf(stderr, "스택 - 비어있습니다.\n");
            exit(-1);
        }
 
        return elementArr[--m_size];
    }
 
    T elementAt(size_t index) {
        if (index < 0 || index >= m_size) {
            fprintf(stderr, "스택 - 인덱스가 잘못되었습니다.\n");
            exit(-1);
        }
 
        return elementArr[index];
    }
    T top() {
        return elementAt(m_size - 1);
    }
 
    size_t size() {
        return m_size;
    }
    bool empty() {
        return (m_size <= 0) ? true : false;
    }
 
private:
    T elementArr[STACK_SIZE];
    size_t m_size;
};
 
class Relation {
public:
    Relation() {
    }
    Relation(Stack<int> *self, Stack<int> *target, Stack<int> *other) {
        m_self = self, m_target = target, m_other = other;
    }
 
    Stack<int> *m_self, *m_target, *m_other;
};
 
void render(Relation relation, Stack<int> *aTower, Stack<int> *bTower, Stack<int> *cTower) {
    char selfTower, targetTower;
 
    if (relation.m_self == aTower)        selfTower = 'a';
    else if (relation.m_self == bTower)    selfTower = 'b';
    else                                selfTower = 'c';
 
    if (relation.m_target == aTower)        targetTower = 'a';
    else if (relation.m_target == bTower)    targetTower = 'b';
    else                                    targetTower = 'c';
 
    printf("%d원판이 %cTower에서 %cTower로 이동되었습니다.\n", relation.m_target->top(), selfTower, targetTower);
}
 
int main() {
    Stack<int> aTower, bTower, cTower;
    Stack<int> *self, *target, *other;
    Stack<Relation> commandStack;
    
    Relation relation(&aTower, &cTower, &bTower);
    int self_top, target_size;
    int i, j, size;
 
    // 원판 설정
    printf("Size : ");
    scanf("%d", &size);
 
    for (i = size; i >= 1; i--)
        aTower.push(i*2 - 1);
 
    // 현재 타워에서 목적 타워로 모든 원판을 옮길 것을 예약
    size = relation.m_self->size();
    for (i = 0; i < size; i++)
        commandStack.push(relation);
    
    // 예약된 모든 명령어를 실행
    while (!commandStack.empty()) {
        relation = commandStack.pop();
 
        self = relation.m_self, target = relation.m_target, other = relation.m_other;
 
        // 옮길 수 있는 경우
        if (target->empty() || self->top() < target->top()) {
            target->push(self->pop());
            render(relation, &aTower, &bTower, &cTower);
            // getchar();
        }
        // 현재 원판보다 더 작은 원판이 있는 경우
        else {
            self_top = self->top();
            target_size = target->size();
 
            // 작은 원판이 어디까지 있는지 탐색 (중간값을 확인하는 식으로 초기화 가능)
            for (i = target_size - 1; i >= 0 && self_top > target->elementAt(i); i--);
 
            // 작은 원판이 되돌아 올 것을 예약
            for (j = i + 1; j < target_size; j++)
                commandStack.push(Relation(other, target, self));
            // 현재 원판을 옮길 것을 예약
            commandStack.push(Relation(self, target, other));
            // 작은 원판을 다른 곳으로 옮길 것을 예약
            for (j = i + 1; j < target_size; j++)
                commandStack.push(Relation(target, other, self));
        }
    }
 
    // 출력
    int num;
    for (i = cTower.size() - 1; i >= 0; i--) {
        num = cTower.elementAt(i);
        for (j = 0; j < num; j++)
            printf("*");
        printf("\n");
    }
}
cs


이 문제의 목적은 A 타워에 있는 N층의 원판을 C 타워로 옮기는 것입니다.
A 타워에 있는 3층의 원판을 C 타워로 옮길 경우 처음 상황은 다음과 같습니다.
  *     -     -
 ***   ---   ---
***** ----- -----
  A     B     C
A 타워의 최하위 층을 옮길 경우 다음과 같은 상황이 됩니다.
  -     -     -
 ---   -*-   ---
----- -***- *****
  A     B     C
그럼 이 상황은 다시 B에 있는 2층의 원판을 C 타워로 옮기는 문제로 생각할 수 있습니다.

이렇게 최하위에 존재하는 판을 옮기는 것을 기준으로 생각하면 DP 방법으로 풀 수 있습니다.

반복문으로 짜보고자 스택을 사용했지만, 사실 재귀 함수로 프로그래밍 한 것과 같습니다.

저작자표시

'프로그래밍' 카테고리의 다른 글

유튜브 뮤직 컨트롤러  (0) 2020.09.07
[개인 공부] 거북이 프로그램  (2) 2017.06.07
posted by Nehoy
2017. 5. 20. 13:23 프로그래밍/알고리즘

[프로젝트 오일러] Prob4, Prob5 Prob9, Prob10

Prob4


Prob5


Prob9 - Python


Prob10




저작자표시

'프로그래밍 > 알고리즘' 카테고리의 다른 글

탐욕 알고리즘  (0) 2020.01.11
완전 탐색  (0) 2020.01.11
[Baekjoon] 10610번: 30  (0) 2017.06.26
[프로젝트 오일러] Prob18  (0) 2017.05.20
[프로젝트 오일러] Prob96 (스도쿠)  (3) 2017.04.09
posted by Nehoy
2017. 5. 20. 13:15 프로그래밍/알고리즘

[프로젝트 오일러] Prob18

문제 사진 :



k층에서 k+1층으로 내려갈 때 큰 값으로만 내려가면 안된다. 왜냐하면 k+2층부터 n층까지가 변수가 되기 때문이다.
하지만, n-1층에서 n층으로 내려갈 때에는 변수가 될 층이 존재하지 않기 때문에 큰 값으로만 내려가면 된다. 

위 공식에 따르면, n-1층까지의 경로를 몰라도 n-1층의 한 노드에서 n층의 두 노드 중 어떠한 노드로 갈지는 알 수 있다.
이 n-1층부터 n층까지의 각각 모든 경로의 합을 n-1층에 저장해놓으면, n층의 데이터들은 쓸모가 없어지고 이것은 곧 n층이 사라졌다고 볼 수 있다.
따라서, n층의 삼각형이 n-1층의 삼각형이 된 것이다.
위 작업을 n - 1번 반복하면 삼각형 최상위 노드인 1층의 값이 이 문제에서 구하던 합이 최대가 되는 경로의 합이 된다.

// prob18.c
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
#include <stdio.h>
#include <stdlib.h>
 
// argv[0] : (output) 배열 크기
// return : 동적할당된 배열
int **inputFile(int *_size) {
    FILE *pFile;
    int **arr, size;
    int i, j;
 
    pFile = fopen("input18", "r");
    if (pFile == NULL) {
        fprintf(stderr, "파일 열기 실패 - input\n");
        return NULL;
    }
 
    fscanf(pFile, "%d", &size);
    *_size = size;
 
    arr = malloc(sizeof(int *) * size);
    for (i = 0; i < size; i++) {
        arr[i] = malloc(sizeof(int) * (i + 1));
        for (j = 0; j <= i; j++)
            fscanf(pFile, "%d", &arr[i][j]);
    }
 
    return arr;
}
void release(int **arr, int size) {
    int i, j;
 
    for (i = 0; i < size; i++)
        free(arr[i]);
    free(arr);
}
 
int max(int num1, int num2) {
    return (num1 > num2) ? num1 : num2;
}
 
int main() {
    // 예제
    //    int arr[NUM][NUM] = {{3}, {7, 4}, {2, 4, 6}, {8, 5, 9, 3}}, temp[NUM - 1];
    //    int size = 4;
    int **arr, size;
    int i, j, sum;
 
    arr = inputFile(&size);
    if (arr == NULL) return -1;
 
    // 계산
    for (i = size - 2; i >= 0; i--) {
        for (j = 0; j <= i; j++)
            arr[i][j] += max(arr[i+1][j], arr[i+1][j+1]);
    }
 
    // 결과 출력
    printf("total sum : %d\n", arr[0][0]);
 
    // 할당 해지
    release(arr, size);
 
    return 0;
}

// input18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
15
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
 
cs

// 결과
total sum : 1074


저작자표시

'프로그래밍 > 알고리즘' 카테고리의 다른 글

탐욕 알고리즘  (0) 2020.01.11
완전 탐색  (0) 2020.01.11
[Baekjoon] 10610번: 30  (0) 2017.06.26
[프로젝트 오일러] Prob4, Prob5 Prob9, Prob10  (0) 2017.05.20
[프로젝트 오일러] Prob96 (스도쿠)  (3) 2017.04.09
posted by Nehoy

티스토리툴바