728x90 Algorithm (C++ based)70 백준 No.2447 [별 찍기 - 10] // Baekjoon Online Judge No.2447 [별 찍기 - 10] 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 30 31 32 33 34 35 36 37 38 #include #include #include using namespace std; vector map; void solve(int n, int x, int y) { if (n == 1) { map[x][y] = '*'; return; } // cout 되는것이 아닌 map 에 입력을 하는 것. int div = n / 3; for (int i = 0; i num; map.assign(num, vector(num, ' ')); s.. 2021. 1. 24. 백준 No.10757 [큰 수 A+B] // Baekjoon Online Judge No.10757 [큰 수 A+B] 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include #include using namespace std; int main() { string A, B; bool AisLonger = false; bool BisLonger = true; cin >> A; cin >> B; int maxLen = B.length(); int minLen = A.length(); if (A.length().. 2021. 1. 5. 백준 No.10844 [쉬운 계단 수] // Baekjoon Online Judge No.10884 [쉬운 계단 수] 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 30 31 32 33 34 #include #include using namespace std; int N; int main() { cin >> N; vector SN; SN.assign(10, vector(N + 1, 1)); SN[0][1] = 0; for (int i = 2; i 2020. 11. 18. 백준 No.1932 [정수 삼각형] // Baekjoon Online Judge No.1932 [정수 삼각형] 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include #include using namespace std; vector tri; vector ground; int main() { int N; cin >> N; tri.assign(N + 1, vector(N + 1, -1)); ground.assign(N + 1, 0); for (int i = 1; i tri[i][j]; } } ground[1] += tri[1][1.. 2020. 11. 16. Greedy algorithm (탐욕 알고리즘) // Greedy algorithm What is Greedy algorithm? 답을 하나씩 골라가는데, 미리 정해놓은 기준에 따라 매번 가장 좋아 보이는 답을 선택하는 것이다. 하지만 을 이용하여 설계를 한다면 항상 최적의 해는 보장할 수 없다. Example 의 예시로 가장 많이 보여지는 것들 중 하나인 "거스름돈 문제"를 예시로 들어보자. "거스름돈 문제"란, 임의의 액수만큼 거스름돈을 주어야 하는데 최소한의 개수의 동전을 사용하여 주어야 할 때 해당되는 동전들을 고르는 문제이다. 예를 들어 만약 거스름돈으로 520원을 주어야 한다. 이때 520원을 줄 수 있는 방법은 다양하다. 하지만 상식적으로 10원짜리 동전 52개로 거슬러주는 것보단 500원짜리 동전 1개와 10원짜리 동전 2개로 거슬러주는.. 2020. 11. 10. 백준 No.1149 [RGB거리] // Baekjoon Online Judge No.1149 [RGB거리] 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 30 #include using namespace std; int N; int price[1001][4]; int minSum[1001][4]; int main() { cin >> N; for (int i = 1; i price[i][j]; } } minSum[1][1] = price[1][1]; minSum[1][2] = price[1][2]; minSum[1][3] = price[1][3]; for (int i = 2; i 2020. 11. 10. Dynamic programming (동적 계획) // Dynamic programming What is Dynamic programming? 이란, 문제의 입력사례를 분할하여 문제를 푸는 것이다. 흔히들 'DP'라고 많이 한다. 이 점은 분할정복과 비슷하지만, 분할정복은 Top-down(하향식) 접근방법이고 은 Bottom-up(상향식) 접근방법이다. 또한 의 특징은 이미 계산된 부분 문제가 다시 발생하면 또 계산을 하는 것이 아닌 이전의 계산값을 참조한다는 것이다. Example 우리는 의 예시로 를 들 수 있다. 좌측 삽입한 링크에 들어가면 을 사용하여 를 구현한 예시를 볼 수 있다. "Top-down(하향식) 접근방법 이란?" * 큰 문제에서 작은 부분문제를 재귀적으로 호출하여 리턴 되는 값을 이용하여 큰 문제를 해결하는 방식 "Bottom-up.. 2020. 11. 9. Sorting (정렬) // Sorting What is Sorting? 임의로 나열되어있는 자료들을 일정한 기준에 따라 배열시키는 것이다. Example 4 23 7 -3 9 15 -9 0 19 6 Q. 위에 나열된 수들을 오름차순으로 정렬하시오. A. 정답은 아래와 같다. -9 -3 0 4 6 7 9 15 19 23 More about 위 문제에서 자료의 개수는 10개이며, 각 자료들에서 보여지는 수의 범위는 그렇게 크지않다. 그렇다면, 만약 자료의 개수가 1,000,000개이고 각 자료들의 종류나 크기의 범위가 정말 크다면 정렬을 하는것이 쉽지 않을 것이다. 코딩의 Sorting algorithm에는 여러 종류가 있으며 각각 각자의 장단점을 지닌다. 그 예시로 라는 Sorting algorithm을 들어보자. (자세한 내.. 2020. 11. 7. Fibonacci sequence (피보나치 수열) // Fibonacci sequence What is Fibonacci sequence? 란, 임의의 항의 값이 이전의 두 항의 값을 더한 값을 가지는 수열을 의미한다. 이를 점화식으로 표현하면 아래와 같다. An = 1 , ( n > n; // *********** Dynamic programming *********** Fibonacci_dynamic[0] = 0; Fibonacci_dynamic[1] = 1; for (int i = 2; i > num; cout 2020. 11. 6. 백준 No.1904 [01타일] // Baekjoon Online Judge No.1904 [01 타일] How to solve 복잡할 것 같아 보이지만 N에 1, 2, 3 ... 8 까지만 대입 해보아도 결국 피보나치수열을 이룬다는 것을 알 수 있다. 하지만 이 문제에서 고려해야하는 점이 두 가지 있다. 1. 피보나치 수열을 구하는 함수를 구현할 때 1,000,000번째 항까지 구해야 하므로 Time out 이 생기지 않을 방법으로 함수를 구현하여야 한다. 2. 아무리 unsigned long long 자료형을 가진다고 해도 1,000,000번째 피보나치수는 overflow를 발생시킨다. "1. 피보나치 수열을 구하는 함수를 구현할 때 1,000,000번째 항까지 구해야 하므로 Time out 이 생기지 않을 방법으로 함수를 구현하여.. 2020. 11. 6. 이전 1 2 3 4 5 다음 728x90
