is Upgrading _ is Upgrading _

정올 1060: 최소비용신장트리 풀이 Question 문제 링크 Hint Prime 알고리즘 첫 노드에서 연결된 간선 중 가장 짧은 간선을 선택한다. 이제 연결된 노드들 중, 2개의 노드에서 다른 노드로 연결된 간선 중 가장 짧은 간선을 선택한다. 이를 반복한다. Answer (Python) # Input node = list(range(1, int(input()))) board = [] for i in node: board.append([int(x) for x in input().split(' ')]) connected = [0] result = 0 while len(node) > 0: min_vertex = 100001 min_node = -1 for n in connected: for o in no..

정올 1335: 색종이 만들기 풀이 Question 문제 링크 Hint 각 종이를 나타내는 Class 를 하나 만들고, 같은 색으로 차있으면 큐에서 빼고, 같은 색으로 차있지 않으면 4개의 Class 로 나눠서 큐에 넣고 끝까지 반복한다. Answer (Python) import queue def check_complete(board): idx = board[0][0] n = len(board) for i in range(n): for j in range(n): if board[i][j] != idx: return False return True def devide_board(board): n = len(board) m = int(n/2) b1, b2, b3, b4 = [], [], [], [] for ..

정올 1077: 배낭채우기 풀이 Question 문제링크 Hint Dynamic 알고리즘으로, 가방무게가 1~W 일 때 까지를 순차적으로 구한다. Answer (Python) # Sample input # N, W = 4, 14 # J = [[2, 40], [5, 110], [10, 220], [3, 50]] # Input N, W = map(int, input().split(' ')) J = [] for i in range(N): J.append([int(x) for x in input().split(' ')]) # Maximum cost that can contain in the bag # C[x]: maximum cost that x weight can have C = [] # Calculate m..

Question 문제 링크 How BFS 알고리즘으로 한다. DFS 로 하면 시간 초과한다. Answer import queue # Class for 1 horses in the chess board class Horse: def __init__(self, pos, idx): self.pos = pos self.idx = idx # Return position of this horse def get_pos(self): return self.pos # Return idx of this horse def get_idx(self): return self.idx # Return another horse moved from this horse def move_and_create(self, dpos): return..

Question 문제 링크 How 그냥 단순하게 앞의 소부터 뒤의 소를 전부 검색하면 시간 초과로 인해 통과가 안된다. 그래서 아래와 같이 최소한으로 list 를 검색하도록 해야 한다. 아래와 같은 로직으로 풀었다. Stack 에 소를 넣을 때, 현재 들어오는 소보다 작은 소들은 Stack 에서 전부 뺀다. 그리고 Stack 에 남은 소들의 개수를 결과 변수에 더해준다. 이렇게 진행할 경우, Stack 의 소들은 항상 정렬되어 존재한다. 앞에서부터 소를 한마리씩 넣으면, 해당 소보다 키가 큰 소만 현재 들어오는 소를 볼 수 있기 때문에 작은 소들은 버리는 것이다. Java 로 풀었을 때 위의 로직만으로는 시간제한을 어기게 된다. 그래서 현재 들어오는 소보다 키가 작은 소의 위치를 찾을 때, 앞에서부터 찾..

Question 입력값을 6 6 을 주면 아래와 같이 6*6 매트릭스에 나선형 회전을 한 값을 출력해야 한다. 6 6 0 1 2 3 4 5 19 20 21 22 23 6 18 31 32 33 24 7 17 30 35 34 25 8 16 29 28 27 26 9 15 14 13 12 11 10 코딩도장 문제 링크 Answer # Input, map size and make default map n, m = 6, 6 board = [[-1 for i in range(m)] for j in range(n)] # x and y is starting point # dx and dy is amount of moving # count is x, y = 0, 0 dx, dy = 0, 1 count = 0 while b..