본문 바로가기

Programming/BOJ277

[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.
[C/C++] 백준 #1981 배열에서 이동(이분탐색) 이번 문제는 보통의 그래프 문제와 다르게 경로상의 최저값과 최고값의 차이가 가장 적게 나오는 경로에서의 그 차이를 출력하는 문제입니다. 최저값과 최고값의 차이를 가지고 다루는 문제이기 때문에 다익스트라 알고리즘과 같은 탐욕 알고리즘 기반을 사용할 수가 없습니다. 제가 접근한 방법은 최고값과 최저값의 차이를 주어지고, 깊이우선 탐색(DFS)을 통해서, 시작점과 끝점까지 가는데, 그 차이를 가지는 경로가 있는지 확인하도록 했습니다. 최고값과 최저값의 차이는 이분탐색을 이용했습니다. 제일 먼저 모든 간선값들의 최저값과 최고값을 찾아서 그 차이값을 상한값으로 하였습니다. 이 값은 반드시 경로가 존재하게 되겠죠. 그리고 경로가 존재할 수 없는 값은 -1이 되겠죠. 모든 간선값이 같은 경우에는 0이 나와야 하니까요.. 2023. 1. 2.
[C/C++] 백준 #1978 소수 찾기(수학) 이번 문제는 N개의 수중에 소수인 수의 갯수를 찾는 것입니다. 소수의 범위가 크지 않기 때문에 사실 미리 소수를 구해도 되고, 에라토스테네스의 체를 이용해도 됩니다. 소수의 범위 K(이 문제에서는 1,000)라고 한다면, 에라토스테네스의 체를 사용하면 \(O(K \sqrt{K})\)의 시간안에 소수를 찾을 수가 있습니다. 또한 이것 자체가 소수인지 아닌지 판별하는 배열이 되기 때문에 소수의 개수를 구하는 것도 \(O(N)\) 시간안에 찾을 수 있습니다. 저는 에라토스테네스의 체가 아니라, 주어진 수마다 소수인지 판별을 했습니다. 이 경우 \(O(N \sqrt{K})\) 시간안에 찾을 수가 있습니다. 알고리즘 효율로 본다면, \(N 2022. 12. 20.
728x90

티스토리툴바