본문 바로가기

백준144

[C/C++] 백준 #1755 숫자놀이(정렬) 이번 문제는 숫자를 단어로 바꾸었을 때, 사전순서로 정렬하는 문제죠. 제 경우에는 ord란 배열을 이용해서 순서를 정했습니다. 최대 숫자가 99이므로 두자리 숫자가 최대가 됩니다. 0은 zero로 가장 순서가 늦게 되겠죠. 그 순서대로 하면 아래의 표대로 됩니다. 다른 숫자에 같은 단어가 있을 수 없으므로 1이 가장 앞에 수이고, 10이 가장 뒤의 수로 놓았습니다. 가장 앞의 수는 8(eight)가 됩니다. 0 1 2 3 4 5 6 7 8 9 10 5 9 8 3 2 7 6 1 4 위의 표를 이용해서 cmp함수를 만들었습니다. 위의 표에서 제가 순서를 나타낼 때 0을 사용치 않은 것은 3과 38을 비교하기 위해서입니다. 0부터 시작했다면, 3과 38은 같은 값을 가지게 되었을겁니다. 수는 두자리 숫자인 경.. 2022. 10. 10.
[C/C++] 백준 #1753 최단경로(다익스트라) 이번 문제는 문제 자체가 다익스트라 알고리즘으로 푸는 문제입니다. 유향 그래프(directed graph)가 주어졌을 때, 시작점에서 출발해서, 다른 모든 노드들까지의 최단 경로를 찾는 것입니다. 정확하게 다익스트라 알고리즘입니다. 저는 일단 해시맵(unordered map)을 이용해서 인접리스트를 구성했습니다. 그렇게 했던 가장 큰 이유는 두개의 정점사이에 두개 이상의 간선이 존재할 수 있다는 조건때문이었죠. 물론 벡터(vector)를 이용한다고 해서 문제가 되지는 않습니다. 최단거리이므로, 알아서 최소값을 찾아서 갈테니까요. 이것은 필수라기보다는 선택이라고 보입니다. 우선순위큐는 힙(heap) 자료구조를 이용해서 구현하였습니다. 우선순위큐를 바로 사용해도 괜찮은 선택입니다. 제 경우에는 힙을 직접 쓰.. 2022. 10. 10.
[C/C++] 백준 #1748 수 이어 쓰기 1(수학) 수 이어 쓰기 문제는 N이 주어지면 1부터 N까지의 숫자를 그대로 이어썼을 때 몇자리 숫자가 될 것인지를 물어봅니다. 무한대의 수를 소수로 만들면, 이 수는 초월수가 된다는 것이 증명되었는데, 비슷한 개념이지만, 여기는 유한개의 수를 붙여 쓰는 것이고, 자릿수만 계산하면 되는 문제라 어려운 수학이라고 보기는 힘듭니다. 한자리 숫자는 9개가 있고, 두자리 숫자는 90개가 있고, 세자리 숫자는 900개가 있습니다. k자리숫자는 \( 9 \times 10^{k-1} \)개가 있게 됩니다. 이를 이용하면 이 문제를 쉽게 풀 수 있습니다. 예를 들어서 372까지의 숫자를 쓴다고 해보죠. 1) 9보다 큰 수이므로 9자리가 나옵니다. 2) 9를 빼면, 363이 되고 이 수는 90보다 크므로, 189가 됩니다. 3) .. 2022. 10. 9.
[C/C++] 백준 #1747 소수&팰린드롬(수학) 이번 문제는 n 이상의 수중에 가장 작은 소수이면서 팰린드롬이 되는 수를 찾는 문제입니다. 구현을 위한 핵심은 다음과 같습니다. 1) n의 앞부분 절반의 수를 구합니다. 예를 들어서 120의 경우라면 3자리 숫자에 12가 됩니다. 31과 같은 숫자는 2자리 수에 3이 됩니다. 2) 절반의 수를 이용해서 같은 자리수의 팰린드롬을 구합니다. 120의 경우에는 121이 팰린드롬 수가 됩니다. 31의 경우에는 33이 팰린드롬이 됩니다. 이 수가 n 이상의 수가 된다면, 통과이고, 그렇지 않다면 절반의 수에 1을 더합니다. 이 수는 반드시 n보다 큰 수가 되기 때문에 1을 더하는 것으로 충분합니다. 3) 그 수부터 시작해서 팰린드롬이 되는 수 중에 소수인 수를 찾습니다. 여기서 사실 알고리즘 효율을 위해서 맨 첫.. 2022. 10. 9.
[C/C++] 백준 #1744 수 묶기(탐욕 알고리즘) 이 문제는 탐욕 알고리즘으로 풀기에 괜찮은 문제입니다. 수열이 주어지면 그 수를 다른 수와 묶어서 곱한 후 더하거나 수 자체를 더하는 방법을 사용합니다. 한번 사용된 수는 다시 사용될 수 없습니다. 그리고 모든 수가 참여되어야 합니다. 이렇게 했을 때 최대의 합을 구하는 것이 문제입니다. 예를 들어서 ( 3, -2, 5, -7, 0 ) 이 있다고 한다면, (-2 * -7) + (3 * 5) + 0을 하면 가장 최대수를 얻게 됩니다. 원리는 간단합니다. 0 이하의 수와 1보다 큰 수들, 그리고 1의 갯수를 구합니다. \(1a = a\)이므로 1은 곱하기보다는 자기 자신으로 더하는 것이 더 큰 수가 됩니다. ( 2, 3, 5, 7 ) 이렇게 4개의 수가 있다면, 가장 큰 값을 얻기 위해서는 큰수끼리 곱해나가.. 2022. 10. 8.
[C/C++] 백준 #1743 음식물 피하기(너비우선탐색) 이번 문제는 섬의 개수 구하기라든지, 섬의 넓이 구하기 문제와 비슷한 유형으로 너비 우선 탐색(BFS)나 깊이 우선 탐색(DFS)를 이용해서 푸시면 됩니다. 구현 자체는 깊이 우선 탐색이 더 쉽습니다. 너비 우선 탐색은 일단 큐를 사용해야 하기때문에 구현이 조금 더 까다롭다고 볼 수 있습니다. 그에 비해서 깊이 우선 탐색을 이용하면 재귀함수만 이용하면 되죠. 구현도 훨씬 간단하고요. 제가 작성한 소스입니다. 소스는 참고로 봐주세요. //-------------------------------------------------------------------- // baekjoon #1743 - Avoid The Lakes // - by Aubrey Choi // - created at 2019-08-06 .. 2022. 10. 6.

티스토리툴바