백준 algorithm
-
백준 3085 - 사탕 게임백준 algorithm 2020. 5. 31. 23:50
-> 오랜만에 푸는 알고리즘 문제입니다. -> 그동안 스프링 공부하느라 포스팅을 못했습니다....... => 브루트 포스를 통해 풀어야 하는 문제입니다. => BFS DFS로 접근을 하려했지만 도저히 생각이 안 납니다. 배열의 오른쪽과 바꾸는 것과 배열의 아래쪽과 바꾸는 것 두 가지의 경우를 생각해야 합니다. 바꾼 다음에 check라는 함수를 만들어 위아래로 했을 때 길게 나오는 배열의 수와 옆으로 했을 때 길게 나오는 배열의 수를 확인해야 합니다. 위의 두 가지의 경우를 확인하고 각자 나온 결과값 중 가장 긴 값을 출력합니다. 배열의 길이보다 긴 최댓값은 없으므로, 배열의 길이만큼의 값이 나온다면 도중에 멈출 수 있습니다. // // main.cpp // Baekjoon // // Created by ..
-
백준 2309 - 일곱난쟁이백준 algorithm 2020. 5. 16. 00:56
=> Brute Force 문제이다. => 모든 경우의 수를 탐색해보면 알 수 있다. 알고리즘은 아래와 같다. 배열을 입력받으며, 전체 난쟁이(9명)들 키의 합을 구한다.(sum) 배열을 sort 시킨다. STL을 써도 무방한다. ( 이 경우, 배열의 크기 또한 정해져 있다.) 해당 배열을 i가 index 0부터 9까지 탐색한다, j는 i+1부터 9까지 탐색한다. i, j index 값을 sum에서 뺏을 때, 100이 되는 i와 j를 구한다. => 위의 방법을 통해 제외되는 두 명의 난쟁이를 구할 수 있다. *** 본인은 원하는 난쟁이를 구한 경우, 프로그램을 끝내지 않고, 모든 경우의 수를 탐색하도록 하여 여러 번 틀렸었다. *** 원하는 i와 j를 찾았을 경우, 프로그램을 중지시켜주는 것이 정답을 맞..
-
백준 11053 - 가장 긴 증가하는 부분 수열백준 algorithm 2020. 5. 9. 12:42
=> DP 문제이다. => 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. => 수열 A =[10, 20, 10, 30, 20 ,50] => 가장 긴 증가하는 부분 수열 A = [10, 20, 30, 50] => D[N] : A[i] 를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 => D[i]는 A[i]를 반드시 포함하여야 한다. => 위의 그림을 보면 어떤 방식으로 이루어지는지 알 수 있다. **가장 긴 증가하는 부분 수열 구하는 알고리즘 for(int i=0; i N; for(int i=0; i> A[i]; } int D[N]; for(int i=0; i
-
백준 2193 - 이친수백준 algorithm 2020. 4. 23. 17:39
=> DP 문제이다. => DP [i][j] => i : 몇 자릿수인지 나타냄 => j : 어떤 숫자로 끝나는지 나타냄 DP[i][0] = DP[i-1][0] + DP[i-1][1] => 0으로 끝나는 수의 경수, 앞의 수가 1이어도 되고 0이어도 된다. DP[i][1] = DP[i-1][0] => 1으로 끝나는 수의 경수, 앞의 수가 0이어야 된다. 위의 식대로 풀어도 된다. 본인은 하나씩 손으로 풀어보며 식을 세우게 되었다. DP[i] = DP[i-1] + DP[i-2] => 위의 식을 통해 원하는 값을 얻을 수 있다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr)..
-
백준 15990 - 1, 2, 3 더하기 5백준 algorithm 2020. 4. 23. 16:29
=> DP 문제이다. => 기존 문제아 달리 이차원 배열로 하여 문제를 해결하여야 한다. dp[i][j] : i를 1,2,3의 합으로 나타내는 방법의 수, j : 마지막에 사용한 수 dp[i][1] : 바로 전에 사용할 수 있는 수는 2,3 dp[i][2] : 바로 전에 사용할 수 있는 수는 1,3 dp[i][3] : 바로 전에 사용할 수 있는 수는 1,2 if (n - 1 >= 0) { dp[n][1] = (dp[n - 1][2] + dp[n - 1][3]) % mod; } if (n - 2 >= 0) { dp[n][2] = (dp[n - 2][1] + dp[n - 2][3]) % mod; } if (n - 3 >= 0) { dp[n][3] = (dp[n - 3][1] + dp[n - 3][2]) % ..
-
백준 16194 - 카드 구매하기 2백준 algorithm 2020. 4. 15. 02:17
=> 카드 구매하기 1번 문제를 참조하여 풀 수 있다. https://codingham.tistory.com/124 백준 11052 - 카드 구매하기 => DP 문제입니다. => 카드 i개를 구매할 때의 최대 비용을 생각해야 합니다. => D[i] : 카드 i개 구매하는 최대 비용 =>카드 i개를 구매하는 방법의 가짓수 카드 1개 들어있는 카드팩 구매, 카드 i - 1개 구매.. codingham.tistory.com => 위와 다른 것은 최솟값을 구하는 것이다. ***주의점 => 카드를 구매하는 비용은 0보다 크다 => 배열의 초기값 설정을 잘해주어야 한다. => D에 들어갈 수 있는 값의 최댓값은 1000 * 10000이다. ( 카드의 개수 * 카드팩의 가격 ) for(int i=1; i N; vec..
-
백준 11052 - 카드 구매하기백준 algorithm 2020. 4. 14. 15:42
=> DP 문제입니다. => 카드 i개를 구매할 때의 최대 비용을 생각해야 합니다. => D[i] : 카드 i개 구매하는 최대 비용 =>카드 i개를 구매하는 방법의 가짓수 카드 1개 들어있는 카드팩 구매, 카드 i - 1개 구매 카드 2개 들어있는 카드팩 구매, 카드 i - 2개 구매 .... .... .... 카드 i 개 들어있는 카드팩 구매, 카드 0개 구매 이를 나타내면 P[1] + D[i-1] 위와 같이 표현할 수 있습니다. 이를 코드로 표현하면 for(int i=1; i N; vector P(N+1); vector D(N+1); int tmp; for(int i=1; i> tmp; P[i] = tmp; } for(int i=1; i
-
백준 11726 - 2 x n 타일링 (c+백준 algorithm 2020. 4. 6. 01:16
=> DP 문제이다. => 2 x n 크기의 사각형이 있을 때, 맨 오른쪽에 타일을 채워 넣는 경우를 생각해보자. 1. ( 2x 1 ) 타일이 세로로 세워져 있는 경우 2. (2 x 1 ) 타일이 가로로 두개 놓여 있는 경우 => 위의 경우를 보고 점화식을 세울 수 있다. * arr[i] : i 크기의 사각형이 있을 때 타일을 놓을 수 있는 방법의 배열 arr [ i ] = arr [ i -1 ] + arr[ i -2 ] => 위의 점화식을 사용하여 간단하게 구현가능하다. => 초기배열값은 넣어주어야 한다. => arr[1] = 1, arr[2] = 2 => arr에 넣을때 10007로 나눠주지 않으면 int의 범위를 벗어나는 일이 생긴다. 배열에 값을 넣으면서 나눠서 넣어주도록 해야 한다. #inclu..