본문 바로가기

Programming456

[C/C++] 백준 #1761 정점들의 거리(최소 공통 조상) 트리에서 두 노드간 최소 거리를 구하는 방법은 여러가지가 있습니다. 가장 간단하게 생각할 수 있는 것은 깊이 우선 탐색(DFS) 이용하는 방법이 있겠죠. 하지만, 노드의 수가 많다면, 꽤 오랜 시간이 걸리겠지만, 크게 문제가 되지 않습니다. 노드의 개수가 N개라면, \(O(N)\) 알고리증으로 풀 수 있으니까요. 물론 재귀 호출의 깊이가 깊어지기 때문에 너비 우선 탐색(BFS)를 이용할 수도 있습니다. 하지만, 이번 문제는 단순하게 두 노드간의 거리를 한번 구하는 것이 아니고 M번 구하는 것입니다. 그러면, 알고리즘 효율이 \(O(NM)\)이 됩니다. 그렇기 때문에 보다 효율적인 알고리즘을 찾아야 합니다. 최소 공통 조상 알고리즘은 기본적으로 많은 질의(query)가 있는 경우 사용할 수 있습니다. 모든.. 2022. 10. 11.
[C/C++] 백준 #1759 암호 만들기(조합) 이번 문제는 조합을 이용하는 것입니다. 단지 조건이 좀 들어가 있습니다. 적어도 1개의 모음과 2개의 자음이 들어가야 합니다. 사실, 조합을 구한 다음에 모음의 개수를 세면, 그 외는 모두 자음이기때문에 손쉽게 풀 수 있습니다. 저는 재귀함수를 이용해서 풀었습니다. 모음의 개수를 따로 세어서 마지막에 검사를 했습니다. 재귀 함수를 사용하여 조합을 만들 수 있다면, 어렵지 않게 풀 수 있는 문제입니다. 암호의 길이가 길다면, 모음을 검사하는 비용이 클 수가 있기 때문에 주의가 필요하겠죠. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------------------- // baekjoon #1759 - Making password.. 2022. 10. 11.
[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.
728x90

티스토리툴바