경북대학교 배준현교수님의 알고리즘실습 수업시간 실습과제를 이해하기 위한 포스팅입니다. 저의 코드는 정답이 아니며 참고만 해주시면 감사하겠습니다. 저도 배우는 입장이고 아직 대학생이므로, 간혹 설명을 잘못 드리는 경우가 있습니다. 댓글로 오류를 지적해주시면 감사하겠습니다. AP.2.1 - 시간 복잡도 분석 1 함수의 시간 복잡도를 분석하는 문제입니다. 시간 초과에 걸리지 않기 위해 반복문을 몇 번 반복하는지 시간복잡도(점화식)를 구해야 합니다. 그래서 input 값을 넣으면 바로 결과가 나올 수 있도록 계산만 하면 일일히 반복문을 돌지 않으므로 시간 초과에 걸리지 않습니다. #include using namespace std; typedef long long long_t; int main() { long_..

Problem https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net Comment 이 문제의 핵심은 두 가지입니다. 재귀 함수를 이용해 하노이의 탑 계산의 조건에 맞게 적절한 값 도출 원판 이동 횟수 계산 이 문제에서는 아래의 조건에 맞게 원판을 옮겨야 합니다. 한 번에 하나의 원판만 옮길 수 있음 맨 위에 있는 원판만 옮길 수 있음 크기가 작은 원판 위에 큰 원판이 쌓일 수 없음 중간의 막대를 임시적으로 이용할 수 있으나 위의 조건들을..

Problem https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net Comment 피보나치 수를 재귀 함수만 사용하게 된다면 시간 복잡도가 $O(2^n)$이 되어 시간 초과가 날 확률이 높습니다. 따라서 배열에 피보나치 함수들의 값을 저장해 실행 시간을 줄이는 것이 가장 중요합니다. Code #include int n, d[50] = { 0, 1 }; int fib(int n) { if (n == 0) return 0..

Problem https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net Comment 이 문제의 핵심은 두 가지입니다. 재귀 함수를 이용한 거듭 제곱 계산으로 시간 복잡도 성능 향상 모듈러 연산을 이용해 큰 수가 나오지 않도록 조정 거듭 제곱 계산을 재귀 함수로 짜는 방법은 아래 포스트에 게시되어 있으니 참고하시기 바랍니다. https://laurent.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-2-%EC%9E%AC%EA%B7%80-recursion#3.1.%20..

Problem https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net Comment 괄호가 맞지 않으면 no, 괄호가 맞으면 yes를 출력하는 프로그램입니다. 받은 문자열을 한 문자씩 읽어보면서 여는 괄호( '(' , '[' )는 스택(s)에 넣어 닫는 괄호( ')' , ']' )가 나올 때마다 스택(s)의 제일 위에 있는 값(s.top())과 비교하면 됩니다. Code Result Remark 프로그램에서 값을 받을 때 한 줄씩 받기 ..

Problem https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net Comment 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어집니다. 이제 순서대로 K번째 사람을 제거합니다(프로그램에서는 pop 한 다음 다시 push를 하지 않으면 됩니다.). N명의 사람이 모두 제거될 때까지 계속되기 때문에 모든 원소가 pop 될 때까지 반복하면 됩니다. Code Result

Problem https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net Comment 상근이가 개발한 프린터에서 돌고 있는 특정 문서의 프린터물 출력 순서를 구하는 문제입니다. 상근이가 개발한 프린터가 동작하는 알고리즘은 다음과 같습니다. 1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다..