재원블로그 재원블로그

이 문제는 다이나믹 프로그래밍을 이용한 문제이다. 입력이 최대 2000인 자연수이므로 배열로 선언하기 좋은 크기이고, 경우의 수가 매우 많아 완전 탐색으로는 중복된 경우가 많이 생기기 때문에 다이나믹 프로그래밍을 사용하면 좋다. 이 문제의 경우 점화식은 dp[1] = 1 dp[2] = 2 dp[k] = (dp[k - 1] + dp[k - 2]) % 1234567 (k >= 3) 이 된다. 헷갈렸던 점은 1칸 전까지 오면 1가지의 경우의 수 밖에 없지만, 2칸 전까지 오면 1 1 로 오는 것과 2 한번에 오는 두가지 경우가 있지 않나하는 것이었다. 그러나 이는 중복 경우를 셀 수 밖에 없는데, 전부 한칸씩 오는 경우가 dp[k - 1]과 dp[k - 2]에 모두 해당되어 있기 때문에 dp[k - 2] 에서..

이 문제는 유클리드 호제법을 이용한 문제이다. 나는 이 문제를 풀 때 처음에 주어진 배열 안 모든 숫자에 대한 최대공약수와 최소공배수를 구하려고 했다. 하지만 이렇게 풀면 정답이 나오지 않는다. 정확한 방법은 두 수씩 짝을 지어서 그 수에 대한 최소공배수를 얻고, 그 다음 수와 이전 결과로 나온 수를 짝짓는 식으로 해야 올바른 답이 나온다. 개념에 오류가 있어 헤맸던 문제였다. #include #include #include using namespace std; int gcd(int a, int b) { if (a < b) { swap(a, b); } if (b == 0) { return a; } return gcd(b, a % b); } int solution(vector arr) { unsigned ..

이 문제는 수학 문제이다. 어떤 사람의 수가 n이라고 할 때, n이 홀수인 경우 이겼을 때 다음 라운드에서의 번호는 n / 2 + 1이고, 짝수인 경우 n / 2 가 된다는 규칙을 찾았다. 또한 a, b 둘이 만났다면 둘이 경기를 하고 난 다음 라운드의 번호가 각각 같게 된다. 이를 이용해서 문제를 풀면 쉽게 풀 수 있다. #include using namespace std; int solution(int n, int a, int b) { int answer = 0; while (a != b) { if (a % 2 == 1) { a = a / 2 + 1; } else { a = a / 2; } if (b % 2 == 1) { b = b / 2 + 1; } else { b = b / 2; } answer+..

이 문제는 프로그래머스 level 2에 있는 문제이다. 이 문제를 풀기 위해 많은 노력을 기울였지만 풀지 못했다. 정답 횟수를 1부터 n / 2까지 돌리면서 해당 숫자로 n까지 갈 수 있는지로 풀어봤지만 이건 시간 초과가 발생하고 애초에 정답도 안 나온다. 다른 어떤 방법을 써도 완전 탐색과 같은 방향으로 시간 초과가 나지 않을 수는 없었다. 그래서 구글링을 통해 코드를 봤는데, n부터 시작해서 2로 나눈 나머지를 보고 1이면 점프 횟수를 추가하는 방식으로 하면 무조건 정답이 나올 것이라는 생각이 들었다. 그리디한 방식이었는데, 이렇게 간단한 방법을 생각하지 못해 아쉬웠다. #include using namespace std; int solution(int n) { int ans = 0; while (n..

이 문제는 구현 문제이다. 일단 words 를 기준으로 완전 탐색을 하는데 words의 최대 길이가 100밖에 안되므로 시간 초과 걱정은 없다. 또한 문제에서 나온 규칙에서 중요한 것은 3, 4인데, 5는 단어의 길이가 최소 2이므로 애초에 위반할 수 없기 때문이다. words에 대해 for문을 돌리고, 3번과 4번 규칙을 만족하지 않는 경우 바로 break하고 정답을 출력하면 쉽게 풀 수 있다. #include #include #include #include using namespace std; map mp; vector solution(int n, vector words) { vector answer; int wordIndex = 0; int turn = 1; int peopleIndex = 1; s..

이 문제는 스택을 이용하는 문제이다. 주어진 문자열을 순차 탐색하면서 스택에 push하거나 pop 하므로, O(n) 시간이 걸리는데 문자열의 최대 길이가 1,000,000 이므로 충분히 시간 안에 풀 수 있다. 스택을 이용했을 때 top과 비교해서 현재 문자가 같으면 pop, 다르면 push 하고, 전체 탐색이 끝난 후 스택에 문자가 남아있으면 0, 비어있으면 1을 리턴하면 정답이 나온다. #include #include #include using namespace std; int solution(string s) { int answer = -1; // base case if (s.size() == 1) { return 0; } stack st; for (char c : s) { if (st.empty(..

이 문제는 구현 문제인 것 같다. 처음에는 입력 숫자의 최대 크기가 1,000,000 이고, 이에 대한 이진수는 1111 0100 0010 0100 0000 이고, 다음 큰 수는 대략 1111 0100 0010 1000 0000 으로 1,000,064가 되어 최대 시간 복잡도가 2^20 * 20 = 약 1억이라고 생각해 완전 탐색으로 구현하려고 했다. 그러나 생각을 더 해보면 n + 1 부터 시작해서 1의 개수가 같은 이진수가 나오는 숫자까지 반복하면 훨씬 짧은 수의 반복문으로 해결할 수 있을 것 같았다. 다음 큰 숫자가 생각보다 멀리 있지 않다는 점을 이용해서 풀었고, 정답을 맞출 수 있었다. #include #include #include using namespace std; string toBina..

이 문제는 다이나믹 프로그래밍 문제이다. 입력 n의 최대가 100,000 인데, 이를 단순히 재귀 함수로 구현해서 풀면 너무 많은 콜 스택으로 인해 프로그램이 작동하지 않는다. 이를 줄이기 위해서 점화식을 이용한 다이나믹 프로그래밍을 사용하면 풀 수 있다. 피보나치 수의 점화식은 fib[0] = 0 fib[1] = 1 fib[n] = fib[n - 1] + fib[n - 2] (n >= 2) 이므로 fib 값을 저장하기 위한 배열을 선언하고, 점화식에 쓰여진 대로 반복문을 돌리면 된다. 값을 1234567로 나눈 값을 저장해야 하므로, (a + b) % n = (a % n + b % n) % n 을 이용해서 문제를 풀었다. #include #include using namespace std; #defin..