본문 바로가기

Programming455

[C/C++] 백준 #1965 상자넣기(가장 긴 증가하는 부분수열) 이번 문제는 가장 긴 증가하는 부분수열을 찾는 문제입니다. 문제의 알고리즘 힌트에는 동적 프로그래밍을 이용하라고 되어 있지만, 동적 계획법을 이용하는 경우에는 \(O(N^2)\) 알고리즘으로 풀어야 합니다. 그에 비해 약간의 정책을 이용해서 풀면 \(O(N \log N)\) 알고리즘으로 풀 수 있습니다. 가장 긴 증가하는 부분수열이라는 것은, 부분수열중에 단순 증가하는 수열을 찾는 것입니다. 예를 들어서, 1 6 2 5 7 3 5 6 이란 수열이 있습니다. 부분수열은 순서를 지키면서, 이 수열에서 몇개의 수를 뽑아내는 것을 말합니다. 예를 들어서 1 6 2 5 도 이 수열의 부분수열이고, 1 2 7 6도 이 수열의 부분수열이 됩니다. 그런데, 증가하는 부분수열은 앞의 숫자보다 뒤의 숫자가 큰 경우를 의미.. 2022. 12. 10.
[C/C++] 백준 #1963 소수 경로(너비 우선 탐색) 이번 문제는 소수중 한자리의 숫자만 다른 소수 경로를 찾는 문제입니다. 소수를 찾기 위해서 에라토스테네스의 체를 이용해도 되겠지만, 저는 미리 구한 4자리 소수 집합을 사용했습니다. 약간 편법일 수 있겠지만. 소수의 경로를 찾기 위해서 소수 후보를 찾는 것이 가장 힘듭니다. 일단 4자리 소수는 모두 홀수 소수이므로 갈 수 있는 경로는 31가지가 됩니다. 그것을 생각해서 한자리 숫자들을 바꾸면서 소수면 너비우선탐색 알고리즘으로 방문을 합니다. 그래서 목표하는 소수가 나오면 그때의 경로횟수가 답이 됩니다. 그런데, 모든 갈 수 있는 경로를 다 갔는데, 목표하는 소수가 나오지 않은 경우(queue가 비어있는 경우)에는 불가능하다고 출력을 내면 됩니다. 제가 작성한 소스입니다. //----------------.. 2022. 12. 9.
[C/C++] 백준 #1956 운동(플로이드 워샬) 이번 문제는 전형적인 플로이드 워샬 문제입니다. 플로이드 워샬 알고리즘은 음의 가중치가 있어도 문제를 풀 수 있고, 사이클을 찾아내는데에도 유용합니다. 하지만, 반복횟수가 많기 때문에, 노드의 개수가 많은 경우에는 좋지 않습니다. 알고리즘 시간복잡도가 \(O(V^3)\)입니다. 별도의 자료구조가 필요한 것도 아니기 때문에, 알고리즘만 이해하고 있다면, 손쉽게 구현할 수 있습니다. 제가 작성한 소스입니다. //------------------------------------------------ // baekjoon #1956 // - by Aubrey Choi // - created at 2019-11-16 //------------------------------------------------ #in.. 2022. 12. 9.
[C/C++] 백준 #1946 신입 사원(탐욕 기법) 신입사원의 채용 기준은 다른 모든 면접자들의 성적과 비교해서 하나라도 우수한 직원을 뽑는 것입니다. 문제의 뜻을 잘 이해하지 않으면 풀기 어려운 문제입니다. 성적은 두가지가 있는데, 이 두가지의 성적은 모두 동차 없이 순위가 정해집니다. N명의 면접자가 있다면, 1위부터 N위까지말이죠. 예를 들어서 3명의 면접자가 있고, 순위가 (1, 3) (2, 2) (3, 1) 이었다면, (1, 3)위 한 사람은 다른 두 직원에 비해서 첫번째 성적이 좋으므로 채용됩니다. (2, 2)한 면접자는 (1, 3) 면접자에 비해서는 두번째 시험성적이, (3, 1) 면접자에 비해서는 첫번째 시험성적이 좋아서 채용되죠. (3, 1) 면접자는 다른 두 면접자에 비해서 두번째 성적이 좋아서 채용됩니다. 이것을 저는 탐욕적 기법을 통.. 2022. 11. 29.
[C/C++] 백준 #1940 주몽(두개의 포인터) 두개의 조합에 의해서 M인 값을 얼마나 많이 찾을 수 있는 가에 대한 문제입니다. 예를 들어서, 2 7 4 1 5 3 이라는 재료가 주어지고, 조합해서 만들어야 하는 갑옷이 9의 값을 가져야 한다면, 먼저 정렬을 수행합니다. 1 2 3 4 5 7 그러면 두개의 합을 왼쪽편과 오른쪽편을 이용해서 구해보도록 합니다. 1) 1 과 7을 더하면 8이므로 숫자가 부족하므로 왼쪽을 1 증가시킵니다. 2) 2 와 7을 더하면 9이므로 답을 1 증가시키고, 왼쪽을 1 증가, 오른쪽을 1 감소합니다. 3) 3과 5를 더하면 8이므로, 왼쪽을 1 증가합니다. 4) 4와 5를 더하면 9이므로, 왼쪽은 1 증가, 오른쪽을 1 감소합니다. 5) 왼쪽의 포인터와 오른쪽 포인터가 교차했으므로 종료합니다. 그러면 총 2개의 갑옷을 .. 2022. 11. 29.
[C/C++] 백준 #1939 중량제한(그래프) 이번 문제는 프림이나 다익스트라와 비슷하게 동작하지만, 경로에 걸쳐있는 간선중, 최소값의 간선값이 해당 경로값이 됩니다. 이 경로값이 가장 큰 것을 찾는 문제입니다. 그래서 프림 알고리즘이나 다익스트라 알고리즘을 곧이 곧대로 사용할 수가 없습니다. 제가 사용한 탐욕 방법은 이것입니다. 0) 모든 노드의 값을 0으로 초기화합니다. 1) 출발지점에서 가장 큰 노드값을 가지고 있는 노드를 선택합니다. 2) 이동할 수 있는 모든 간선들을 적용하여 도착할 곳의 노드값을 결정합니다. 도착할 노드값은 현재보다 큰 경우 노드값을 저장하고, 우선순위큐에 해당 값을 넣습니다. 3) 도착지점이 가장 큰 노드값인 경우 종료합니다. 이 상태에서 선택할 수 있는 다른 노드값은 도착지점보다 적은 값이므로 의미가 없습니다. 제가 작.. 2022. 11. 19.

티스토리툴바