목록Algorithm (111)
Sunrise
중복 순열, DP 문제입니다. 두 가지 풀이 방법이 있습니다. 1. [1, 2, 3] 배열의 중복 순열을 구해서 합을 확인합니다. 2. 경우의 수를 따지다가 점화식을 찾아서 DP(동적 계획법)으로 접근합니다. 첫 번째, 중복 순열을 구해서 합을 확인하는 방법입니다. - (1,1,2) (1,2,1) (2,1,1) 모두 다른 경우이므로 중복 순열을 구해야 합니다. - 중복 순열을 구하기 위해 [1, 2, 3] 배열을 선언합니다. 부분 배열을 위해 1~n 까지 for문을 돌립니다. - 중복 순열을 생성하는 itertools의 product를 이용하여 길이 i의 n_permu를 생성합니다. - 중복 순열 n_permu의 합이 n이 되면 count +1 from itertools import product T =..
조합 문제입니다. - n_list의 부분 수열은 1~N개의 수열 → for문 돌려서 combinations 으로 부분 수열의 조합 n_combi를 구합니다. - 조합 구한 후, 조합 요소들의 합이 S인 경우에만 count +1 from itertools import combinations N, S = map(int, input().split()) n_list = list(map(int, input().split())) count = 0 for i in range(1, N+1): n_combi = combinations(n_list, i) for x in n_combi: if sum(x) == S: count += 1 print(count)
조합 문제입니다. - 테스트 케이스를 받은 후, 첫번째 수 k를 pop해서 조합할 숫자들만 남겨놓습니다. - combinations(배열, 조합할 숫자 갯수) 를 이용하면 로또 조합을 쉽게 구할 수 있습니다. from itertools import combinations while(1): test_case = list(map(int, input().split())) if test_case[0] == 0: break k = test_case.pop(0) n_list = list(combinations(test_case, 6)) for x in n_list: print(*x) print()
덱 자료구조 문제입니다. D가 들어오면 배열의 첫번째 수를 버리고, R이 들어오면 배열을 뒤집는 기능을 해야 하므로 deque 자료구조를 사용합니다. - 입력을 받으면 먼저 rstrip()으로 문자열 맨 뒤 '\n'을 제거한 후, 슬라이싱 [1:-1]을 이용하여 앞 뒤 대괄호를 빼고, 나머지는 ','으로 나눠줍니다. - R이 들어온 경우, 배열 길이 n 범위가 10만, 명령 문자열 p의 길이가 10만이므로 배열 n에 대해 reverse를 하나하나 수행하면 시간초과가 납니다. R이 들어온 횟수 rev를 선언하여 짝수 개 들어오면 그대로, 홀수 개면 reverse를 수행합니다. - D가 들어온 경우, 배열이 비어있으면 error_flag, 그렇지 않다면 그 시점에 rev가 짝수인지 홀수인지 확인하여 버릴 숫..
구현 문제입니다. 소수 판별함수 is_prime_num 을 만들어서 소수 개수를 구합니다. 소수를 판별할 때 1은 소수가 아니므로 예외처리하고, 2 이상의 수에서 i로 나눠지는 경우 소수가 아니고 i로 나눠지지 않았다면 소수입니다. i의 범위를 2 ~ x까지 모두 확인하면 시간복잡도가 O(N)이지만, 약수는 항상 짝을 이루는 성질을 생각해보면 (1 2 4 8 16) x의 제곱근까지만 i로 나눠지는지 확인해서 시간복잡도를 O(√N)으로 줄일 수 있습니다. def is_prime_num(x): if x == 1: return False for i in range(2, int(pow(x, 0.5))+1): if x % i == 0: return False return True N = int(input()) n..
최대공약수, 최소공배수 문제입니다. 서로 다른 두 수의 최소공배수는 두 수의 곱을 최대공약수로 나눈 값이므로 최대공약수를 구하면 최소공배수는 쉽게 구할 수 있습니다. 유클리드 호제법에 의하면 서로 다른 두 수 a, b의 최대공약수는 b와 a%b의 최대공약수와 동일합니다. 이를 이용하여 계속 다른 두 수 b, a%b 를 구하다보면 최대공약수를 구할 수 있습니다. a, b = map(int, input().split()) def gcd(a, b): while b > 0: a, b = b, a % b return a def lcm(a, b): return a * b // gcd(a, b) print(gcd(a, b)) print(lcm(a, b))
덱 자료구조 문제입니다. - 출력물 리스트의 앞 요소를 빼기 쉽게 덱을 선언합니다. - 관심있는 타겟의 위치를 pos로 저장합니다. - while 문 안에서 타겟이 1순위로 출력 될 때까지 출력물 갯수를 count해주면 값을 구할 수 있습니다. from collections import deque import sys input = sys.stdin.readline T = int(input()) for _ in range(T): N, M = map(int, input().split()) queue = deque(list(map(int, input().split()))) # 앞에꺼 빼기 쉽게 덱 사용 count = 0 pos = M while 1: max_num = max(queue) # 최대값 갱신 fro..
문자열 문제입니다. 문자열 word를 입력 받은 후, 인덱스 i 를 늘려가면서 word[:i] == word[i:2*i]가 되는 경우를 찾으면 됩니다. T = int(input()) for test_case in range(1, T+1): word = input() i = 1 answer = 0 while(1): if word[:i] == word[i:2*i]: answer = len(word[:i]) break else: i += 1 print(f'#{test_case} {answer}')
2차원 배열 문제입니다. 두 가지 풀이 방법이 있습니다. 1. 2차원 정수 배열을 받고 각 행에 대하여 인덱스 범위를 조작하여 값을 더합니다. 2. 문자열로 받아 슬라이싱하여 값을 더합니다. 첫 번째, 2차원 정수 배열을 받은 후 인덱스를 조작하는 방법입니다. - farm에 2차원 정수 배열을 받고 start, end 인덱스를 선언합니다. - 이중 for문을 이용해 각 i행에서 start, end까지의 [ i ] [ j ] 요소를 더합니다. - 만약 i가 N의 중간보다 작으면 start, end를 1칸씩 확장 시키고 반대인 경우 1칸씩 축소시킵니다. T = int(input()) for test_case in range(1, T+1): N = int(input()) farm = [list(map(int,..