본문 바로가기

Programming456

#1517 버블 소트 버블 소트는 정렬에서 가장 재미있는 정렬 방식이자, 사실 실생활에서도 많이 이루어지는 정렬 방식이죠. 이웃하는 것끼리 크기를 비교해서 위치가 잘못되었으면 서로 교환을 하는 방식입니다. 대략 해당되는 알고리즘을 코드로 표현하면 다음과 같습니다. function Bubble(a, from, to): for i in (to, from+1, -1): for j in (from, i-1): if a[j] > a[j+1]: swap(a, j, j+1) 위의 알고리즘에서 swap하는 횟수가 몇번인가를 구하는 것이 이번 문제죠. 이 문제를 풀기 위해서 swap 횟수는 몇번 일어날 것인지 알아볼께요. 3, 5, 1, 2, 4 라는 수열이 있습니다. 3 5 1 2 4 이 수열이 버블 정렬에 의해서 swap이 발생하는 과정.. 2022. 8. 23.
[C/C++] 백준 #1516 게임 개발(위상 정렬) 게임 개발 문제는 위상정렬(Topology sort)를 사용해서 풀 수 있는 문제입니다. https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 건물을 짓기 위해서 필요한 건물이 있게 되는데요. 이 필요한 건물을 위상으로 생각하면 됩니다. 건물을 짓는데 걸리는 시간이 있는데, 이것은 여러개의 입력 간선이 있다면, 그 입력 간선중 가장 긴 시간이 소요된 것으로 시간을 적으면 되죠. 기존의 위상정렬이 순서대로 나열하는 것이었다면, 여기서는 입력.. 2022. 8. 23.
#1509 팰린드롬 분할 팰린드롬 분할은 주어진 문자열에 팰린드롬이 되는 단어들로 나눌 때 나오는 팰린드롬의 개수가 최소가 되는 수를 계산합니다. 맞힌 사람들의 수행시간을 보니, 제 알고리즘은 그다지 좋지는 않습니다. 제 알고리즘은 \(O(N^3)\)인데, 이보다 적게 계산할 수 있는 방법이 있겠죠. 일단 기본적인 생각은 앞에서부터 n개의 글자에 대한 팰린드롬 분할의 최소 개수를 구합니다. 이것을 \(dp_n\)이라고 한다면, 1개의 글자는 그 자체로 팰린드롬이니, \[ dp_0 = 0, dp_1 = 1 \] 이 됩니다. \[ dp_{n+1} = min_{i = 0,...,n-1}(dp_{i} + 1~ if~ s[i:n]~is~pallindrome) \] 이 방식대로 구현한 프로그램은 아래와 같습니다. 좀 더 효율적인 프로그램을.. 2022. 8. 22.
#1504 특정한 최단 경로 특정한 최단 경로는 중간에 두군데의 지점을 반드시 통과하는 경로중 최단 경로를 찾아라하는 문제입니다. 중간에 두군데의 지점을 반드시 통과하기 위해서는 [시작]-[지점1]-[지점2]-[끝]을 가는 경로와 [시작]-[지점2]-[지점1]-[끝]을 가는 경로중 거리가 짧은 것을 선택하시면 됩니다. 기본적인 알고리즘은 다익스트라(Dijkstra)의 변형입니다. 다익스트라 변형은 도착지점이 큐에서 나오면, 더이상 계산하지 않도록 하는 것입니다. 무방향 그래프이므로 [지점1]-[지점2]와 [지점2]-[지점1]은 같은 값입니다. 제가 구현한 소스입니다. 소스는 참조용으로만 봐주세요. //--------------------------------------------------------------------------.. 2022. 8. 22.
#1494 절대값 수열 절대값 수열 문제는 전체적으로 감소하는 수열의 특징을 이용하시면 됩니다. 일반적으로 비율로 줄어드는 수열의 경우에는 그 비율이 \(1/\varphi\)인 경우 가장 오래 갈 수 있습니다. 절대값 수열도 크게 다르지 않기 때문에, 가장 긴 수열을 얻기 위해서는 \(1/\varphi\) 비율에 가까워야 합니다. 정수에서는 1618:1000 정도의 비율입니다. 이 문제는 Platinum I 문제이지만, 수열 법칙을 조금 이해하시면 풀 수 있습니다. 60과 1로 시작하는 수열을 생각해보면, 60, 1, 59, 58, 1, 57, 56, 1, 55, 54, 1, ..., 2, 1, 1, 0, 1, 1, 0, .... 형태로 전체적으로 감소하는 수열이 됩니다. 이 중 두번째 값인 1이 여러번 반복하게 되는데, 이 .. 2022. 8. 22.
#1493 박스 채우기 박스 채우기는 일견 어려워 보이지만, 채워야할 큐브들의 2의 멱승길이를 가지는 정육면체라는 것에 착안하면 어렵지 않게 풀릴 수 있습니다. 예를 들어서 길이 2인 공간은 길이 1인 정육면체 큐브 8개로 채울 수 있죠. 저는 이 문제를 풀 때, 가장 큰 큐브부터 시작해서 작은 큐브로 채우는 것을 생각했습니다. 채울 수 있는 박스들의 최대 크기는 \(2^{19}\)이므로 이 크기의 큐브가 몇개 필요한지 우선 계산을 합니다. 이게 0개이면 다음 크기로 가겠죠. 일단 큰 큐브로 채우고 나면, 남아있는 부분들이 자잘하게 생기는데, 이 부분들이 총 7 부분이라고 생각을 했습니다. 그리고 같은 함수로 큐브 크기를 한단계 낮추어서 채우도록 합니다. 그리고 필요한 큐브의 갯수를 v[] 배열에 담아두고, 주어진 큐브의 배열.. 2022. 8. 21.
728x90

티스토리툴바