본문 바로가기

📚 전공 공부/알고리즘 해석 및 설계

(10)

[알고리즘] 그래프 - 최단거리 구하기(cpp) N개의 노드와 M개의 에지가 있는 그래프에서, 세 노드 s, a, t가 주어졌을 때 s에서 a를 반드시 지나서 t까지 도달하는 가장 짧은 거리를 구하는 프로그램을 작성하시오. 입력 표준 입력으로 입력을 받는다. 첫 줄에는 노드의 개수 N과 에지의 개수 M이 주어진다. 노드의 개수는 3 이상 100 이하이고, 에지의 개수는 0개 이상 N(N-1)개 이하이다. 두번째 줄에는 세 정수 s a t가 주어진다. 노드들은 0 이상 N 미만인 정수들로 표현되며, 이 세정수는 각각 시작 노드, 중간 노드, 도착 노드를 나타낸다. 세번째 줄부터 총 M줄에 에지 정보가 주어진다. 한 줄은 에지 하나에 대한 정보를 나타내며, 세 정수 U V W로 이루어진다. U는 에지의 시작 노드, V는 에지의 도착 노드, W는 에지의 가..

[알고리즘] 실패 함수 - 중복 최대 부분문자열(cpp) 영어 소문자로 이루어진 최대 길이 1,000인 문자열에서, 두 번 이상 나오면서 가장 긴 부분문자열의 길이를 출력하는 프로그램을 작성하시오. 예를 들어, banana의 경우 길이가 5인 부분 문자열은 banan, anana, 길이가 4인 부분 문자열은 bana, anan, nana, 길이가 3인 부분 문자열은 ban, ana, nan, ana이므로 ana가 2번 나오면서 가장 길이가 길다. 답은 따라서 이 경우 3이 된다. 힌트: 실패함수를 잘 이용해보자. 입력 표준 입력으로 입력을 받는다. 입력은 한 줄로 이루어지며, 최대 길이가 1,000인 영어 소문자로 이루어진 문자열이다. 출력 표준 출력으로 출력한다. 출력은 한 줄로 이루어지며, 입력된 문자열에서 두번 이상 나오면서 가장 길이가 긴 부분 문자열의..

[알고리즘] 문자열 다루기 - 로마숫자(cpp) 로마인들은 로마 숫자를 사용했다. 1은 I, 5는 V, 10은 X로 표현했고, I, V, X가 나타내는 문자열은 각 글자가 나타내는 수의 합이다. 예를 들어 XVI = 10 + 5 + 1 = 16이다. 단, IV는 4이고 IX는 9이다. 예를 들어 IVI = 4 + 1 = 5이다. 위의 예외에 추가로, IIV는 3이고 IIX는 8이라고 하자. 반드시 IIV, IIX는 3, 8이어야 한다. 즉 IIV는 1 + 1 + 5 = 7도 아니고, 1 + 4 = 5도 아니고, 반드시 3이어야 하는 것이다. 최대 길이가 10인 로마 숫자를 나타내는 문자열이 주어질 때 이 문자열이 나타내는 수를 출력하는 프로그램을 작성하시오. 입력 표준 입력으로 입력을 받는다. 최대 길이가 10인 문자열이 주어지고, 이 문자열은 I, ..

[알고리즘] DP - 계단 오르기(cpp) N단의 계단이 있고, 한번에 계단을 한 단 또는 두 단을 올라갈 수 있다고 하자. 최대 두 군데의 계단에는 장애물이 있어서 올라갈 수 없다. 이 때 N단까지 올라가는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오. 입력 표준입력으로 세 정수 N A B가 주어진다. N은 계단의 단수로, 1 이상 30 이하이다. A와 B는 장애물이 있는 계단의 위치이다. A와 B는 0 이상 N 이하인 수이며, A와 B가 같을 수 있다. A, B 값이 0이라면, 이는 장애물이 없다는 뜻이다. 예를 들어 N, A, B가 3, 0, 1이라고 주어지면 총 3단의 계단이 있고, 장애물은 1단에만 있다. 조금 더 생각해보면 N, A, B가 3, 1, 0으로 주어져도 같다는 것을 알 수 있다. 출력 표준출력으로 하나의 정수를 출력..

[알고리즘] Greedy algorithm - 이집트 나눗셈(cpp) 문제 이집트 나눗셈을 하는 프로그램을 작성하시오. 입력 p/q를 나타내는 두 정수 p, q가 사이에 공백을 하나 두고 주어진다. p는 1 이상 1,000 이하, q는 p+1 이상 2,000 이하인 정수 출력 수업 시간에 배운 이집트 나눗셈의 결과로 몇 개의 분수가 나오는지 출력한다. 예를 들어, 5/6은 1/2 + 1/3이므로 2개의 분수가 필요하다. 예제 입력 1 5 6 예제 출력 1 2 예제 입력 2 19 20 예제 출력 2 4 알고리즘 수업의 첫 과제였다. 이집트 나눗셈이란, 유리수 p/q가 주어지면 분자가 1인 분수들의 합으로 p/q를 표현하는 것이다. 예) 5/6 = 1/2 + 1/3 , 3/4 = 1/2 + 1/4 욕심쟁이 기법, 흔히 Greedy 알고리즘이라고 부르는 기법을 사용하여 풀이할 ..

[알고리즘] 정렬의 최적성 정렬의 최적성 앞에서 우리는 연속한 두 원소를 비교하는 방식으로 정렬하면, O(n2) 보다 좋은 시간 복잡도를 얻을 수 없다는 것을 보였다. 그 다음에 배운 정렬 방식인 퀵정렬, 병합정렬, 힙정렬 에서는 멀리 떨어진 두 원소를 비교하여 교환함으로써 이보다 빠른 시간 복잡도인 O(n log n) 시간을 얻을 수 있었다. 그렇다면 이제 우리가 다시 비슷한 질문을 해보자. O(n log n)보다 더 빠르게 정렬을 수행할 수 있겠는가? 정리. 두 원소를 비교하여 교환하는 방식으로는 O(n log n)보다 더 빠르게 정렬을 수행할 수 없다. 증명. 의사 결정 트리(decision tree)는 어떤 문제에 대해서 판단을 내리는 과정을 트리로 표현한 것이다. 루트는 문제를 풀기 위해서 처음 시작하는 지점이다. 루트를..

[알고리즘] 비교기반 정렬의 한계/비교에 기반하지 않은 정렬 비교 기반 정렬의 시간복잡도 한계 위 트리는 이진 트리이다. (크기 비교에 따른 두 가지 경우의 수) 트리의 리프 수 L은 n개의 값을 정렬하는 모든 경우를 포함한다. L = n! ≤ 2^h h ≥ log L = log(n!) (n/2)^(n/2) ≤ n! ≤ n^n log(n!) = Ω(n log n) 따라서 두 원소의 비교에 기반한 정렬 알고리즘은 Ω(n log n)보다 빠를 수 없다. 비교에 기반하지 않은 정렬 1 : 버킷 정렬 정렬될 데이터가 자릿수 개념이 있다면, 이를 이용한다. 예를 들어 정렬될 데이터가 택배 주소(~시 ~구 ~동)라면, 처음 위치(~시)만 보고도 데이터 분류가 가능. 분류한 데이터를 각각 정렬하고, 이를 이으면 정렬 완료 시간 복잡도 : Best = c개의 버킷으로 모든 원소..

[알고리즘] 비교 기반 정렬 문제 정렬 문제→ 여러 방법이 존재하며, 방법마다 특징이 다름 → 시간복잡도, 최적성에 대해 증명이 쉬움 → n개의 서로 다른 수가 주어질 떄, 이들을 이동하여 점점 커지게(오름차순) 또는 점점 작아지게(내림차순)으로 만드는 문제 가정 : 정렬한 데이터가 담긴 배열의 각 원소를 O(1)시간에 접근 가능하다. (= 데이터가 메인 메모리에 저장되어 있다.) 버블 정렬 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해가면서, 큰 수가 오른쪽으로 가도록 교환함. 맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해서 반복 정확성 : 자명함 시간 복잡도 : 처음 가장 큰 원소를 구할 때 n-1번 비교, 두 번째 큰 원소를 구할 때 n-2번 비교 (n-1) + (n-2) + … + 1 =..

이전 1 2 다음

티스토리툴바