2020. 1. 11. 21:05
보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.
'프로그래밍/알고리즘'에 해당되는 글 15건
- 2020.01.11 완전 탐색
- 2017.06.26 [Baekjoon] 10610번: 30
- 2017.05.20 [프로젝트 오일러] Prob4, Prob5 Prob9, Prob10
- 2017.05.20 [프로젝트 오일러] Prob18
- 2017.04.09 [프로젝트 오일러] Prob96 (스도쿠)3
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. 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
프로그래밍/알고리즘
Sudoku.zip오일러 프로젝트 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 |
