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

[백준17070&파이썬] State를 통해서 파이프의 이동방향을 다각화 하기

# 문제 백준 17070 파이프 옮기기1 파이썬 풀이 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net # 코드 import sys def print2D(arr) : for i in arr : print(i) N = int(sys.stdin.readline().strip()) board = list() for _ in range(N) : line = list(map(int,sys.stdin.readline().split())) board.append(line) # 파이프를 계속 바꿔가면서..

[백준12865&파이썬] 0-1 냅색문제(배낭문제)

# 문제 백준 12865 평범한 배낭 파이썬 풀이 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net # 코드 import sys def print2D(arr) : for i in arr : print(i) return N,K = map(int,sys.stdin.readline().split()) arr = list() for _ in range(N) : weight, value = map(int,sys.stdin.readline().split())..

[백준11054&파이썬] dp를 두번 이용하여 문제를 해결하자

# 문제 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net # 코드 import sys n = int(sys.stdin.readline().strip()) arr = list(map(int,sys.stdin.readline().split())) # print(arr) # 왼쪽부터 증가하는 수열을 구한다. dpL = [1] * n for pivot in range(n) : for i in range(pivot) : if arr[i] < arr[pivot] : dpL[pivot] = max(dpL[pivot], dpL[i] + 1) #..

[백준11053&파이썬] DP를 이용하여 반복문을 하나 줄일 수 있다.

# 문제 백준11053 가장 긴 증가하는 부분 수열 파이썬 풀이 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net # 코드 ''' - 수열의 크기 N이 최대 1,000이기 때문에 O(N^2)을 이용한 완전탐색을 하더라도 1,000,000 ( 약 백만 ) 안에 구할 수 있기 때문에 1초안에 구할 수 있을 것으로 보인다. ''' import sys N = int(sys.stdin.readline().strip()) arr = list(ma..

[백준2096&파이썬] DP와 슬라이딩 윈도우를 이용하기

# 문제 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net # 코드 import sys N = int(sys.stdin.readline().strip()) mmin = [0,0,0] mmax = [0,0,0] for _ in range(N): cur = list(map(int, sys.stdin.readline().split())) mmin = [cur[0] + min(mmin[:2]) , cur[1] + min(mmin), cur[2] + min(mmin[1:])] mmax = [cur[0] + max(mmax[:2]) ,..

[백준5639&파이썬] BST의 preorder를 postorder로 변환하는 방법

# 문제 백준 5639 이진 검색 트리 파이썬 풀이 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net # 코드 import sys sys.setrecursionlimit(10**6) def printSolve(arr) : for i in arr : print(i) # 몇개인지 모르는걸 입력받을때는 아래와 같이 수행하자. bst = list() while True : try : bst.append(int(sys.stdin.readline().strip())) except : break l = 0 r ..