WakaraNai

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net Python import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a, b = map(int, input().split()) graph[a].append(b) graph[..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net Python import sys input = sys.stdin.readline n = int(input().rstrip()) arr = [0]+[int(input().rstrip()) for _ in range(n)] dp = [[arr[i], arr[i]] for i in range(n+1)] for i in range(2, n+1): dp[i][0] += dp[i-1][1] # 직전 계단은 건너 뛰어서 ..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net Python import sys n = int(sys.stdin.readline().rstrip()) ans = [] def hanoi(start,thor,dest,n): global ans if n 3 -> 2 hanoi(start, dest, thor, n-1) ans.append(str(start)+" "+str(dest)) #2 -> 1 -> 3 hanoi(thor, start..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net Python import sys input = sys.stdin.readline n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] def recur(r,c,size): global arr if size == 1: return str(arr[r][c]) size //= 2 ans = '' ..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net Python n = int(input()) dp = [0] dp.append(int(input())) # nn==1 cnt = 0 for n in range(1, n): k = list(map(int, input().split())) for r in range(1, len(k)+1): if r == 1: dp.append(k[r-1] + dp[cnt+r]) # (n-1, r)) #print(dp, dp[cnt+r]) elif r == len(k): dp.append(k..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net Python - 코드 정리 후 import sys input = sys.stdin.readline n = int(input()) arr = [list(map(int,input().split())) for _ in range(n)] def recur(r,c,size): global arr if size

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net Python 해당 섹션의 병합 여부를 판단하여 불가능 하면 무조건 4등분하기 import sys input = sys.stdin.readline N = int(input()) arr = [list(input().rstrip()) for _ in range(N)] def recur(r,c,size): global arr if size == 1: return arr[r][c] ans = ..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net Python import sys input = sys.stdin.readline tree = {} n = int(input().rstrip()) a, b, c = input().split() tree[a] = (b, c) root = a for _ in range(n-1): a, b, c = input().split() tree[a] = (b, c) def pre(now): print(now..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net Python import sys input = sys.stdin.readline n = int(input()) first = list(map(int, input().split())) dps, dpm = first, first for i in range(1, n): l, m, r = map(int, input().split()) nl, nm, nr = 0, 0, 0 nl = l + min(dps[0], dps[1..

BFS https://wakaranaiyo.tistory.com/254 다익스트라 https://wakaranaiyo.tistory.com/256 시간복잡도 : O(N^2) 다익스트라 + 우선순위큐(최소힙) https://wakaranaiyo.tistory.com/255 시간복잡도 : O(E logE) - E : 간선 개수 우선순위 큐를 이용하면 삽입 삭제 모두 O(logN) 소요