본문 바로가기
반응형

Programming401

[C/C++] 백준 #1758 알바생 강호(탐욕) 이번 문제는 팁을 최대로 받기 위해서 적절한 전략을 세울 필요가 있습니다. 사실 모두 꽤 많은 팁을 생각했다면, 어떤 순으로 커피를 전달해도 결과는 같습니다. 예를 들어서 3명의 손님이 10원, 20원, 30원을 생각했다면, 순서와 관계가 없이 받는 팁은 같습니다. 알바생 강호는 10원, 19원, 28원을 받게 되겠죠. 순서가 바뀌어도 (10원 29원, 18원), (20원, 9원, 28원), (20원, 29원, 8원) 형태가 되어서 일정한 금액을 받습니다. 문제의 핵심은 음수를 많이 만들어서 등수에 의해서 빠지는 수를 적게 하는 것입니다. 그러면, 정렬을 해서, 적은 금액의 팁을 생각한 것들의 등수를 뒤로 밀어놓음으로써, 가능한 많은 음수를 만드는 것입니다. 예를 들어서 3명의 손님이 1원, 2원, 3원.. 2022. 10. 11.
[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++] 프로젝트 오일러 #82 path sum : three ways(다익스트라) 이번 문제는 앞에 #81 문제와 동일하게 경로의 합을 구하는데 있어서 최소의 경로값을 잦는 것입니다. 앞의 문제가 two ways였던 것에 비해서 이번 것은 three ways입니다. 프로젝트 오일러 문제들 초창기가 제가 알고리즘 문제들 풀기 시작한 초기였던 점을 생각했을 때, 지금 보면 유치하기 짝이 없네요. 일단 힙구조를 사용하지도 않고 짰고, 삽입정렬을 이용해서 짰네요. 뭐 삽입정렬을 한다고 한다면, \(O(N^2)\) 알고리즘이었다는 것이죠. 이것 작성할 때만 해도 STL 사용도 안 했을 때이니까요. 우선순위 큐를 사용하면 해결되었을텐데요. 행렬이 크기 않았기 때문에 풀 수 있던 것이죠. 동적 계획법으로 풀 수도 있습니다. 하지만 사이클이 있기때문에 반복을 많이 해야 안정된 값이 나오게 됩니다. .. 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.
728x90

티스토리툴바