본문 바로가기

Programming456

[C/C++] 백준 #1699 제곱수의 합(동적 계획법) 어떤 수를 제곱수의 합으로 표현할 수 있습니다. 모든 자연수의 1을 해당 수만큼 더하면 되기 때문에 모든 자연수는 가능하다고 할 수 있습니다. 예를 들어서 10과 같은 수는 1을 10번 더해도 되겠지만, 9와 1을 더해도 되고, 4+4+1+1 형태도 가능합니다. 동적계획법을 단순하게 한다면, 다음과 같이 할 수가 있습니다. n을 만들 수 있는 제곱항의 수를 \(d_n\)이라고 한다면, \[ d_0 = 0 \] \[ d_n = min( d_{n-1}+d_1, d_{n-2}+d_2, ..., d_{n/2} + d_{(n+1)/2} ) \] 그런데 이렇게 하게 되면, \(d_n\)을 구하는 알고리즘 효율이 \(O( n ) \) 형태가 되게 되고 전체적으로는 \(O(n^2)\)이 됩니다. 그것을 줄이기 위해서 .. 2022. 9. 30.
[C/C++] 백준 #1697 숨바꼭질(너비 우선 탐색) 이번 문제는 너비 우선 탐색을 이용해서 풀었습니다. 너비 우선 탐색(BFS) 아닌 방법으로도 풀 수 있을 듯 합니다만, 당장 좋은 방법은 떠오르지 않습니다. 그래프 탐색 이론을 배울 때, 너비 우선 탐색은 후에 나오는 프림 알고리즘, 다익스트라 알고리즘, A* 알고리즘의 근간이 됩니다. 너비 우선 탐색은 큐(Queue)를 사용하는데, 후에 나오는 알고리즘들은 우선 순위 큐(Priority Queue)를 사용한다는 점이 다릅니다. 사실 간선의 가중치 값이 1인 그래프를 생각한다면, 다익스트라 알고리즘을 사용할 수 있지만, 굳이 그럴 이유가 없는 것이 먼저 방문한 것들이 모두 후에 방문한 것들보다 작거나 같은 노드값을 가지고 있기 때문에 우선순위 큐를 사용할 하등의 이유가 없습니다. 제가 작성한 소스입니다... 2022. 9. 30.
[Python] 백준 #1684 같은 나머지(정수론) 이번 문제는 주어진 숫자들에 대해서 나머지가 같은 수가 되는 나눔수 중 최대의 정수를 찾는 것입니다. 나머지가 같다는 것은, 숫자들의 차이에 대한 최대공약수를 구하는 것과 같습니다. \[ Find~ maximum~ such~ D~ that~ \forall i ~ a_i ~mod ~D = k \Longleftrightarrow gcd( a_i - min(a) ) \] 음수를 피하기 위해서 주어진 수 중에 가장 작은 수를 찾습니다. 그리고 나머지 수 중에 가장 작은 수와 같은 경우를 제외하고, 그 차이를 기록합니다. 마지막으로 그 차이들의 수열의 최대 공약수를 구합니다. 다음은 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. """ baekjoon #1684 - by Aubrey Choi - creat.. 2022. 9. 29.
[C/C++] 백준 #1676 팩토리얼 0의 개수(수학) 이번 문제는 팩토리얼을 계산했을 때, 뒤에서부터 연속된 0의 개수를 세는 것입니다. 팩토리얼은 1부터 n까지의 곱을 계산한 것인데요. 20 팩토리얼만 해도 2,432,902,008,176,640,000 값이 나와서 정수 계산으로는 힘듭니다. 물론 64비트 정수형을 사용하면 조금 더 계산할 수는 있습니다. 그런데 문제는 500까지의 숫자 범위를 가지고 있습니다. 500 팩토리얼은 \( 1.2 \times 10^{1134} \) 의 숫자로 굉장히 큰 숫자가 나오며, 파이썬이나 C#과 같이 기본적으로 Big Integer가 제공되는 언어가 아니라면, 실제 팩토리얼을 계산하기 힘듭니다. n 팩토리얼 계산은 \(O(n)\) 알고리즘이라고 할 수 있지만, Big Integer 곱셈이 기본 연산이 아닌 관계로 더 오.. 2022. 9. 28.
백준 #1671 상어의 저녁식사(최대 유량) 이번 문제에 대한 알고리즘 힌트에는 이분 매칭으로 되어 있지만, 저는 최대 유량으로 풀었습니다. 상어 A 와 상어 B를 비교해서 상어 A의 조건이 상어 B보다 좋거나 같다면, 상어 A는 상어 B로 가는 간선이 있다고 선언합니다. 이렇게 하면 유향 그래프가 만들어집니다. 그런데, 상어 한마리당 오직 두마리만 먹을 수 있기 때문에 그에 대한 제한을 하면 됩니다. 최대 유량을 구하는 방법은, 상어 A가 먹을 수 있는 상어에 대해서 식사를 합니다. 두번의 식사가 가능하면 그만큼 상어의 수는 줄어듭니다. 그런데, 그 상어중 이미 다른 상어에게 먹힌 상어가 있을 수 있습니다. 그런 경우, 해당 상어를 먹은 다른 상어가 또 다른 상어를 먹을 수 있는지 검사합니다. 다른 상어를 먹을 수 없다면, 그 상어는 넘어가고 다.. 2022. 9. 27.
[C/C++] 프로젝트 오일러 #81 Path sum : two ways(동적 계획법) 이 문제는 난이도 10% 문제로, 그래프 이론을 이용해서 풀어도 되겠지만, 기본 자체가 동적 계획법을 이용하는 것이 더 쉽습니다. 시작점은 왼쪽 위의 지점이고, 오른쪽과 아래로만 이동할 수 있고, 도착점은 오른쪽 아래의 지점입니다. 다양한 경로가 나올 수 있는데, 이 때, 최대의 값을 찾는 프로그램을 작성하면 됩니다. \[ \begin{pmatrix} \color{red}{131} & 673 & 234 & 103 & 18\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\ 630 & 803 & \color{red}{746} & \color{red}{422} & 111\\ 537 & 699 & 497 & \color{red}{121}.. 2022. 9. 26.
728x90

티스토리툴바