minimimi

문제출처] https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제요약 1차원 배열 누적합(PREFIX SUM) 알고리즘 문제 풀이 누적합의 기본 알고리즘은 N부터 M까지의 합을 (M까지의 합) - (N까지의 합) 을 이용하여 계산하는 것이다. 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline n,m = map(int, input().split()) number..

문제출처] https://www.acmicpc.net/problem/9184 문제요약 재귀 함수를 다이나믹 프로그래밍으로 구현하기 풀이 식이 모두 주어줘 있는 재귀 함수이므로 다이나믹 프로그래밍만 구현해주면 된다. 다이나믹 프로그래밍에서 가장 중요한 점은 "이미 계산했던 값은 다시 계산하지 않는다."이다. 그래서 dp라는 리스트를 만들어 계산했던 값은 저장해 주면 된다. dp 리스트를 선언할 때 인풋값의 범위가 -50 ~ 50 이므로 사이즈를 102로 하였다. 음수값이 들어오더라도 리스트의 뒤의 값부터 인덱싱을 하기 때문에 추가적인 코드를 짤 필요는 없다. 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline dp = [[[False for _..

문제출처] 문제요약 트리의 부모 찾기 (find parent) 문제 풀이 파이썬 딕셔너리를 이용한 그래프 구현 https://zero-rabbit.tistory.com/47 [백준] 11724 연결 요소의 개수 문제출처] https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양.. zero-rabbit.tistory.com find parent def find_parent(start): for i in tree[start]: if parents[i] == 0: parents[i] = start find_par..

문제출처] https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 같은 숫자를 포함하는 순열을 구해야 된다. 파이썬에서 그러한 함수를 지원하지 않기 때문에 일반 순열 함수를 이용하여 순열을 구한다음 set 자료형을 사용하여 중복을 제거해주었다. 주의할 점은 음수 나누기 양수를 할 때, 음수를 우선 양수로 변환한 다음 나눗셈을 한 뒤 다시 음수로 변화해줘야 된다는 점이다. 소스코드는 Pytho..

1. 순열 permutations(Iterable, r) # 순열 from itertools import permutations for i in permutations([1,2,3,4], 2): print(i, end=" ") # (1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3) 2. 조합 combinations(Iterable, r) # 조합 from itertools import combinations for i in combinations([1,2,3,4], 2): print(i, end=" ") # (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) 3. 중복순열 produc..

문제출처] https://www.acmicpc.net/problem/4949 문제요약 스택을 활용한 괄호 확인하기 문제 풀이 우선 문장이 주어지므로 문장에서 괄호만 리스트로 빼내야 된다. parentheses = ['(', ')'] square_brackets = ['[', ']'] while True: sentence = input() if sentence == '.': break brackets_list = [] for text in sentence: if text in parentheses or text in square_brackets: brackets_list.append(text) 반복문을 돌면서 독점(.)이 나올때까지 문장을 입력받는다. 괄호는 리스트로 미리 정의해 두었다. text가 괄호에..

문제출처] https://www.acmicpc.net/problem/1010 문제요약 중복을 포함하지 않는 증가, 감소 함수 구하기 (조합) 풀이 함수에서 단순 증가 혹은 단순 감소함수는 조합을 통해서 구할 수 있다. 조합에서 !(팩토리얼)이 필요하기에 함수 fact을 정의하였다. def fact(a,b): result = 1 for _ in range(b): result *= a a -= 1 return resulta를 b회까지 팩토리얼을 연산하는 함수이다. 만약 n!을 구하고 싶으면 fact(n,n)을 호출하면 된다. 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline n = int(input()) def fact(a,b): result ..

문제출처] https://www.acmicpc.net/problem/3036 문제요약 톱니바퀴가 맞물려 돌아갈 때 회전 수 구하는 문제 풀이 첫 번째 링과 각 링의 최대 공약수를 구하여 각각 나누어 준 후 첫 번째 링을 최대 공약수로 나눈 몫은 분자로 나머지 링을 최대 공약수를 나눈 몫은 분모로 취하면 된다. 최대 공약수를 구하는 방법은 2609번 최대공약수와 최소공배수 문제의 유클리드 호제법을 이용하면된다. 2609번문제풀이 링크] https://zero-rabbit.tistory.com/53 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline def gcd(a, b): # 무조건 a > b 유지 if a > b: pass else: a, ..