본문 바로가기

PS

 (25)
백준 2579번: 계단 오르기 C++ Code 벽 부수고 이동하기 문제의 아이디어가 떠올라 적용하여 풀었다. 메인 아이디어는 빨리 떠올렸지만 구현에 시간이 많이 소요됐다. 메인 아이디어의 경우에는 특정 경우의 수가 가지는 상태에 대한 표현 방법이였다. 이러한 문제를 하나의 차원을 더 추가해 따로 처리를 했다. 그 이후는 다른 dp문제와 같은 방식으로 풀이했다. 여러 아이디어가 결합되어 있어 구현할 때 다소 혼돈이 와서 아쉬웠다.
백준 1932번: 정수 삼각형 C++ Code DP로 경우의 수를 푸는 문제이다. 앞의 RGB거리 문제와 연관이 있고 같은 원리로 풀 수 있다. 한 층의 값들을 다 결정지어놓는 식으로 풀이하는 것으로 내가 푼 BFS형태의 문제와 닮아 있다. 1층 부터 시작해서 각층의 최댓값을 업데이트 시키며 올라간다. 0번째 열의 요소들은 따로 처리해줘야 하는 부분이 조금 까다롭긴 했지만, RGB거리 문제의 중심 아이디어만 파악하고 있다면 큰 어려움은 없는 문제였다.
백준 1149번: RGB거리 C++ Code 직관적인 해설을 하기 힘든 문제이다. dp를 이용해 최적의 경우를 구하는 문제인데 하나의 선택이 미치는 영향이 크고 예측할 수 없기 때문에 경우의 수를 가지치기 하기 힘들다. 다만 영향을 끼치는 범위가 전후 1개 노드로 좁기 때문에 시간, 공간 복잡도가 그렇게 심해지지는 않는다.
백준 1904번: 01타일 C++ Code dp는 점화식 문제에도 자주 응용되지만 경우의 수와도 큰 연관이 있다. 그리고 놀랍게도 이 문제는 점화식 문제이면서도 경우의 수와도 연관이 있다. n이 4인 경우를 생각해보자. xxxx는 00xx 또는 1xxx 두 경우로 나누어진다. 이렇게 작은 식으로 쪼개지다 보면 n이 1인 경우와 2인 경우로 나뉘어진다. 따라서 가장 작은 단위를 정의해놓고 반복문으로 처리해준다. 코드를 써놓고 보니 피보나치 수열이라는 것을 알 수 있었다. 경우의 수에 대한 표현이 점화식으로 연결되었다.
백준 1003번: 피보나치 함수 C++ Code dp문제는 탐색으로 푸는 것도 가능하다. 다만 값들을 저장해놓는다는 점에서 시간효율이 우수하다. 또한 데이터 간의 연결을 표현하는 점화식 풀이에도 자주 사용된다. 때문에 dp의 대표적인 예가 피보나찌인 이유가 여기에 있다. i번 째 피보나찌 수열이 가지고 있는 0과 1의 개수는 i-1번 째와 i-2번 째를 더한 수와 같다 따라서 pair형태의 배열을 통해 단순 피보나치 연산을 했다.
백준 2748번: 피보나치 수 2 C++ Code DP 카테고리의 첫 번째 문제이다. 피보나찌 수열은 문제 풀이 방식이 다양하다. 재귀로 해결할 수도 있고 단순 반복 연산으로도 해결할 수 있다. 하지만 가장 메모리 효율이 좋은 방식은 dp이다. dp방식은 자주 사용되는 데이터를 저장해두어 연산의 중복을 막아 시간효율을 증대 시키는 알고리즘이다. 첨부한 코드를 보면 반복문을 통해 아래순번부터 차근차근 쌓아 올렸다. 사실 단순한 연산이지만 재귀로 풀이하는 것 보다는 빠르다.
에라토스테네스의 체 소수가 특정한 규칙이 없다보니 구하기 힘들지만 에라토스테네스의 체를 이용하면 쉽고 간결하고 구할 수 있다. 기본 규칙은 다음과 같다. 1. 2 이상의 자연수를 오름차순으로 정렬한 배열과 소수를 담을 배열을 준비한다.(0, 1은 자연수가 아니므로) 2. 자연수 배열 맨 앞의 값을 소수 배열에 담는다. 3. 해당하는 값을 약수로 하는 모든 값을들 자연수 배열에서 제거한다. 2~3의 과정을 반복한다.
유클리드 호제법 Euclidian Algorithm https://www.youtube.com/results?search_query=euclidean+algorithm euclidean algorithm - YouTube www.youtube.com https://www.acmicpc.net/problem/2609 최대공약수 Greatest Common Divsor, 최소공배수 Least Common Muliple을 구하는 알고리즘이다. 일명 유클리드 호제법. 최대공약수를 가지고 최소 공배수를 구하는 법은 쉽다. 두 수 A, B가 주어졌을 때 중복되는 부분인 최대공약수를 한번 나누어주면 된다. 문제는 최대공약수를 구하는 것인데, 이 때 유클리드 호제법을 이용한다. 방법은 위 영상과 같이 그저 따라만 가면 되는거라 크게 어려운 부분이 없지만 그 안에 담겨져..

티스토리툴바