2020. 1. 11. 22:15
보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.
'프로그래밍'에 해당되는 글 18건
- 2020.01.11 탐욕 알고리즘
- 2020.01.11 완전 탐색
- 2017.06.26 [Baekjoon] 10610번: 30
- 2017.06.07 [개인 공부] 거북이 프로그램2
- 2017.05.20 [개인 공부] 하노이 타워
- 2017.05.20 [프로젝트 오일러] Prob4, Prob5 Prob9, Prob10
- 2017.05.20 [프로젝트 오일러] Prob18
- 2017.04.09 [프로젝트 오일러] Prob96 (스도쿠)3
2020. 1. 11. 21:05
보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.
2017. 6. 26. 14:23
프로그래밍/알고리즘
그리디 알고리즘을 연습하기 위해서 찾은 문제다.
30의 배수
- 3의 배수 : 모든 자릿수의 합이 3의 배수가 되면 된다.
- 10의 배수 : 1의 자리 수가 0이면 된다.
위의 조건을 만족하는 상황에서 가장 큰 수를 만들면 된다. 가장 큰 수는 주어진 수들을 내림차순 정렬함으로써 얻을 수 있다.
Ex. 2931 -> 9321
코드는 3의 배수인지를 확인하고 내림차순 정렬한 후 끝자리가 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 44 45 46 47 48 | // https://www.acmicpc.net/problem/10610 // [2017-06-26] 14시 05분 #include <iostream> #include <stdlib.h> #include <cstring> using namespace std; bool check(char buff[], size_t len) { unsigned int total = 0; for (int i = 0; i < len; i++) total += buff[i] - '0'; if (total % 3 == 0) return true; else return false; } int compare(const void *pCh1, const void *pCh2) { char ch1 = *(char *)pCh1; char ch2 = *(char *)pCh2; if (ch1 > ch2) return -1; else if (ch1 < ch2) return 1; else if (ch1 == ch2) return 0; } int main() { char buff[100001]; size_t buffLen; cin >> buff; buffLen = strlen(buff); if (!check(buff, buffLen)) cout << -1 << endl; else { qsort(buff, buffLen, sizeof(char), compare); if (buff[buffLen - 1] != '0') cout << -1 << endl; else cout << buff << endl; } return 0; } | cs |
가장 큰 수를 앞자리로 가져오는 것이 그리디 알고리즘인거 같다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| 탐욕 알고리즘 (0) | 2020.01.11 |
|---|---|
| 완전 탐색 (0) | 2020.01.11 |
| [프로젝트 오일러] Prob4, Prob5 Prob9, Prob10 (0) | 2017.05.20 |
| [프로젝트 오일러] Prob18 (0) | 2017.05.20 |
| [프로젝트 오일러] Prob96 (스도쿠) (3) | 2017.04.09 |
2017. 6. 7. 13:39
프로그래밍
거북이 명령 프로그램 
Turtle.zip
수업 과제로 있길래 만들어봤다.
// Example.mp4
// Turtle.cpp
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 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 | #include <iostream> #include <fstream> #include <vector> #include <queue> #include <string> #include <Windows.h> using namespace std; #define MAX_LINE_LENGTH 100 void gotoxy(int x, int y) { COORD Pos = { x, y }; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), Pos); } class Vector2 { public: Vector2() { x = 0; y = 0; } Vector2(int x, int y) { this->x = x; this->y = y; } Vector2& operator+=(const Vector2& vector) { x += vector.x; y += vector.y; return (*this); } int x, y; }; class Turtle { public: void readFile(char *fileName) { ifstream commandFile; char command[MAX_LINE_LENGTH]; init(); // 객체 초기화 // 파일 읽기 commandFile.open(fileName, ios::in); if (commandFile.fail()) { fprintf(stderr, "파일이 열리지 않습니다.\n"); system("pause"); exit(-1); } while (!commandFile.eof()) { commandFile.getline(command, MAX_LINE_LENGTH); commandList.push_back(command); } commandFile.close(); // 계산 compute(0, commandList.size() - 1); } void draw() { // 배열 생성 및 초기화 size_t width = (arrSize[1] + -arrSize[3]) * 2 + 1, height = (arrSize[0] + -arrSize[2]) * 2 + 1; // * 2 : 간선과 정점, + 1 : 시작 점 포함 char ***drawArr = createDrawArr(width, height); char *drawChar; pos = Vector2(-arrSize[3] * 2, -arrSize[2] * 2); // start = (Left, Down) // 배열에 그리기 while (!dirQueue.empty()) { dirIndex = dirQueue.front(); if (dirIndex % 2 == 0) drawChar = "│"; // Up or Down else drawChar = "─"; // Right or Left pos += dirArr[dirIndex]; drawArr[pos.y][pos.x] = drawChar; // 간선 그리기 pos += dirArr[dirIndex]; drawArr[pos.y][pos.x] = "＊"; // 정점 그리기 dirQueue.pop(); } // 화면에 그리기 for (int i = height - 1; i >= 0; i--) { for (int j = 0; j < width; j++) printf("%s", drawArr[i][j]); printf("\n"); } destroyDrawArr(drawArr); } void sequenceDraw(unsigned int delay) { size_t width = (arrSize[1] + -arrSize[3]) * 2 + 1, height = (arrSize[0] + -arrSize[2]) * 2 + 1; // * 2 : 간선과 정점, + 1 : 시작 점 포함 char *drawChar; pos = Vector2(-arrSize[3] * 2, -arrSize[2] * 2); // start = (Left, Down) while (!dirQueue.empty()) { dirIndex = dirQueue.front(); if (dirIndex % 2 == 0) drawChar = "│"; // Up or Down else drawChar = "─"; // Right or Left pos += dirArr[dirIndex]; gotoxy(pos.x * 2, height - pos.y - 1); printf("%s", drawChar); // 간선 그리기 Sleep(delay); pos += dirArr[dirIndex]; gotoxy(pos.x * 2, height - pos.y - 1); printf("%s", "＊"); // 정점 그리기 dirQueue.pop(); Sleep(delay); } gotoxy(0, height + 1); } private: void init() { commandList.clear(); dirQueue = queue<int>(); dirIndex = 0; pos = Vector2(0, 0); memset(arrSize, 0, sizeof(int) * 4); } int classifyCommand(string command) { // 탭 제거 int i, len = command.size(); for (i = 0; i < len && command[i] == '\t'; i++); // 분류 if (command[i] == 'r') { if (command[i + 1] == 'e') return 0; // repeat else if (command[i + 1] == 'i') return 2; // right } else if (command[i] == 'g') return 1; // go else if (command[i] == 'l') return 3; // left return -1; } void compute(int start, int end) { for (int i = start + 1; i < end; i++) { switch (classifyCommand(commandList[i])) { case 0: // repeat int repeatNum, tapNum, endTapNum, endLine; sscanf(commandList[i].c_str(), "%*s %d", &repeatNum); // 반복 횟수 가져오기 // end 문자열 찾기 for (tapNum = 0; commandList[i][tapNum] == '\t'; tapNum++); for (endLine = i + 1; i < end; endLine++) { for (endTapNum = 0; commandList[endLine][endTapNum] == '\t'; endTapNum++); if (endTapNum == tapNum) break; } if (commandList[endLine][endTapNum] != 'e') { fprintf(stderr, "올바른 형식이 아닙니다.\n"); system("pause"); exit(-2); } for (int j = 0; j < repeatNum; j++) compute(i, endLine); i = endLine; break; case 1: // go dirQueue.push(dirIndex); pos += dirArr[dirIndex]; switch (dirIndex) { case 0: if (pos.y > arrSize[0]) arrSize[0] = pos.y; break; // Up case 1: if (pos.x > arrSize[1]) arrSize[1] = pos.x; break; // Right case 2: if (pos.y < arrSize[2]) arrSize[2] = pos.y; break; // Down case 3: if (pos.x < arrSize[3]) arrSize[3] = pos.x; break; // Left } break; case 2: // right dirIndex = (++dirIndex % 4); break; case 3: // left if (--dirIndex < 0) dirIndex = 3; break; } } } char ***createDrawArr(size_t width, size_t height) { char ***drawArr; drawArr = new char **[height]; for (int i = 0; i < height; i++) { drawArr[i] = new char *[width]; for (int j = 0; j < width; j++) drawArr[i][j] = " "; } return drawArr; } void destroyDrawArr(char ***& drawArr) { if (drawArr != nullptr) { size_t height = (arrSize[0] + -arrSize[2]) * 2 + 1; for (int i = 0; i < height; i++) delete[] drawArr[i]; delete[] drawArr; drawArr = nullptr; } } private: const Vector2 dirArr[4] = { Vector2(0, 1), Vector2(1, 0), Vector2(0, -1), Vector2(-1, 0) }; // Up, Right, Down, Left vector<string> commandList; queue<int> dirQueue; int dirIndex; Vector2 pos; int arrSize[4]; // Up, Right, Down, Left }; int main(int argc, char *argv[]) { Turtle turtle; char *fileName; if (argc <= 1) { fileName = "input.txt"; system("cls"); turtle.readFile(fileName); turtle.sequenceDraw(25); system("cls"); turtle.readFile(fileName); turtle.draw(); system("pause"); return 1; } for (int i = 1; i < argc; i++) { fileName = argv[i]; system("cls"); turtle.readFile(fileName); turtle.sequenceDraw(25); system("cls"); turtle.readFile(fileName); turtle.draw(); system("pause"); } } | cs |
// 설명.txt
핵심 알고리즘은 Dynamic Programming(큰 문제를 작은 문제로 쪼개 해결하는 것)을 기초로 하였다.
제일 중요한 코드는 Turtle 클래스의 compute 함수다.
compute 함수는 commandList 배열에 들어있는 명령어들을 처리하여, dirQueue 에 dirArr의 index를 뜻하는 정수들을 넣어준다.
매개변수 start와 end는 처리할 commandList 배열의 시작과 끝을 말한다.
repeat 명령어의 처리는 반복문과 재귀함수를 이용했다.
0.program
1. go
2. repeat 3
3. go
4. right
5. end
6.end
위와 같이 입력예제가 있다고 가정해보자.
일단, 반복 횟수인 3을 추출한다
repeat와 end 사이에 있는 3-4번줄 명령어는 또 다른 코드라고 볼 수 있다.
따라서, compute(2, 5)를 호출하여 사이에 있는 명령어를 처리할 수 있다.
이를 3번 반복하기 위해서 다음과 같은 코드가 되게 한다.
int num = 3;
for (int i = 0; i < num; i++)
compute(2, 5);
이후 5번 줄까지의 명령어는 이미 처리되었기 때문에, 다음에 처리할 명령어의 줄을 6으로 설정해야 한다.
i = endLine;
위 코드가 해당 역할을 해준다.
실수했던 점은 repeat에 대응하는 end 문자열을 찾는 일이였다.
처음에는 맨아래서부터 tap의 길이를 무시하고 end를 찾아 올라왔었는데,
0. program
1. repeat 3
2. go
3. end
4. repeat 2
5. go
6. end
7. end
이런 코드가 있을 경우 제대로된 처리가 되지 않았다.
따라서, 기존에 했던 방법을 철회하고 해당 repeat 줄을 기점으로 차례대로 내려가면서 같은 tap의 길이이면서 end문자열이 있는 줄을 찾는 방식으로 프로그래밍 하였다.
위 예제의 경우 기존 코드는 1번줄 repeat에 6번줄 end를 대응시키는데, 변경시킨 코드의 경우 1번줄 repeat에 3번줄 end를 대응시킨다.
이로써 해당 문제를 해결하였다.
'프로그래밍' 카테고리의 다른 글
| 유튜브 뮤직 컨트롤러 (0) | 2020.09.07 |
|---|---|
| [개인 공부] 하노이 타워 (0) | 2017.05.20 |
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 |
2017. 5. 20. 13:23
프로그래밍/알고리즘
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 |
2017. 5. 20. 13:15
프로그래밍/알고리즘
문제 사진 :
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 |
2017. 4. 9. 18:13
프로그래밍/알고리즘
오일러 프로젝트 96번 문제(http://euler.synap.co.kr/prob_detail.php?id=96)를 풀기 위해 작성한 코드다.
문제의 핵심은 당연하게도 스도쿠를 푸는 것이다.
스도쿠를 풀기 위해서 사용된 알고리즘은 다음과 같다.
가. 유일 가능성을 갖는 자리를 찾고 존재 여부에 따라 다음을 실행한다.
- 유일 가능성을 갖는 자리가 존재할 경우
1. 해당 자리를 가능성이 있는 숫자로 확정한다.
2. 숫자가 확정된 자리와 그에 영향을 받는 자리의 가능성을 제거한다.
3. 다시 '가'를 실행한다.
- 존재하지 않을 경우
1. '나'를 실행한다.
나. 숫자가 확정되지 않은 자리가 있는지 확인한 후 존재 여부에 따라 다음을 실행한다.
- 확정되지 않은 자리가 존재하지 않을 경우
1. 문제가 풀린 경우이다. (End)
- 존재할 경우
1. '다'를 실행한다.
다. 숫자가 확정되지 않았으면서 가능성이 하나도 없는 자리를 찾는다.
라. '다'에서 찾은 자리가 있을 경우 가정 유무에 따라 다음을 실행한다.
- 가정된 것이 없을 경우
1. 문제가 잘못된 경우이다. (Error!)
- 가정된 것이 있을 경우
1. 최근에 행한 가정을 제거한다. (가정하기 전 풀이 상황으로 돌아간다.)
2. (x, y)자리에서 n의 수를 가정했다고 할 경우, (x, y)자리의 n의 가능성을 없앤다.
마. 주어진 정보만으로는 풀이가 불가능하므로 가정을 한다.
1. 현재 풀이 상황을 스택에 저장한다.
2. 임의의 가능성 있는 자리를 찾는다.
3. 해당 자리에 들어갈 수 있는 수 중 하나를 확정한다.
4. 숫자가 확정된 자리와 그에 영향을 받는 자리의 가능성을 제거한다
바. '가'로 돌아간다.
* 유일 가능성이란 줄이나 상자에서 하나의 가능성만 갖을 경우를 의미한다.
Ex. 다음과 같은 상황에서 (9, 2)자리가 9라는 숫자로 유일 가능성을 갖는다.
[그 이유는 (9,2)자리가 (3,1)상자에서 유일하게 9의 가능성을 갖고 있기 때문이다.]
내 생각에 코드에서 개선해야 되는 부분은 2가지가 있다.
1. 한 자리에 하나의 가능성만 있는 경우를 확인하지 않았다. (현재는 가정으로 대신하고 있는거 같다.)
2. 가능성을 확인할 때 2중 for문으로 모든 자리를 확인하는게 아니라, 가능성이 변화된 부분을 중심적으로 확인하면 좋을거 같다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| 탐욕 알고리즘 (0) | 2020.01.11 |
|---|---|
| 완전 탐색 (0) | 2020.01.11 |
| [Baekjoon] 10610번: 30 (0) | 2017.06.26 |
| [프로젝트 오일러] Prob4, Prob5 Prob9, Prob10 (0) | 2017.05.20 |
| [프로젝트 오일러] Prob18 (0) | 2017.05.20 |
