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 로 풀었을 때 위의 로직만으로는 시간제한을 어기게 된다. 그래서 현재 들어오는 소보다 키가 작은 소의 위치를 찾을 때, 앞에서부터 찾..

Shallow & Deep Copy Shallow & Deep Copy Python 에서는 변수에 할당할 때, 메모리에 객체를 만들고 변수에는 이 메모리가 어디있는지 알려주는 주소만 할당한다. 그래서 헷갈리는 경우가 참 많은 것 같다. 예를 들어 아래와 같은 예시를 보면 변수를 할당할 때 값이 아닌 주소만 알려준다는 것을 알 수 있다. >>> >>> x = [3, 2, 1] >>> y = x >>> y [3, 2, 1] >>> >>> id(x) 4315217736 >>> id(y) 4315217736 >>> >>> x[0]=99 >>> x [99, 2, 1] >>> y [99, 2, 1] >>> y 에 x 를 할당하면 변수들이 가르치는 메모리의 주소(id)가 같고, x[0]의 값을 바꾸면 y[0]도 바뀌..

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

Github 연동 설정하기 Github 연동 설정하기 소스관리툴 Github 와 연동하자. 우선은 Github 홈페이지 로 가서 회원가입을 한다. 아래 화면이다. 여기에 쓰는 Username 과 E-mail 은 매번 쓰이니 기억해두자. 그리고 로그인하면 오른쪽 중간에 +New repository 라는 버튼이 있다. 이것을 클릭하면 Repository 이름과 설명, 그리고 Ignore File List 를 설정할 수 있다. 이름은 프로젝트명에 맞게 아무렇게나 하고, Add .gitignore 에서 Python 을 선택하고 Repository 를 생성하면 끝이다.원래는 git 명령어를 통해 소스파일을 관리하는데, 아직 눈에 잘 익지도 않고 정확히 원리를 잘 모르니 GUI 로 관리할 수 있는 Source Tr..