Sunrise

누적 합 문제입니다. 문제 조건대로 그냥 구현하게 되면 M, N(i, j)이 10만까지이므로 시간복잡도 O(M*N) → 시간초과 납니다. N, M = map(int, input().split()) num = list(map(int, input().split())) for _ in range(M): answer = 0 i, j = map(int, input().split()) for idx in range(i, j+1): answer += num[idx-1] print(answer) 이러한 경우 받은 숫자들의 합을 누적시켜서 저장해놓는 prefix_sum 알고리즘이 유용합니다. prefix_sum 알고리즘을 사용하면 시간복잡도 O(M+N) 로 낮출 수 있습니다. 먼저 받은 숫자들을 하나씩 누적하여 pref..

백트래킹 문제입니다. https://sunshine0070.tistory.com/167?category=1021920 [백준][파이썬] 15650 N과 M (2) 백트래킹 문제입니다. https://sunshine0070.tistory.com/165?category=1021920 [백준][파이썬] 15649 N과 M (1) 백트래킹 문제입니다. 문제 조건을 보면, N = 4, M = 2 인 경우 (1 2) (1 3) (1 4) (2 1) (2 3) (2.. sunshine0070.tistory.com 15650 N과 M (2) 문제와 같은 방법으로 매개변수를 추가해주고, 자신과 같은 짝을 가진 수열도 포함합니다. def dfs(start): if len(s) == M: print(' '.join(map(..

백트래킹 문제입니다. https://sunshine0070.tistory.com/165?category=1021920 [백준][파이썬] 15649 N과 M (1) 백트래킹 문제입니다. 문제 조건을 보면, N = 4, M = 2 인 경우 (1 2) (1 3) (1 4) (2 1) (2 3) (2 4) (3 1) (3 2) (3 4) (4 1) (4 2) (4 3) 과 같이 자신을 제외한 나머지 숫자들과의 짝을 구해야 합니다. 이는.. sunshine0070.tistory.com 15649 N과 M (1) 문제에서는 11 22 33 과 같은 자신과 짝을 이룬 수열을 if i not in s로 제외했지만, 이번 문제에서는 포함합니다. def dfs(): if len(s) == M: print(' '.join(..

백트래킹 문제입니다. https://sunshine0070.tistory.com/165?category=1021920 [백준][파이썬] 15649 N과 M (1) 백트래킹 문제입니다. 문제 조건을 보면, N = 4, M = 2 인 경우 (1 2) (1 3) (1 4) (2 1) (2 3) (2 4) (3 1) (3 2) (3 4) (4 1) (4 2) (4 3) 과 같이 자신을 제외한 나머지 숫자들과의 짝을 구해야 합니다. 이는.. sunshine0070.tistory.com 15649 N과 M (1) 문제에서 순서에 관계없이 중복된 수열들은 제외해야 합니다. 15649 코드를 보면, def dfs(): if len(s) == M: print(' '.join(map(str, s))) return for ..

백트래킹 문제입니다. 문제 조건을 보면, N = 4, M = 2 인 경우 (1 2) (1 3) (1 4) (2 1) (2 3) (2 4) (3 1) (3 2) (3 4) (4 1) (4 2) (4 3) 과 같이 자신을 제외한 나머지 숫자들과의 짝을 구해야 합니다. 이는 반복문을 통해서도 풀 수 있지만, 만약 m이 커지면 반복문을 m번 중첩시키기 힘들기 때문에 백트래킹을 사용합니다. 백트래킹 문제는 DFS를 사용하여 풀 수 있는데, 일반적인 DFS와의 차이점은 가지치기를 하는 것입니다. 즉, 백트래킹은 DFS 처럼 모든 경우를 탐색하다가 조건에 따라 유망하지 않은 경우, 탐색을 중지하고 이전 노드로 돌아가 다른 경우를 탐색합니다. dfs 함수를 보면 두 가지 부분으로 구성됩니다. 1. len(s)가 M이 ..

재귀 문제입니다. 3가지 기둥이 있는 하노이 탑에서 최소 이동방법은, 1단계 - 가장 아래 원판 제외한 나머지를 1번에서 2번으로 옮기고 2단계 - 가장 아래 원판을 3번에 깔고 3단계 - 나머지 2번 원판을 차곡차곡 3번에 다시 쌓는 것입니다. 위의 이동하는 세 단계를 재귀함수로 풀어낼 수 있습니다. 재귀함수 hanoi_tower를 구성할 때, 문제 조건의 A, B를 출력하기 위해 원판 개수 n개, start 기둥, end 기둥을 파라미터로 정합니다. ex) n = 4 15 1 2 1 3 2 3 1 2 3 1 3 2 1 2 1 3 2 3 2 1 3 1 2 3 1 2 1 3 2 3 https://excalidraw.com/ 직접 옮겨보면서 이해하기 def hanoi_tower(n, start, end):..

정수론 및 조합론 문제입니다. n, m 을 받고 nCm 의 끝자리에 0의 개수가 얼마나 있는지 확인해야합니다. n, m 의 범위를 보면 20억까지이므로 팩토리얼로 구하면 시간초과가 납니다. 이러한 경우, nCm에 10이 얼만큼 들어있는지 확인하면 됩니다. 10은 2의 갯수, 5의 갯수를 구해서 적은 쪽만큼 만들어집니다. ex) 22222 555 팩토리얼 식에서 2의 갯수를 구하기 위해서는 2가 들어있는 규칙을 파악하면 됩니다. ex) n=9 8 = 2 2 2 6 = 2 3 4 = 2 2 2 = 2 이는 n//2 의 누적으로 2의 갯수를 구할 수 있습니다. n=9 → n//2 = 4 (two) n=4 → n//2 = 2 n=2 → n//2 = 1 n=0 break def two_count(n): two =..

정수론 및 조합론 문제입니다. 상의 3가지, 하의 2가지라 했을 때 조합을 따져보면, (상의X, 상의1, 상의2, 상의3), (하의X, 하의1, 하의2) 즉, (3+1) * (2+1) 라 할 수 있고 이중 둘 다 안입는 경우를 1가지 빼주면 됩니다. clothes 로 문자열을 받은 후 종류에 해당하는 clothes[1] 을 dict 에 넣어줍니다. dict 초기화 방법 → 없으면 1 있으면 += 1 (Counter 모듈도 사용가능) dict에 있는 모든 종류의 옷 갯수에 대해, +1 한 값을 곱해주고 마지막에 1 빼주면 답을 구할 수 있습니다. ''' (hx, h1, h2) (ex, e1) (2+1) * (1+1) - 1 ''' T = int(input()) for _ in range(T): closet..

정수론 및 조합론 문제입니다. 문제를 보면, m개의 다리에서 n개를 선택하고 순서에 따른 구별이 없으므로(순열이 아니라 조합) mCn 입니다. mCn 을 구하는 방법은 combinations로 조합을 구하고 길이를 구하는 방법, 수학식으로 계산하는 방법이 있습니다. combinations 사용하면 list로 받게 되는데 29C13 과 같은 큰 계산에서 시간 초과가 납니다. 따라서 수학식으로 계산하는 방법을 사용합니다. mCn = m! / n! (m-n)! from itertools import combinations import math T = int(input()) for _ in range(T): n, m = map(int, input().split()) # m_list = [i+1 for i in ..

정수론 및 조합론 문제입니다. n, k 의 이항 계수는 n! / (n-k)! k! 입니다. factorial은 직접 구현할 수도 있고, math 모듈에서 꺼내와도 됩니다. 실행시간 차이는 거의 없습니다. # def factorial(x): # a = 1 # for i in range(1, x+1): # a *= i # return a import math n, k = map(int, input().split()) answer = math.factorial(n) // (math.factorial(k) * math.factorial(n-k)) # answer = factorial(n) // (factorial(k) * factorial(n-k)) print(answer)