영우

백준 1890 문제 해결 경로의 개수를 세는 문제이다. 여러가지 접근 방법이 있을 수는 있겠지만 가장 먼저 든 생각은 역시 DFS나 BFS를 이용한 완전탐색이었다. 아래그림을 보자 완전탐색의 문제점 모든 칸의 값이 1일 경우에 각 행이나 열의 마지막 칸을 제외한 모든 칸에서 2개의 경우가 발생한다. 이 의미는 한칸 전진할때마다 2개의 가능성이 생기는 것이고 행과 열의 길이가 100이므로 100 * 100개의 칸에서 2개의 경우가 생긴다는 의미 이므로 최악의 경우에 약 2의 10000제곱을 계산해야한다. 해결 방안 결국 모든 경로를 계산해 최종적인 위치로 도달할 수 있는지의 방법으로는 불가능하다. 이를 개선하는 아이디어는 중복을 없애는 것이다. 위의 그림에서 1, 1위치에서 2, 2로 가는 방법을 생각해보..

DP에 대해 한번 정리를 하고 싶어 DP문제를 찾아서 풀어보았다. DP에 대한 개념부터 한번 정리하겠다. Dynamic Programming 동적계획법의 정의는 하나의 큰 문제를 여러개의 작은 문제로 나누어 해결하는 것이다. 나는 이러한 정의가 분할정복과 크게 차이가 없다고 느껴져, 반복되는 부분의 결과를 써 놓아 기억하고, 활용하기라고 생각하고있다. DP 예시 DP를 활용했을때 시간복잡도적으로 이득을 볼 수 있는 가장 대표적인 예시가 피보나치수열이다. 피보나치 수열은 F(0) = 0, F(1) = 1, F(N) = F(N-1)+F(N-2)인 수열이다 피보나치 수열 구현 코드 재귀를 통한 구현이다. 가장 기본적인 아이디어로, 위의 수식을 그대로 코드로 구현한 것을 확인할 수 있다. Top-Down방식으로..

공부하게된 이유 이전에 알고리즘 문제를 풀다가 해설로 귀류법으로 이유를 설명한 것을 보았다. 그래서 귀류법이 대강 결과를 부정해서 모순을 발견해 명제가 참임을 증명하는 거구나 ~ 하고 넘어갔지만, 정확히 알고 싶어 귀류법을 포스팅하려했다. 그런데 귀류법을 찾으려고 하니 매번 귀류법의 세트메뉴인 대우증명법의 설명이 같이나오는것이다 ! 그래서 대우증몀법을 포스팅하게 되었다. 대우증명법 ? 명제의 결과는 항상 명제의 대우의 결과와 같다. 명제의 결과가 참이면 명제의 대우의 결과가 참이고, 명제의 결과가 거짓이면 명제의 대우의 결과도 거짓이다. 이에 기반해서 명제의 대우를 구하고, 대우가 참임을 증명해 명제의 참을 증명하는것이 대우증명법이다. 대우증명법을 사용한 증명 아래의 그림에서 n이 자연수일때, n*n이 ..

백준 1522 문제풀이 문제를 보고 꽤 오래 고민했다. 내가 알고있는 대부분의 알고리즘을 생각해 보아도 답이 나오지 않았다. 우선 인풋의 크기가 1000개로 꽤 작아 완전탐색을 생각했는데, DFS든 BFS든 모든요소가 이미 가본곳에 대한 중복체크가 매우 어렵다고 생각해 하지 않았다. 또 그리디를 생각했는데 aabbbab같은 문자열일때 연속된 개수를 세 2 3 1 1같이 표현한 후 이것을 병합하며 세 보려고 했다. 하지만 이것도 도저히 최선의 경우를 찾지 못해 하지 않았다. 깊은 고민후 서치를 해 보았는데 슬라이딩 윈도우라는 개념을 사용하라고 되어있었다. 간단하게 이해하기로는 창틀을 만들어 창틀안의 값만보고 판단하는 것이었다. 이후 조금 잘못 이해했다는것을 깨닫고 수정했지만, 일단 문제를 해결할 수는 있었..

백준 24533 문제 풀이 30만개의 물질을 가지고 있기 때문에 N혹은 NlogN의 시간정도에 계산을 해내야 했다. 이런 문제는 일반적으로 그리디하게 규칙을 찾아 우선순위 큐에서 뽑아 NlogN으로 하거나, DP로 무언가 기억해 놓고 N의 시간에 해결을 하는것이 국룰인데, 아무리 생각해도 방법이 보이지 않았다. 어떤 방식으로 합쳐야지 가장 큰 에너지값을 얻을수 있을지 잘 떠오르지 않아, 임의로 4개의 테스트케이스를 만들어 손으로 써가며 모든 결합하는 경우의 수를 계산하면서 통찰을 얻으려고했다. 실제로 계산을 해보니 결합순서와 관계없이 에너지량이 항상 같은것을 확인하였다. 하지만 어떻게 계산을 하던 에너지량이 같은것은 증명을 통해 보였어야 하는데, 수학적인 역량이 아쉬워서 문제를 풀 당시에는 증명하지 못했..

백준 9613 여느날과 같이 백준 문제를 풀던 중 GCD라는 용어를 만나게 되었다. GCD가 해당 문제에서 제시한 개념인줄 알고 눈을 부릅 뜨고 찾아봤지만... 그런건 없었다... ㅎㅎ 찾아보니 GCD는 Greatest Common Divisor의 약자로 최대 공약수를 의미하는 것이었다. 기존의 코드 따로 특별한 알고리즘에 대해서 알고있는게 없기 때문에 일단 생각나는데로 코드를 작성했다. int getGCD(int a, int b) { if(!a || !b) return 0; vector vt; vt.push_back(1); int start = 2; while(1){ if(start > a) break; if(a % start == 0){ vt.push_back(start); a = a / start;..