이지코딩

MST 즉 최소신장트리 (최소 스패닝 트리)는 간선에 weight가 있는 그래프를 tree로 만들어 문제를 해결할때 유용하게 사용할 수 있다. 그래프를 최소 비용 간선을 가진 tree로 만드는 방법을 MST 라고 한다. MST를 만들 조건은 1. 그래프 간선에 weight가 있을 경우 2. Cycle이 없어야 할 경우 라고 할 수 있다. MST는 kruskal 알고리즘을 사용하여 tree를 구성하는데, 아래와 같이 동작한다. 1. 가장 weight가 적은 간선을 선택 2. 선택된 간선에 연결된 두 노드가 같은 tree인지 확인한다. 3-1. 두 노드가 서로 다른 tree인 경우 같은 tree로 만들고 1로 돌아간다. 3-1. 두 노드가 같은 tree인 경우 1로 돌아간다. 이것을 반복할 경우, weigh..

다익스트라 알고리즘은 O(NlongN) 안에 한 노드에서 다른 모든 노드에 대한 최단 거리를 찾을 수 있다. 벨만-포드 알고리즘의 경우 O(N^2)으로 최단 거리를 찾는다. 벨만-포드 알고리즘이 존재하는 이유는 "음수"값을 가지는 간선이 존재할때 최단 거리를 찾기 위함이다. 음수 간선이 존재할 경우 circuit이 생길 수도 있는데, circuit을 돌 수록 음수 간선에 의해 최단 거리가 계속 줄어들 수도 있다. 하지만, 상식적으로 생각해 본다면, 같은 길을 반복해서 지나가는건 최단 거리가 아니다. 벨만-포드는 이 두가지 경우를 상정할 때 최단 거리를 구할 수 있는 알고리즘이다. 벨만-포드의 특징은 - 음수간선이 존재 - Cycle을 돌면 안됨 -> cycle을 돌 경우 탐색 중지 라고 할 수 있다. 다..

다익스트라 알고리즘은 최단거리 (shortest path) 탐색 알고리즘의 일종으로, DP에 기반한 알고리즘이다. 한 node에서 다른 모든 node 까지의 최단거리를 탐색할 수 있다. 각 노드간 간선이 존재하고, 각 간선의 거리가 주어질 때 최단 거리를 구할 수 있다. 다음과 같은 그래프가 있다고 가정한다. Node 1에서 각 노드까지의 거리를 표로 정리하면 다음과 같다. 노드 1 2 3 4 5 6 거리 0 2 5 1 INF INF 노드 1에서 5,6까지는 바로 갈 수 없으므로 무한으로 가정한다. 이때 1에서 가장 가까운 노드는 4이다. 따라서 node 4를 거칠 경우 1에 대한 최단 거리를 먼저 구한다. 4를 거쳐 갈 수 있는 노드는 3,5 인데, 1-4-3으로 3까지 갈 경우 거리는 1+3 = 4이..

Outlook에서 학생들의 정보를 추출했으니, 엑셀 파일에 해당 학생의 퀴즈 제출 여부에 체크를 하면 된다. 먼저, 엑셀을 사용하기 위해서는 openpyxl 이라는 라이브러리를 사용해야한다. from openyxl import load_workbook 을 사용하여 엑셀의 한 시트에 접근하여 작업을 할 수 있다. 1 2 3 4 5 from openpyxl import load_workbook # Exel API wb = load_workbook(filename="test.xlsx") # 엑셀파일 오픈 sheet = wb.worksheets[0] # 맨 앞에 시트 꺼내기 sheet['C4'] = 'o' # 시트에 작성 wb.save("test.xlsx") cs 위와 같이 엑셀 파일을 열고, 시트 인덱스에 따..

학부생 수업의 조교를 맡게 되었다. 일거리가 늘어났지만 나 또한 학부생때 들었던 수업이라 열심히 하려고 한다. 매주 학부생들은 한 챕터가 끝날때마다 수업에 대한 퀴즈를 풀고, 조교에게 메일로 퀴즈결과를 전송한다. 조교의 업무 중 하나는 매주 메일을 확인하여 제출을 완료 한 학생을 엑셀에 표시하는 것. 매우 단순한 일이다. 다만 문제는 매주 174개의 메일이 온다는것.... 메일 내용에 있는 챕터 번호와 학번을 일일히 확인하고 엑셀에 해당 학번을 검색해서 "o"를 표시하면 되는데.... 20개쯤 하다보니 현타가 왔다. ... 내가 지금 뭘 하는거지 .... 공부할 것도 산더미 인데... 이렇게 시간낭비를 할수는 없다. 사실 귀찮다... 인터넷에서 이런말을 봤다. 파이썬과 구글만 있으면 못할게 없다고. 나는..