•알고리즘(Algorithm )/문제풀이

[백준9465&파이썬] DP를 풀때는 N이 1일때부터 하나씩 늘려가며 경우의 수를 따져보자.

# 문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net # 코드 import sys def solve() : n = int(sys.stdin.readline().strip()) stickers = list() for row in range(2): line = list(map(int, sys.stdin.readline().split())) stickers.append(line) # 현재 시점에서 대각선으로 한칸전과 두칸전 중 max값이 그 스티커의 최대값 for i in range(1,n) : if..

[백준1149&파이썬] DP를 사용할때 확정되는 값에 대한 명확한 근거를 찾자

# 문제 백준 1149 RGB 거리 파이썬 풀이 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net # 코드 ''' - 집을 조건에 맞게 칠할때, 최소 비용을 구해라 - 중점을 두는 것을, 현재 값에 중점을 두고 과거를 봐야한다. ''' import sys N = int(sys.stdin.readline().strip()) arr = list() # RGB로 칠하는 비용 for _ in range(N): line = list(map(int, sys.stdin.readline().split()..

[백준1991&파이썬] 파이썬에서 이진트리의 전위,중위,후위 간단히 수행해보자.

# 문제 백준 1991 트리 순회 파이썬 풀이 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net # 코드 import sys from collections import defaultdict N = int(sys.stdin.readline().strip()) graph = defaultdict(lambda : defaultdict(str)) LEFT = 1 RIGHT = -1 for _ in range(N) : parent, left, right = sys.stdin.readline().split() ..

[백준16953&파이썬] BFS를 이용해 1차원 탐색하기

# 문제 백준166953 A->B 파이썬 풀이 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net # 코드 ''' - BFS를 이용한 전형적인 풀이 같다. ''' import sys from collections import deque from collections import defaultdict A, B = map(int, sys.stdin.readline().split()) dq = deque() visit = defaultdict(bool) dq.append((A, 1)) visit[A] = True # 초기 방문 while len(dq) != 0: cur = dq.popleft() # ( node, cnt ) next1 = (cu..

[백준2407&파이썬] 조합의 경우의 수를 구할때는 수학 공식을 이용하자

# 문제 백준 2407 조합 파이썬 풀이 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net # 코드 import sys n,m = map(int,sys.stdin.readline().split()) arr = [i for i in range(1,n+1)] # nCm # n! / (n-r)! * r! # DP 로 팩토리얼을 구하자 mulit = 1 cnt = 2 dp = [-1] * 101 dp[1] = 1 while True : if cnt == n+1 : break dp[cnt] = dp[cnt-1]*cnt cnt+=1 print(dp[n] // ((dp[n-m]) * dp[m])) # math모듈을 이용해 쉽게 구할 수 있..

[백준5525&파이썬] 문자열을 탐색하는 방법(KMP를 시도했으나 실패..)

# 문제 백준 5525 IOIOI 파이썬 풀이 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net # 코드 ''' - 문제에서는 Pn이 몇개가 존재하는지 찾아야함 - Pn의 정의 -> N+1개의 I와 N개의 0 - KMP 알고리즘을 통해서 찾아보자 ( 문자열 검색을 위한 알고리즘 ) - Brute Force로 찾으면 O(MN)의 시간복잡도를 가진다. - KMP의 접두부, 접미부, 경계부에 대한 이해가 필요함 - 매칭에 실패했을때 얼마큼 점프해야하..