문제 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제 풀이 학생들은 K개의 알파벳을 배울 수 있다. 이때 N개의 단어 중 가장 많은 단어를 읽을 수 있는 경우의 수를 찾는 문제이다. 문제는 다음과 같은 경우를 확인하며 DFS로 풀면 쉽게 풀 수 있다. 언어는"anta"로 시작되고, "tica"로 끝나므로 배울 수 있는 단어 중, 'a', 'c', 'i', 'n', 't'를 배워야 하므로 5를 제외한다. 만약 K가 5보다 작다면, 읽을 수 있는 단어는 없다. K가 26이라면 모든 알파벳을 배울 수 ..
문제 7453번: 합이 0인 네 정수 문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주�� www.acmicpc.net 문제 풀이 앞 서 다룬 부분수열의 합 2, 두 배열의 합 합과 동일한 방식으로 푸는 문제이다. 한 줄에 A, B, C, D 4 쌍의 값이 있고 N개의 줄에 걸쳐 여러 쌍의 정수들이 주어진다. 앞의 문제들과 마찬가지로 한 번에 모든 경우를 구하는 것은 시간 초과가 발생한다. 따라서 A, B에 대한 부분합에 대한 카운트를 진행한 후, 0 - C, D의 부분합의 경우의 수를 정답으로 반영하면 ..
문제 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 문제 풀이 앞 서 다룬부분수열의 합 2와 유사한 문제이다. 부분수열의 합 2 문제는 입력되는 순열을 직접 절반으로 나누어 처리하여야 하지만, 해당 문제는 이미 A, B라는 배열을 나누어서 입력된다. 입력되는 배열을 합 중, T와 일치하는 경우가 있는지 판단하고 반환하는 문제이다. 부분수열의 합 2 문제와 동일한 로직을 통해 문제를 해결할 수 있다. 앞의 문제 처럼 배열 A에 대해 ..
문제 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이 앞서 다룬 부분수열의 합 문제에서 N의 범위가 40으로 증가한 문제이다. 따라서 기존의 풀이는 이 문제에 적용할 수 없다. 시간 초과가 발생하기 때문이다. 이 문제는 한 번에 N에 대한 부분수열을 모두 구하는 것이 아닌, 수열의 좌/우측으로 나누어 부분적으로 구한 후에 좌측의 작은 값 + 우측의 큰 값부터 점차적으로 계산해 S와 만족하는지 찾게 되면 시간 안에 문제를 해결할 수 있다. def dfs(idx,..
문제 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이 N개의 정수로 이루어진 수열에서 부분 수열의 합이 S가 되는 경우의 수를 찾는 문제이다. 이는 조합을 구하고 발생한 각 조합 중 합이 S를 만족하는지 찾으면 되는 문제이다. N의 범위가 크지 않으므로, 단순히 DFS를 사용하여 문제를 풀 수 있다. 코드 DFS를 이용한 문제 풀이 from sys import stdin def dfs(depth, subtotal): global answer if depth == ..
k8s: Pod
쿠버네티스의 오브젝트 중, Pod에 대해 알아보고자 한다. Pod를 이해하기 위해서는 쿠버네티스의 Pod 없이 컨테이너만 활용하여 서비스를 구성하고자 한다면 어떻게 해야 되는지 안다면, Pod의 필요성에 대해 명확히 이해할 수 있다. 어떤 경우에 필요 할까? 쿠버네티스 없이, 특정 서비스를 위해 컨테이너를 생성하고 관리하여야 한다고 생각해보자. 예를 들어 웹 서비스를 위해 하나의 컨테이너에는 웹과 관련된 어플리케이션을 하나의 컨테이너에는 해당 웹 어플레케이션 동작에 도움을 주는 어플리케이션을 실행하면 다음과 같은 상황이 발생한다. 네트워크, 볼륨, 네임스페이스 등 다양한 요소들을 컨테이너 별로 설정해주어야 한다. 설정이 끝난다고 해도 확장성을 생각한다면 새로운 문제에 직면하게 된다. 예를 들어, 지금은 ..
문제 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 www.acmicpc.net 문제 풀이 이 문제는 수들의 합 2, 부분합 문제에서 소수의 합으로 나타낼 수 있는 경우의 수를 찾는 문제이다. 연속합을 구하는 로직은 앞서 다룬 2 문제와 동일하며, 소수를 구하는 부분만 추가하면 쉽게 풀 수 있는 문제이다. 코드 from sys import stdin def is_prime(num): find = [] check = [True] * (num + 1) check[1..
문제 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 앞서 다룬 수들의 합 2와 유사한 문제이다. 다른 점이 있다면 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 것이다. 수들의 합 2와 마찬 가지로 사전에 누적합에 대한 값을 계산하고 시작, 끝 지점을 달리하여 순차적으로 탐색을 진행하면 경우의 수를 계산할 수 있다. 코드 from sys import stdin if __name__ == '__main__': answer = None start, end = 0, 1 n, s = ma..
