Algorithm

종류시간 복잡도설명버블O(n2)두 인접한 데이터의 크기를 비교하여 크기가 작/크면 swap 정렬하는 방식선택O(n2)전체 데이터 중에서 가장 작은/큰 값을 찾아 첫 번째 위치부터 순서대로 정렬하는 방식삽입O(n2)앞의 이미 정렬된 부분에서 데이터의 알맞은 위치를 찾아 삽입하여 정렬하는 방식퀵평균O(nlogn)pivot을 선정하고 이를 기준으로 크기가 작은 값, 큰 값을 나누어 정렬하는 방식pivot 선정이 잘못될 경우 최악의 경우 O(n2)까지 성능이 떨어질 수 있음.병합O(nlogn)데이터를 가장 작은 단위로 나눈 후, 다시 병합하면서 정렬하는 방식안정적인 성능을 보장하지만, 추가 메모리 사용이 필요함 1. 버블 정렬 (Bubble Sort)버블 정렬은 인접한 두 요소를 비교하여 큰 값을 뒤로 보내는 ..

그래프(G)는 정점(vertex)들의 집합 V와 이들을 연결하는 간성(edge)들의 집합 E로 구성된 자료구조입니다. 그래프의 종류 1. 무방향 그래프(undirected graph) vs 방향 그래프(directed graph) 무방향 그래프는 A→B B→A로도 갈 수 있는 방향이 정해져 있지 않은 그래프입니다. 반대로 방향 그래프는 방향이 정해져 있습니다. 이 때 들어오는 간선을 indegree라 하며, 나가는 간선을 outdegree라 합니다. 정점 B를 살펴보면 A와 C로 부터 들어오는 indegree 2개, E로 나가는 outdegree 1개가 있는 것을 알 수 있습니다. 코딩테스트는 주로 무방향 그래프(undirected graph) 문제를 다룹니다. 2. 다중 그래프 vs 단순 그래프 인접해..

트리(Tree)는 서로 연결된 Node의 계층형 자료구조로, root와 부모-자식 관계의 subtree로 구성되어 있습니다. 트리 순회 트리는 비선형 자료구조이기 때문에 순회하는 방법이 여러 가지 존재합니다. 대표적으로 level order traversal, preorder traversal, inorder traversal, postorder traversal가 있습니다. Level-order Traversal 이 방법은 말 그대로 level 별로 순회하는 것을 말합니다. (A) ► (B, C, D) ► (E, F, G, H, I) ► (J, K, L) 구현 level order는 가장 기본적인 코드이므로, 추후 참고없이 직접 구현할 수 있어야 합니다. queue = 방문할 노드를 순서대로 입력 vi..

Hash table은 빠른 탐색을 위해 key-value 형태로 데이터를 입력받는 자료 구조입니다. 저장, 탐색, 검색의 시간 복잡도는 모두 O(1)입니다. Direct-address Table 직접 주소화 테이블이란, key k를 index k 위치에 저장하는 방식입니다. 이러한 저장 방식은 많은 문제가 발생합니다. 불필요한 공간 낭비 key값으로 문자열이 올 수 없다. 이러한 문제를 해결하기 위해 Hash table을 이용합니다. 이는 hash function h를 이용해서 (key, value)를 저장합니다. “h(k)는 키 k의 해시값이다” 모든 데이터에 key값은 존재하며, 중복되는 key값이 있어서는 안된다. (key, value)데이터를 저장할 수 있는 각각의 공간을 slot 또는 bucke..

문제출처: 프로그래머스 런타임 에러 때문에 디버깅이 쉽지 않았다. 런타임 에러 발생 상황을 사전에 인지하여 검토하는 시간이 필요해보인다. 다음과 같이 크게 4가지 경우가 있다. ValueError: 부적절한 값을 인자로 받았을 경우 ZeroDivisionError: 0으로 나누었을 경우 IndexError: 인덱스 범위를 벗어나는 경우 NameError: 선언하지 않은 변수를 사용하는 경우 from collections import deque def solution(priorities, location): dq_i = deque(list(range(0, len(priorities)))) dq_p = deque(priorities) completed = 0 while dq_i: index = dq_i.po..

문제 출처: 프로그래머스 from collections import deque import math def solution(progresses, speeds): answer = [] # 소요시간 계산 progresses = deque(progresses) speeds = deque(speeds) prev_time = 0 # 이전 작업 소요시간 dist_cnt = 0 # 배포 수 while progresses: extra_prog = 100 - progresses.popleft() time = math.ceil(extra_prog/speeds.popleft()) if time