https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 나의 풀이 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해 보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드 1 코드 2 실행 횟수를 출력하자...
https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 나의 풀이 입력 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u 2 > 3 > 4 순서로 탐색하게 되며..
https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 나의 풀이 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있을 때, 원을 따라 양의 정수 K번째 사람을 제거한다. idx를 사용하여 원을 따라 k번째 사람을 제거하였고 idx가 len(nums) 보다 길어지면 % 연산을 하여 list의 양 끝을 이어서 문제를 해결함 import sys input_num = list(map(int, sys.stdin.readline().split())) nums = [i+1 for i in range(input_num[0])] idx = inpu..
https://www.acmicpc.net/problem/2164 나의 풀이 N장의 카드가 있을 때 카드는 1~N까지 정렬되어 있다. 맨 위의 카드를 버리고 그다음 맨 위 카드를 맨 아래로 옮길 때 마지막에 남은 카드는 무언인지 구하는 문제이다. 맨 위의 카드를 pop()하고 그다음 카드를 저장하여 아래에 넣어서 문제를 해결했다. import sys from collections import deque num = int(sys.stdin.readline()) card = deque([i+1 for i in range(num)]) while len(card) > 1: card.popleft() top_card = card.popleft() card.append(top_card) print(card[0]) ..
https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 나의 풀이 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 3 1 1 2 3 4 4 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4..
https://www.acmicpc.net/problem/25501 25501번: 재귀의 귀재 각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다. www.acmicpc.net 나의 풀이 문자열이 팰린드롬인지 판별하며, recursion이 얼마나 호출됐는지를 출력하는 문제 팰린드롬은 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때 같은 문자열을 말함 힌트 def recursion(s, l, r): if l >= r: return 1 elif s[l] != s[r]: return 0 else: return recursion(s, l+1, r-1) def isPalindrome(s): return recursion(s, 0, le..
https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 나의 풀이 피보나치 수는 0과 1로 시작하고 아래의 수식을 따른다. $$ F_{n} = F_{n-1} + F_{n-2} $$ n = 17일 때, 피보나치 수는 1597이다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 import sys num = int(sys.stdin.re..
https://www.acmicpc.net/problem/27433 27433번: 팩토리얼 2 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 나의 풀이 팩토리얼을 구현하는 문제이다. 팩토리얼은 \( N! \) 으로 표기하고 N보다 작거나 같은 모든 양의 정수의 곱이다. 반복문 for문을 n만큼 반복해 N보다 작거나 같은 모든 양의 정수를 곱해주어서 문제를 풀었음 import sys num = int(sys.stdin.readline()) answer = 1 for i in range(num): answer *= (i+1) print(answer) 재귀함수 num과 answer를 파라미터로 하여 num
