본문 바로가기

Programming456

[C/C++] 백준 #1922 네트워크 연결(크루스칼) 컴퓨터 네트워크를 공용망에 연결하지 않고, 체인 형태로 연결할 때, 최소 비용으로 모든 컴퓨터를 다 연결하고자 합니다. 컴퓨터간 연결하는 비용이 제시되었을 때, 이를 이용해서 가장 최소 비용으로 컴퓨터간 연결을 모두 합니다. 대표적인 최소 간선 비용 트리(MST : Minimum Spanning Tree) 문제입니다. 최소 간선 비용 트리를 만드는 방법은 여러가지가 있지만, 보편적으로 많이 사용되는 것이 크루스칼 알고리즘과 프림 알고리즘입니다. 그 외에도 몇가지 더 있죠. 집합 개념을 사용해서 집합갠 최소 비용 간선을 선택할 수도 있고요. 크루스칼 알고리즘과 같이 간선 가중치를 모두 정렬한 후에 최소 비용 간선을 선택하면서 집합을 늘려가는 방법도 있습니다. 제 경우에는 크루스칼 알고리즘을 이용했습니다. .. 2022. 11. 9.
[C/C++] 백준 #1920 수 찾기(이진 탐색) 주어진 수열에서 M개의 데이터 중에 해당 수가 존재하는지 여부를 가리는 문제입니다. 집합 자료를 이용하면 손쉽게 구현할 수 있고, 또는 정렬 후 이진 탐색을 통해서도 이루어질 수 있습니다. 해시 집합 자료를 이용하면, 이론적으로 \(O(N+M)\)의 효율로 구현될 수 있습니다. 이진트리 집합 자료인 경우에는 \(O((N+M) \log N)\)이 걸립니다. \( \log N \) 자체가 큰 로드가 아니므로 사실상 집합 자료를 사용해도 되고, 정렬 후 이진 탐색을 사용해도 됩니다. 저는 정렬 후 이진 탐색을 이용해서 구현했습니다. 알고리즘 효율은 \(O( (N+M) \log N )\)입니다. 제가 작성한 소스입니다. //------------------------------------------------ .. 2022. 11. 8.
[C/C++] 백준 #1918 후위 표기식(스택) 후위 연산식, 후위 표기식은 모두 스택을 이용해서 문제를 풀 수 있습니다. 여기서는 중위 연산식을 후위 연산식으로 바꾸는 것인데요. 사칙연산자와 괄호만 사용하고 있어서 구현 자체가 어렵지는 않습니다. 단지 주의할 것은 연산자 우선순위입니다. 연산자 우선순위는 테이블을 이용하기도 하지만, 저는 그냥 조건문으로 해결하였습니다. 연산자가 많은 경우에는 테이블을 이용하는 것이 더 유리하겠죠. 중위식에서 후위식으로 바꾸기 위해서는 토큰을 다음과 같이 나누어야 합니다. +, -, *, /, (, ), 숫자로 나눌 수 있습니다. 1) 연산자를 저장할 스택을 마련합니다. 2) + - 연산자의 경우 스택이 비거나 ( 기호가 나올 때까지 연산자를 끄집어내어 출력합니다. 해당 연산자는 스택에 넣습니다. 3) * / 연산자의.. 2022. 11. 8.
[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.
728x90

티스토리툴바