https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 기본적으로 가르쳐야할 알파벳은 남극의 기본문법인 "a", "c", "i", "t", "n" 총 5개이다. (위의 5개의 알파벳을 가르치지 않으면 어떠한 단어도 읽을 수 없다.) combinations로 조합을 통해 추가로 가르칠 알파벳을 골라주었다. 이를 통해서 완전탐색으로 단어를 읽을 수 있는지 없는지 확인해주었다. 시간초과 문제로 인해 PyPy3로 제출해주었습니다. 코드(PyPy3..

https://www.acmicpc.net/problem/7511 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net 풀이 기존 bfs 알고리즘을 사용할 시에 시간초과가 일어난다. 주어지는 유저의 수가 n^6까지 주어지기 때문이다. 그래서 분리 집합 알고리즘을 이용해서 답을 구해주었습니다. bfs를 사용하게 되면 확인해야하는 친구 관계의 개수만큼 bfs가 돌아가기에 매우 비효율적입니다. 그러나 분리집합을 사용하게 되면 연결된 최상위 노드만이 저장된 리스트를 비교함으로 효율적으로 ..

https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 풀이 이분탐색 방법을 이용해서 풀어주어도 괜찮겠지만, 집합을 이용해서 문제를 풀어주었습니다. 코드 # 2776번 암기왕 t = int(input()) for _ in range(t): _ = int(input()) note_1 = set(input().split()) _ = int(input()) note_2 = input().split() for i in note_2: if i in note_1: p..

https://www.acmicpc.net/problem/1788 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 통해서 문제를 풀어주었습니다. 코드 # 1788번 피보나치 수의 확장 n = int(input()) dp = [0, 1, 1] for i in range(3, abs(n)+1): dp.append((dp[i-2] + dp[i-1])%1000000000) if n > 0: print(1, dp[-1], sep="\n") elif n < 0:..

https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이 다이나믹 프로그래밍으로 피보나치 수를 구해주었습니다. 코드 # 10826번 피보나치 수 4 n = int(input()) dp = [0, 1] for i in range(2, n+1): dp.append(dp[i-2] + dp[i-1]) print(dp[n]) 출력결과

https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 풀이 피보나치의 함수가 얼마나 호출되는지에 대한 계산을 요구한다. 그래서 dp테이블을 만들어서 n이 0~2까지의 함수 호출 횟수를 넣어준 뒤 다이나믹 프로그래밍을 통해서 n이 원하는 답을 구해주었습니다. 코드 # 17175번 피보나치는 지겨웡~ n = int(input()) dp = [1,1,3] for i in range(3, n+1): dp.append((dp[i-1] + dp[i-2] + 1..

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 배낭 알고리즘을 이용해서 풀어줄 수 있는 문제이다. solved.ac 기준으로 class5를 달성하기 위해서 거쳐가야하는 문제 중 하나이다. 참고로 배낭 알고리즘은 Dp 알고리즘이기에 이 문제를 풀기 이전에 간단한 Dp문제를 풀고 오기를 바란다. 이 문제는 새로운 B앱을 활성화하기 위해 M메모리만큼 비활성화해야하는 앱들의 집합의 cost 최솟값을 찾는 문제이다. 따라서 기존의 배낭 알고리즘 문제에서..

Knapsack 문제와 Python으로의 구현 Knapsack 문제는 최적화 문제로 알려져 있으며, 가장 잘 알려진 결정론적 알고리즘 문제 중 하나입니다. 다양한 변형이 있지만, 여기서는 가장 대표적인 0-1 knapsack 문제에 대해 설명하겠습니다. 문제 설명: 주어진 물건들과 각 물건의 가치 및 무게, 그리고 일정한 무게를 수용할 수 있는 가방이 있을 때, 가방에 넣을 수 있는 물건들의 가치의 합을 최대화하는 문제입니다. 수식으로 표현하면: n개의 물건이 있고, i번째 물건의 무게는 w[i], 가치는 v[i]라 하자. 가방의 최대 무게는 W로 한정되어 있다. dp[i][j]를 i번째 물건까지 고려하고 가방의 무게 한도가 j일 때의 최대 가치로 정의한다. 본 문제를 풀기 위한 점화식: def knap..