본문 바로가기
반응형

Programming406

[C/C++] 백준 #2014 소수의 곱(우선 순위 큐) 우선 순위 큐와 힙(heap) 자료구조는 탐욕 알고리즘(greedy algorithm)에서 많이 쓰이는 자료구조입니다. 우선 순위 큐가 힙 자료구조를 이용해서 작성된다는 것은 이미 잘 알고 있겠죠. 그래서 삽입, 최소값(또는 최대값) 삭제가 모두 \(O(\log N)\) 시간복잡도를 가지고 있습니다. 이번 문제는 주어진 소인수로 이루어진 수들중 K번째로 작은 수를 고르는 문제입니다. 여러가지 방식을 생각해보았는데, 저는 우선 순위 큐를 이용해서 풀었습니다. 1) 주어진 소수를 우선 순위 큐에 넣습니다. 2) K번째 수가 나올 때까지 2-1) 우선 순위 큐에서 수를 빼냅니다. 2-2) 빼낸 수에 대해서 주어진 소수를 곱해서 우선 순위 큐에 넣습니다. 조금이라도 효율을 좋게 하기 위해서 우선 순위 큐의 저장.. 2023. 1. 17.
[C/C++] 백준 #2011 암호코드(동적 계획법) 영문 대문자로만 이루어진 암호가 있으면, 해당 영문자를 A는 1로 B는 2로 Z는 26으로 차례대로 숫자를 지정한다면, 숫자를 나열할 수 있습니다. 예를 들어서 BEAN은 B는 2, E는 5, A는 1, N은 14이므로 25114로 표현할 수 있죠. 하지만, Y = 25, K = 11, D = 4 이므로 YKD도 될 수 있죠. 숫자가 주어졌을 때, 그것을 영문자로 바꿀 수 있는 경우는 제한되어 있습니다. 일단 0을 제외한 한자리 숫자는 모두 영문으로 만들 수가 있겠죠. 두자리 숫자가 26을 초과한다면 이 경우에는 J 이상의 영문자로 만들 수가 없으므로 한자리 숫자로 해야 합니다. 그리고 바꿀 수 없는 경우도 있습니다. 304와 같은 숫자는 나올 수 있는 영문 단어가 없습니다. 30은 글자가 안 되고, 0.. 2023. 1. 15.
[C/C++] 백준 #2004 조합 0의 개수(수학) 조합을 계산할 때에는 보통 다음의 식을 사용합니다. \[ _nC_r = \frac{n!}{r!(n-r)!} \] 뒤의 0의 개수를 구할 때에는 10의 배수가 몇개나 생기는 가가 중요합니다. 그렇기 때문에 2의 소인수의 개수와 5의 소인수의 개수가 몇개인 가가 중요하게 됩니다. 일반적으로는 2의 소인수의 개수가 더 많지만, 꼭 그렇지는 않습니다. \(_5C_1\)의 경우라면 5의 소인수의 개수는 1개, 2의 소인수의 개수는 0개이니까요. 그래서 소인수를 카운팅할 때, 2의 소인수 개수와 5의 소인수 개수를 같이 카운팅해주어야 합니다. \(n!\)의 경우라면 뒤에 연속으로 나오는 0의 개수를 세기 위해서라면 5의 소인수의 개수를 세면 됩니다. 5로 계속 나눈 몫의 합을 구하면 뒤에 연속으로 나오는 0의 개수.. 2023. 1. 15.
[C/C++] 백준 #2003 수들의 합 2(두개의 포인터) 두개의 포인터는 연속된 구간을 나타낼 수 있는 두개의 인덱스를 유지하면서, 그 구간의 결과가 해가 되는지 검사하는 방법입니다. 현재 영역에서 영역이 커지면 결과도 커져야 하고, 영역이 작아지면 결과도 작아져야 합니다. 이 조건을 만족하지 않으면, 사실상 두개의 포인터를 이용할 경우가 별로 없습니다. 양수들의 구간의 합은 위의 조건에 부합합니다. [a .. b] 구간에서 구간이 하나 증가하면, 구간의 합은 늘어나게 됩니다. 또한 구간이 하나 줄어들면, 구간의 합은 줄어들게 됩니다. 이를 이용해서 연속된 구간의 합이 M이 되는 곳을 찾을 수 있습니다. 시간 복잡도는 \(O(N)\)입니다. 제가 작성한 소스입니다. //------------------------------------------------ //.. 2023. 1. 14.
[C/C++] 백준 #1991 트리순회(깊이 우선 탐색) 트리를 순회하는 방법은 크게 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있습니다. 깊이 우선 탐색은 스택(또는 재귀호출)을 이용하고 너비 우선 탐색은 큐를 사용하죠. 그런데, 깊이 우선 탐색의 경우에는 방문을 했다는 표시를 하는 방법에 따라서 전위(pre), 중위(in), 후위(post) 탐색으로 나눌 수 있습니다. 이번문제는 깊이 우선 탐색에서 전위, 중위, 후위 탐색의 결과를 출력하는 것입니다. 이 세가지 방법은 사실 기본적으로 호출하는 것은 똑같지만, 언제 방문 여부를 표시하는가에 따라서 다를 뿐입니다. 각각의 탐색 방법에 따라 함수를 따로 만드는 것이 시간상으로 더 효율적이겠지만, 저는 하나의 함수로 작성해보았습니다. 이 방법이 좋다는 것은 아니지만, 세가지 탐색 방법을 알아보기 좋게 .. 2023. 1. 13.
[C/C++] 백준 #1987 알파벳(깊이 우선 탐색) 이번 문제는 깊이 우선 탐색(DFS)를 이용해서 풀었습니다. 백트랙킹과도 같은 기법이긴 합니다. 백트랙킹 자체가 깊이 우선 탐색을 이용하여 푸는 것인만큼 딱히 구분을 지을 필요는 없어보입니다. 갈 수 있는 길이냐 아니냐를 따지기 위해서는 알파벳 마스크(Alphabet mask)를 사용합니다. 일반적인 깊이 우선 탐색은 방문했는지 여부를 따지게 되는 것과는 다릅니다. 알파벳은 오직 한번만 지나갈 수 있기 때문에, 이미 지나온 자리는 다시 방문할 수가 없습니다. 다음으로는 가장 짧은 경로가 아니라 가장 긴 경로를 찾는 것이기 때문에 모든 경로를 다 살펴보아야 합니다. 그러다보면 꽤 많은 경로를 검색하게 됩니다. 문제에서 행과 열의 개수가 상당히 적기 때문에 (\( 1 \ge R,~C \ge 20\)), 깊이.. 2023. 1. 12.
728x90

티스토리툴바