If at first you don't succeed, try again

* 개요 플로이드-워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. 플로이드-워셜 알고리즘은 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다. 노드의 개수가 N개일 때, 알고리즘 상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 폴로이드-워셜 알고리즘의 총 시간 복잡도는 O(N^3)이다. 다익스트라 알고리즘은 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해서 1차원 리스트를 이용했다. 반면에 플로이드 워셜 알고리즘은 다익스트라 알고리즘과는 다..

* 개요 위상정렬은 정렬 알고리즘의 일종이다. 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 조금 더 이론적으로 설명하자면, 위상 정렬이란, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 위상 정렬 알고리즘을 알기 위해서는 먼저 진입 차수(Indegree)를 알아야 한다. 진입 차수란 특정한 노드로 들어오는 간선의 개수를 뜻한다. 방향 그래프에서 위상 정렬을 수행하는 절차는 다음과 같다. 진입 차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다.(3 -> 4, 3 -> 4, ...) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입 차수가 0이 된 노드를 큐에..

* 개요 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다. 음의 간선이란, 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다. 알고리즘의 원리를 간략히 설명하면 다음과 같다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은..

* 개요 파이썬으로 코테, 자료구조, 알고리즘 공부를 진행하다보니, 리스트 선언의 중요성이 더욱 와닿는다는 것을 느꼈다. 오늘 소개할 List Comprehension(리스트 컴프리헨션)은 리스트를 초기화하는 방법 중 하나이다. 리스트 컴프리헨션은 간단히 0부터 19까지의 수 중에서 홀수만 포함하는 리스트를 만들고자 할 때는 다음과 같이 리스트를 초기화할 수 있다. 이 경우 한 줄의 소스코드로 리스트를 초기화할 수 있어 매우 간편하다. # 0부터 19까지의 수 중에서 홀수만 포함하는 리스트 array = [i for i in range(20) if i % 2 == 1] print(array) # [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 참고로 위 소스코드를 일반적인 소스코드로 작성..

* 개요 수학, 특히 그래프 이론에서 회로가 없는 연결된 무향의 그래프를 Tree(트리)라고 한다. 트리의 각 부분의 명칭과 용어는 다음과 같다. 트리는 항상 root 노드에서 시작된다. 루트 노드는 자식 노드를 가지며, 간선으로 연결되어 있다. 자식 노드의 개수는 차수라고 하며, 크기는 자신을 포함한 모든 자식 노드의 개수다. 높이는 현재 위치에서부터 리프까지의 거리, 깊이는 루트에서부터 현재 노드까지의 거리다. 트리는 그 자식도 트리인 서브트리 구성을 띤다. 레벨은 0부터 시작한다. 트리는 항상 단방향이기 때문에(단방향이 아니면 순환 참조가 발생하여 문제 발생) 간선의 화살표는 생략이 가능하다. 일반적으로 방향은 위에서 아래로 향한다. 루트 노드(root node/root): 트리에서 부모가 없는 최..

* 개요 Hash Table(해시 테이블)은 Index(색인)에 해시값을 사용하는 자료구조로, 정렬을 하지 않고도 빠른 검색, 빠른 삽입이 가능하다는 특징을 가진다. 해시는 리스트를 사용하는 접근법은 동일하지만, 여기에 색인 개념이 추가되어 있다. 충분히 큰 공간을 할당받은 다음, 해시 함수를 이용하여 고유 인덱스를 생성한다. 그리고 이 고유 인덱스와 맞는 위치에 데이터를 저장한다. 예를 들어, 0 ~ 100까지의 데이터를 담을 수 있는 리스트를 생성하고, '사과' 라는 단어에 해시 함수를 적용하여 50이라는 인덱스가 생성되면, 리스트의 50번 인덱스에 '사과'를 저장하는 방식이다. 언제나 동일한 해시 값을 반환하기 때문에 '사과'를 입력하면 50이라는 인덱스가 나오므로, 정렬하지 않고도 데이터를 탐색할..

코딩테스트 연습 - 더 맵게 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr * 문제 설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 ..

* 개요 Deque(덱)은 단뱡향으로만 데이터의 삽입 / 삭제가 가능했던 큐와는 달리 양방향으로 데이터의 삽입 / 삭제가 가능한 자료구조이다. 즉, 스택으로도 쓸 수 있고, 큐로도 쓸 수 있다는 장점이 있다. 리스트 자료형이 있는데, 덱을 많이 사용하는 이유는 리스트보다 덱의 속도가 훨씬 빠르기 때문이다. 리스트는 O(N), 덱은 O(1)의 시간 복잡도를 가진다. * 파이썬으로 구현한 덱 deque 모듈을 활용하여 덱을 구현하였다. from collections import deque queue = [] dq = deque(queue) dq.append(1) # 1 dq.append(2) # 1 2 dq.append(3) # 1 2 3 dq.appendleft(0) # 0 1 2 3 dq.pop() # ..

* 개요 Circular Queue(원형 큐)는 큐의 변형된 구조로서, 데이터를 넣는 부분(rear)과 데이터를 빼는 부분(front)을 포인터로 지정함으로써,enqueue와 dequeue를 하는 형태의 자료구조이다. 원형 큐에서 정해둔 큐의 크기보다 더 큰 경우(큐가 가득 찬 경우), 큐가 비어있을 경우에 포인터가 같은 위치를 지정하기 때문에 이를 해결하기 위해 한 공간을 비워놓는다.(None or Null) * 파이썬으로 구현한 원형 큐 원형 큐를 리스트로 구현하였다. MAX_SIZE = 5 class CircularQueue: def __init__(self): self.front = 0 self.rear = 0 self.queue = [None] * MAX_SIZE def enqueue(self,..

* 개요 Priority Queue(우선순위 큐)는 선입선출 구조를 가지는 일반적인 큐의 자료구조와는 달리, 데이터의 삽입은 순서와 관계가 없지만 삭제할 때는 우선순위가 높은 원소부터 삭제가 되는 자료구조이다. 우선순위 큐의 대표적인 예로 heap이 있다. * Heap(힙) heap(힙)은 여러 개의 값 중에서 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 이진 트리이다. 힙의 종류에는 최대 힙과 최소 힙이 있는데, 최대 힙은 root 노드에 가장 큰 값이 들어가게 되며, 최소 힙은 root 노드에 가장 작은 값이 들어가게 된다. 힙의 데이터 삽입 및 삭제의 시간 복잡도는 O(logN)이 소요된다. * 파이썬으로 구현한 우선순위 큐(최소 힙) 우선순위 큐를 위해서 파이썬에 내장되어 있는 heapq ..