1. 문제 설명 https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 2. 아이디어 처음 알고리즘을 공부할 때 함수명을 dfs나 dijkstra처럼 쓰지 않는 사소한 반항을 했었는데, 그땐 그게 멋있어 보였나..덕분에 블로그에 정리하는데 무슨 의도로 썼었는지 헷갈린다. N의 범위가 고작 해봐야 20이하이므로 brute-force로 끝내버렸다. 모든 경우의 수를 조합하여 가능한 결과값..

1. 문제 설명 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 2. 아이디어 값의 범위가 크지 않아서 팩토리얼을 사용하면 간단하게 해결되는 문제다. 이항 계수가 무엇인지에 대한 설명은 따로 다루지 않겠다. 3. 코드 import sys sys.setrecursionlimit(100000) def factorial(nb): if (nb == 0 or nb == 1): return 1 return (nb * factorial(nb - 1)) def solution(): n, k = map(int, input().sp..

1. 문제 설명 https://www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 2. 아이디어 약간의 수학적 사고력을 필요로 하는 구현 문제다. 이 문제를 정직하게 풀려고 한다면 n만큼 수를 이어붙인 문자열에서 k번째 숫자를 찾아나서야 하는데 최악의 경우가 n == 100,000,000이고 k == 1,000,000,000이다. 데이터 1억개를 처리하는 시간이 대략 1초정도 걸리는데 이걸 다 이어붙이고, 문자열 1억 번째 위치를 찾으려 하면 당연히 타임에러가 발생한다. 이런 문제를 해결할 방..

1. 문제 설명 https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 2. 아이디어 당시에 이 문제를 풀 아이디어를 떠올리지 못해서 구글링을 통해 찾아낸 방법이 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)이었는데 애초에 다이나믹 알고리즘도 모르던 내가 이걸 100% 이해할 수 있었을리가 없다. 근데 난 왜 이걸로 문제를 풀어놨을까..? 분명한 건 구글링의 도움을 받아 문제를 풀었었다. 알고리즘에 대한 포스팅은 이후에 한 번에 정..