효과는 굉장했다!

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 트리 너비 우선 탐색 깊이 우선 탐색 SOLUTION import sys from collections import deque def dfs(): # 깊이 우선 탐색 활용 queue = deque([1]) # 트리의 루트가 1번이므로 1번 노트부터 시작 while queue: # 트리에 연결된 노드들을 전부 탐색 node = queue.popleft() for i in graph[node]: if not visited[i]: # 방문하지 않은 노드일때 # queue에 다시 넣어줘서 넣어준..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 SOLUTION import sys N = int(sys.stdin.readline()) N_list = list(map(int, sys.stdin.readline().split())) dp = [1] * N # Dynamic Programming 이용 for i in range(N): for j in range(i): if N_list[i] > N_l..

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 SOLUTION import sys import heapq def bfs(): visited = [[False] * N for _ in range(N)] shark_size = 2 exp = 0 ans = 0 while heap: cnt, x, y = heapq.heappop(heap) # 해당 칸의 물고기를 먹을 수 있을 때 if 0 < space[x][y] < shark_size: ..

15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 알고리즘 분류 백트래킹 SOLUTION import sys from itertools import combinations_with_replacement, repeat N, M = map(int, sys.stdin.readline().split()) num_list = sorted(map(int, sys.stdin.readline().split())) combi_w_replace = list(combinations_with_replacement(num_li..

15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 알고리즘 분류 백트래킹 SOLUTION import sys from itertools import permutations N, M = map(int, sys.stdin.readline().split()) num_list = list(map(int, sys.stdin.readline().split())) permu = list(permutations(num_list, M)) #permutations()함수 이용 permu.sort() for i in per..

15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 알고리즘 분류 백트래킹 SOLUTION import sys from itertools import combinations_with_replacement N, M = map(int, sys.stdin.readline().split()) # combinations_with_replacement(iterable, r) : r길이 튜플들, 정렬된 순서, 반복되는 요소 있음 combi_replace = list(combinations_with_replacement([i ..

15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 알고리즘 분류 백트래킹 SOLUTION import sys from itertools import combinations N, M = map(int, sys.stdin.readline().split()) combi = list(combinations([i for i in range(1,N+1)], M)) #combinations()함수 이용 for i in combi: print(*i) # *를 통해 unpacking

2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 알고리즘 분류 수학 다이나믹 프로그래밍 조합론 임의 정밀도 / 큰 수 연산 SOLUTION import sys from math import factorial n, m = map(int, sys.stdin.readline().split()) print((factorial(n) // factorial(n-m)) // factorial(m))

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 SOLUTION import sys from collections import deque def bfs(A, B): queue = deque([[A, ""]]) # queue에 초기값 A와 커맨드가 입력될 빈문자열을 넣는다. visited = [False] * 10000 # 범위는 10000까지, D,S,L,R 명령을 통해 나온 숫자들을 방문 처리 하기 위한 공간 visited[A] = True..

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 알고리즘 분류 구현 브루트포스 알고리즘 SOLUTION import sys def block(i, j): global answer for x in range(19): result = 0 for y in range(4): try: next_x = i + tetromino[x][y][0] # X좌표 next_y = j + tetromino[x][y][1] # Y좌표 result += paper[next_x][next_y] except IndexError: contin..