본문 바로가기
반응형

백준144

[C/C++] 백준 #1916 최소비용 구하기(다익스트라) 이번 문제는 다익스트라 알고리즘을 이용해서 최소 경로를 구하는 문제입니다. 다익스트라 알고리즘은 Edsger W. Dijkstra(독일 : 데이크스트라 또는 다이크스트라)가 개발한 알고리즘입니다. 프림 알고리즘과 비슷하지만, 누적 간선 가중치의 값을 노드의 값으로 한다는 점이 다릅니다. DFS, 프림, 다익스트라, A* 알고리즘은 모두 비슷한 형태로 구성이 되어서 이해하면 쉽게 구현이 가능합니다. 다익스트라를 구현하는 방법은 거의 일정합니다. 다익스트라 기본 알고리즘은 시작정이 주어지고, 나머지 모든 노드들까지의 최소 경로값을 구하는 것이지만, 여기서는 도착점이 주어지기 때문에, 도착점이 선택되면, 그 부분에서 멈추도록 합니다. 이 문제에서는 저는 인접행렬과 힙을 이용해서 구현해보았습니다. 일반적으로는 .. 2022. 11. 6.
[C/C++] 백준 #1915 가장 큰 정사각형(동적 계획법) 이번 문제는 숫자가 써져있는 배열에서 1로만 채워진 가장 큰 정사각형을 찾으라는 문제입니다. 기본적인 알고리즘은 현재 셀을 포함한 가장 큰 정사각형을 찾는 것입니다. 현재 셀이 0이면 가장 큰 정사각형은 0입니다. 현재 셀이 1인 경우에만 가능하죠. A B C D 위의 그림에서 D에서 가장 큰 정사각형을 찾기 위해서는 D의 값이 0이면 0의 값이 됩니다. D의 값이 1일때만, ABCD 구역에서 D를 포함한 가장 큰 정사각형의 넓이를 구하는 것이죠. 첫번째는 A에서 가장 큰 정사각형입니다. 이 경우에는 D와 대각선으로 이웃한 셀은 1로 설정이 되어 있지않다면 0의 값을 가집니다. 다음으로는 AB에서 가장 큰 정사각형입니다. D의 위의 셀값은 1이 아니라면 0이겠죠. 다음으로는 AC에서 가장 큰 정사각형입니.. 2022. 11. 3.
[Python, C/C++] 백준 #1914 하노이 탑(재귀 함수) 재귀 함수를 배울 때, 가장 자주 사용하는 예제가 하노이 탑입니다. 하노이 탑의 이동 횟수는 다음의 점화식을 통해서 간단하게 구할 수 있습니다. \[ T(1) = 1 \] \[ T(N) = 2T(N-1) + 1 \] 위의 정화식을 풀면 \( T(N) = 2^N - 1 \) 이라는 것을 금방 풀 수 있습니다. 프로그램을 파이썬을 이용해서 작성해 보았습니다. 소스는 참고용으로 봐주세요. """ // baekjoon #1914 // - by Aubrey Choi // - created at 2019-07-23 """ def hanoi(n, a, b, c): if n == 0: return hanoi(n-1, a, c, b) print '%d %d'%(a,b) hanoi(n-1, c, b, a) a = raw_.. 2022. 11. 3.
[C/C++] 백준 #1913 달팽이(수학) 이번 문제는 C언어를 배우다보면 자주 나오는 달팽이 수열을 적는 것입니다. 일반적으로 왼쪽 위가 1의 자리이지만, 이번 수열은 가운데가 1의 자리입니다. 그래서 N은 홀수로 제한됩니다. 그냥 가운데부터 시작해서 차례차례 적어도 되고요. 숫자를 감소시키면서 거꾸로 적어나가도 됩니다. 저는 계산에 의해서 수열을 적었습니다. 굳이 이럴 이유는 하나도 없습니다. 성능상 이슈가 있는 것도 아니니까요. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------------ // baekjoon #1913 // - by Aubrey Choi // - created at 2019-07-22 //-----------------------------.. 2022. 11. 3.
[C/C++] 백준 #1912 연속합(탐욕 알고리즘) 주어진 수열에 대해서 연속합의 최대값을 찾는 것이 이번 문제입니다. 모두 다 양수라면 다 합친 것이 최대값이 될겁니다. 이와 비슷하게, 이번 알고리즘은 처음부터 차례대로 더해서 음수가 되지 않는 이상 양수 상태이면, 그것을 유지하는 것이 관건입니다. 알고리즘은 아주 간단합니다. 1. 현재의 합이 양수라면, 다음 수를 합한다. 2. 현재의 합이 음수이면, 현재의 합은 다음 수가 된다. 3. 현재의 합이 현재까지의 최대값보다 크다면, 최대값을 갱신한다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //-------------------------------------- // baekjoon #1912 - Sequential Sum // - by Aubrey Choi // - created at 20.. 2022. 11. 2.
[C/C++] 백준 #1904 01타일(피보나치 수열) 이번 문제는 복잡하게 썼지만, 결국 피보나치 수열을 구하는 문제입니다. 길이가 N인 01 타일의 이진수를 얻기 위해서는 길이가 N-1인 01 타일의 이진수에 1이 쓰인 타일을 붙이거나 길이가 N-2인 01 타일의 이진수에 00이 쓰인 타일을 붙여야 합니다. 이것을 식으로 표현하면, \[ d_{0} = 1 \] \[ d_{1} = 1 \] \[ d_{n} = d_{n-1} + d_{n-2} \] 점화식을 보면, 피보나치 수열임을 알 수 있습니다. 단지 시작점이 다른 피보나치 수열이죠. 피보나치 수열을 계산하는 방법은 단순하게 반복문을 돌리는 것이 편합니다. 재귀함수는 아주 시간이 많이 걸리고, 배열을 잡아서 하는 방법도 있지만, 전 그냥 편의상 두개의 변수만을 잡아서 사용했습니다. 제가 작성한 소스입니다... 2022. 11. 1.
728x90

티스토리툴바