효과는 굉장했다!

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 SOLUTION import sys N = int(sys.stdin.readline()) RGB_cost = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] for i in range(1,N): # 이전 집 색깔과 겹치지 않는 것이 Key Point RGB_cost[i][0] = min(RGB_cost[i-1][1], RGB_cost[i-1..

15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 알고리즘 분류 백트래킹 SOLUTION import sys from itertools import combinations_with_replacement N, M = map(int, sys.stdin.readline().split()) N_list = list(map(int, sys.stdin.readline().split())) N_list.sort() # 중복되는 수열 출력을 방지하기 위해 set() 이용 combi_w_list = sorted(set(lis..

15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 알고리즘 분류 백트래킹 SOLUTION import sys from itertools import permutations N, M = map(int, sys.stdin.readline().split()) N_list = list(map(int, sys.stdin.readline().split())) # 중복되는 수열 출력을 방지하기 위해 set() 이용 permu = sorted(set(list(permutations(N_list, M)))) for i in p..

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: ..

선형 리스트[Linear List] 란? 데이터를 일정한 순서로 나열한 자료구조로 '순차 리스트' 라고도 한다. 즉, 선형 리스트는 입력으로 들어온 데이터들이 순차적으로 저장되는 형식이라고 볼 수 있다. 가장 기본적으로 배열(리스트)을/를 통해 구현한다. 선형 리스트의 장점 데이터가 실제 위치 순서로 구성되기 때문에 데이터를 파악하기 쉽다. (직관적이다) 구현이 간단하다. 인덱스를 이용해 데이터에 접근할 수 있으므로 접근성이 좋다. 선형 리스트의 단점 삽입/삭제 시 시간이 오래걸린다. (O(N)의 속도를 가진다) 배열을 만들 때 데이터의 크기가 고정적이기 때문에 낭비하는 공간이 생길 수 있다. 선형 리스트의 간단한 구현 delivery = ["치킨", "피자", "햄버거", "None", "None"] ..

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 ..