알고리즘
알고리즘14 :: BOJ_1057_토너먼트
알고리즘14 :: BOJ_1057_토너먼트
2019.02.25이 문제를 풀때 짝수, 홀수를 정확하게 찾아내고 싶어서 블로그들을 찾아봤는데, 이런 방법이 있었다. NUM = NUM / 2 + NUM % 2; 처음에 생각한 아이디어는 다음과 같다. 테스트케이스 16 8 9 의 경우 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16이면 여기서 홀수 일경우 +1 을 더해준다. 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16가 된다. 여기서 /2 를 해주게 되면 다음 순번을 확인할 수 있게 된다. 1 2 3 4 5 6 7 8 여기서도 +1을 더해준다. 2 2 4 4 6 6 8 8 마찬가지로 /2를 해주게 되면 다음 순번을 확인할 수 있다. 1 2 3 4 결국 이렇게 WINNER까지 올라가게 된다. 이때 조건을 형성하여 반복문을 빠..
알고리즘13 :: BOJ_2293_동전1
알고리즘13 :: BOJ_2293_동전1
2019.02.23DP가 어렵다고 느끼는 이유는 점화식을 세워야 한다. 이 문제는!! DP를 연습하기 좋은 문제지 않나 생각해본다. 위 두 블로그를 통해서 방법은 같지만 서로 다른 점화식을 확인할 수 있었다. 요약하자면 다음과 같다. 문제에서는 k원이라고 주어졌지만, 테스트 케이스 10원으로 예시로 든다면 1원 부터 테스트 케이스(원) 까지 만들 수 있는 방법을 전부 고려해보는것이 가장 첫 번째 스텝인것 같다. 이때 입력으로 주어진 동전을 고려해 봐야 하는데 테스트 케이스로 주어진 1원, 2원 그리고 5원을 고려해보자. 1원으로 1~10원을 만들 수 있는 방법은 각각 1원은 1가지 방법 2원도 1가지 방법 ... 10원도 한가지 방법이다. 1원으로 뭔 짓을 해봤자 1가지 방법밖에 나올 수 없다. 2원으로 1~10원을 만들..
알고리즘12 :: BOJ_2577_숫자의개수
알고리즘12 :: BOJ_2577_숫자의개수
2019.02.23핵심 포인트 : % 와 / % 는 1234567 이 있으면 10으로 % 시 7 을 획득할 수 있다. / 는 1234567 이 있으면 123456 을 획득할 수 있다. 이때 10으로 계속 % 반복하게 되면 순서대로 7 6 5 4 3 2 1 을 얻을 수 있게 된다. 여기서! 배열을 이용해서 각 배열의 index를 활용해서 0~9 까지지만 1~10으로 인지하여 각 index의 값을 추출하면 숫자마다 몇번 나타났는지 알 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include using namespace std; int main(void){ int a = 3, cnt = 0, total=1; int arr[3], arr2[10]={}; memset(arr, fa..
알고리즘11 :: BOJ_더하기사이클_1110번
알고리즘11 :: BOJ_더하기사이클_1110번
2019.01.05C++로 작성한 코드입니다. Code 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 #include #include #include using namespace std; int main() { int c; int temp, count=0; int temp_A, temp_B, temp_C; cin >> c; temp = c; while (temp != c || count == 0) { temp_A = temp % 10; //1의 자리 temp_B = temp / 10; //10의 자리 temp_C = (temp_A + temp_B) % 10; temp = (temp_A * 10) + temp_C; count++; ..
알고리즘10 :: 쇠막대기
알고리즘10 :: 쇠막대기
2019.01.04123456789101112131415161718192021222324#include #include #include #include using namespace std; int solution(string str) { vector st; int result = 0; for(int i=0; i
알고리즘이란?
알고리즘이란?
2018.12.26알고리즘이란? 문제를 해결하기 위한 여러 동작들의 모임입니다. 이를 해결하기 위해 수학적이고 논리적으로 정의된 계산 단계에 따라 원하는 출력을 하는 절차를 거칩니다. 통상적으로 알고리즘은 입력과 출력을 갖고 있습니다. 오류가 존재하면 안되는 점(명확성) 그리고 메모리의 가용영역을 고려하여 효율적인 알고리즘을 작서앻야 합니다. 하나의 알고리즘을 예로 들어보겠습니다. 하기 알고리즘은 최대 공약수를 구하는 알고리즘입니다. 최대 공약수라 함은 손으로 쉽게 구할 수 있지만 코드화 하여 알고리즘을 통해 구할 수 있는 부분도 있습니다. 본 알고리즘 로직은 큰 수에서 작은 수를 빼는 가정을 두 수 중 하나가 0이 될 때까지 반복하면, 0이 아닌 수가 최대공약수입니다. 1 2 3 4 5 6 7 algorithm gcd(..
정렬 알고리즘
정렬 알고리즘
2018.12.25정렬 알고리즘 하기 알고리즘은 각 정렬 알고리즘 종류에 따라 코드로 구현한것이니 참고 부탁드립니다. 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 11..
Dynamic Programming
Dynamic Programming
2018.12.24Dynamic Programming : 작은 문제의 답을 조합해서 큰 문제의 답을 푸는 과정이다. DaC(Divide and Conquer) 과 DP(Dynamic Programming)은 비슷하지만 다음의 차이점이 존재한다. DaC 1. 문제가 절반으로 줄어든다. 2. Function Problem 3. 결과가 한번 사용된다. 4. 분할이 성능을 향상 시킨다. DP 1. 문제가 -1로 줄어든다. 2. 최적화 문제 3. 결과가 여러번 사용된다. 4. 결과 재사용이 성능을 향상시킨다. Overlapping Subproblem 은 중복되는 부분 문제이다. 예를 들면 N번째 피보나치수를 구하는 문제를 구하는 문제는 N-1번째 N-2번째 피보나치 수를 구하는 문제가 되고 다른 수를 구할 때 같은 문제가 겹치는 ..