나의 첫 코딩테스트문제는 총 5문제였고, 알고리즘 4문제, SQL 1문제가 나왔다.난이도는 생각보다 쉽게 나왔다. 체감상 브론즈2~골드5 정도였던 것 같다제한시간은 문제당 10초였고, 메모리는 2GB였다. 백준에서는 많아봐야 512MB였는데 2GB나 줘서 편안하게 풀었던 것 같다.시험시간은 총 120분이었다.SQL을 먼저 풀었고, 알고리즘 3문제를 풀었더니, 1시간이 남아있었다. 마지막 한 문제에 40분 정도 쓴 것 같다.5문제 전부 테스트 케이스는 맞췄는데, 합격 여부는 아직 미지수이다.코딩테스트는 프로그래머스에서 진행되었고, 모니토앱(?)으로 신분증 검사하고, 앞뒤좌우상하를 카메라로 검사하고, 시험볼 때는 노트북 웹캠과 폰카메라 두 기기로 동시에 녹화 및 감독하며 시험을 진행했다. A4용지에 뭐 써진..
크루스칼 알고리즘간선들의 비용을 기준을 정렬한 뒤, 사이클을 이루지 않게끔 최소 신장 트리를 형성하는 알고리즘비용을 기준으로 간선들을 오름차순으로 정렬한다.간선들을 하나씩 확인하며 사이클을 발생시키는지 확인한다.사이클을 발생시킬 경우 포함 x사이클을 발생시키지 않으면 최소 신장 트리에 포함시킨다.모든 간선에 대하여 2번 과정을 반복한다. 크루스칼 알고리즘# 사이클 여부 판별을 위한 union-find 함수들def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) return parent[x]def union(parent, a, b): a = find(parent, a) b = find(pare..
서로소 집합공통 원소가 없는 두 집합서로소 집합들로 나누어진 원소들의 테이터를 처리하기 위한 자료구조는 union 연산과 find 연산으로 조작할 수 있다. union 연산 : 서로 다른 두 원소에 대하여 합집합을 수행하는 것이다. 각각의 루트 노드를 찾아서 그 두 노드 중 더 작은 루트 노드를 가리키도록 하는 방식이다. find 연산 : 특정 원소가 속한 집합을 찾는 것이다. find_parent 함수를 재귀 호출하여 루트 노드를 찾는 방식이다. 서로소 집합 알고리즘def find_parent(parent, x): # 자기 자신이 parent일 경우에는 자신이 루트 노드라는 것이기 때문에, # if 문을 건너뛰고 자기 자신을 리턴한다. if parent[x] != x: ..
최단 경로말 그대로 가장 짧은 경로를 찾는 알고리즘학교 알고리즘 수업시간에 다익스트라 알고리즘과 플로이드 워셜 알고리즘 이 두 가지를 배웠었는데, 이코테에서도 이 두 가지를 설명하고있다.한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우 - 다익스트라 알고리즘모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우 - 플로이드 워셜 알고리즘 다익스트라 알고리즘다익스트라 알고리즘은 음의 간선이 없을 경우 정상적으로 동작한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미한다.출발 노드 설정최단 거리 테이블 생성방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신3, 4번 반복3번에서 방문되지 않은 노..