이번 시간에는 다익스트라 라는 최단 거리를 알아내는 알고리즘에 대해 배워 보도록 하겠습니다. 1. Dijkstra Algorithm - 다익스트라 알고리즘이란? 그래프에서 최단 경로를 찾아내는 알고리즘은 많이 나와있지만 그 중에서 가장 기본이 되는 알고리즘을 뜻함. 다른 최단 거리 알고리즘은 다익스트라를 기반으로 나온 알고리즘입니다. 다익스트라 알고리즘에 대해 미리 조금 살펴보자면 다음과 같은 것들이 존재합니다. 한 vertex에서 다른 vertex까지의 최단 경로이다. Edge의 가중치(weight)은 양수만 가능(음수 불가능)하다. 가중치에 음수가 있는 경우에는 Bellman-Ford's algorithm(벨만-포드 알고리즘) 혹은 Floyd-Warshall(플로이드-워셜) 알고리즘을 사용한다. 대부..

이번 시간에는 다이나믹 프로그래밍(동적 계획법 ,DP)에 대해서 배워 보도록 하겠습니다. 1. 다이나믹 프로그래밍이란? Dynamic Programming 줄여서 DP(또는 동적 계획법)는 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법입니다. 위의 말을 쉽게 풀자면 아래와 같이 정리할 수 있습니다. 하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것 큰 문제를 작은 문제로 쪼개서 그 답을 저장해 두었다가 재활용(기억하며 풀기) 2. 왜 DP를 쓰는 것일까? 사실 일반적인 재귀(Naive Recursion)방식 또한 DP와 매우 유사하다고 볼 수 있는데, 차이점은 일반적인 재귀를 단..

이번 시간에는 그래프 탐색 방법 중 깊이 우선 탐색(DFS)에 대해서 배워볼 것입니다. 1. 그래프 탐색이란하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것EX) 특정 도시에서 다른 도시로 갈 수 있는 지 없는 지, 전자 회로에서 특정 단자와 단자가 서로 연결 되어 있는 지그래프는 탐색하는 동안 동일한 정점으로 다시 이동할 수 있는 싸이클이 있을 수 있습니다. 그래서 동일한 정점이 다시 처리되지 않도록 하려면 처리 후 정점을 방문(visited)했다는 표시를 함으로써 중복 방문을 피하도록 하는 것이 그래프 탐색의 핵심입니다. 2. DFS (Depth-First Search, 깊이 우선 탐색 )DFS는 그래프의 개념이 반드시 선행되어야 하기 때문에 다음 포스트를 먼저 확인하길 바랍니..

이번 시간에는 그래프에 대해 알아보도록 하겠습니다. 1. Graph - 그래프란? 그래프(Graph)는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조입니다. 먼저 그래프와 트리의 차이점을 살펴보면 다음과 같습니다. 구분 그래프(Graph) 트리(Tree) 정의 객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조 그래프의 한 종류이고 방향성이 없으며 순환하지 않음 방향성 무방향 혹은 유방향으로 가능 무방향 그래프 순환성 순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 모두 가능 순환 불가능 자기 자신 연결 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph) 루트 ..

이번 시간에는 Heap 자료구조와 우선순위 큐 (Priority Queue)에 대해서 알아봅시다. 1. 힙 - Heap Heap 자료구조에 대해서 배워 보도록 합시다. 시작하기 앞서 Computer Science(CS) 분야에서 힙이라는 것은 두 가지의 의미를 가지고 있습니다. 자료구조 힙(Heap) Java의 메모리 영역 이 두 가지는 같은 용어를 사용하지만 엄연히 다른 의미를 갖고 있기 때문에 구분하여 알아두어야 합니다. 그렇지만 자료구조 및 알고리즘 수업이기 때문에 여기서는 자료구조 힙에 대해 먼저 보도록 하겠습니다. (CS 카테고리 중 운영체제 수업에서 Java의 메모리 영역으로써의 힙 내용이 다뤄집니다.) 1-1. 자료구조 힙 힙(heap)은 이진 힙(binary heap)이라고도 하고, 최댓값..

이번 시간에는 트리 구조에 대해서 배워보도록 하겠습니다. 1. 트리(Tree)란? 트리란 노드들이 나무 가지처럼 연결된 비선형(non-linear), 계층적 자료구조로 위 그림처럼 나무를 거꾸로 뒤집어 놓은 것과 같은 모양이어서 트리(tree)라는 이름을 가지게 된 자료구조입니다. 개요 트리는 한 노드가 여러 노드를 가르킬 수 있는 비선형적 자료구조를 일컫는 말입니다. 앞서 배웠던 리스트(List), 스택(Stack), 큐(Queue)는 이전 데이터와 다음 데이터 간의 순서가 존재했습니다. 트리도 물론 내부적으로 순서 정보를 가지도록 구현할 수도 있지만 트리 구조자체의 특성상 순서는 그렇게 중요하지 않습니다. 그래서 트리는 뒤에서 배우게 될 그래프(Graph)의 일종이며 데이터 구조의 상하 개념 계층의 ..

이번시간에는 퀵 정렬에 대해서 배워 보도록 하겠습니다. 저번 포스팅에서 설명했던 정렬 방식들(버블 정렬, 삽입 정렬, 선택 정렬) 은 가장 기본적인 수준의 정렬 방식들입니다. 그러나 이것들은 일반적으로 좋은 성능은 낼 수 없기때문에 실제로 개발 시에는 잘 사용하지 않습니다. 앞으로 배울 Merge / Quick 정렬은 굉장히 중요하기 때문에 자세히 알아보도록 하겠습니다. 1. 퀵 정렬이란? 먼저 퀵정렬의 특징은 다음과 같습니다. 퀵 정렬(Quick Sort)은 합병 정렬(Merge Sort)과 마찬가지로 배열을 둘 씩 분할하며 정렬하는 과정을 거치기 때문에 시간복잡도 O(nlog2n)을 갖습니다. 하지만 같은 시간 복잡도라도 실제 정렬에서는 합병 정렬보다 퀵 정렬이 훨씬 더 빠른 시간 안에 정렬이 가능합..

이번 시간에는 merge sorting에 대해서 배워보도록 하겠습니다. 저번 포스팅에서 설명했던 정렬 방식들(버블 정렬, 삽입 정렬, 선택 정렬) 은 가장 기본적인 수준의 정렬 방식들입니다. 그러나 이것들은 일반적으로 좋은 성능은 낼 수 없기 때문에 실제로 개발 시에는 잘 사용하지 않습니다. 앞으로 배울 Merge / Quick 정렬은 굉장히 중요하기 때문에 자세히 알아보도록 합시다. 1. Merge Sort(합병 정렬) 이란? merge sort와 다음 시간에 배울 quick sort가 정렬 알고리즘의 핵심이라고 할 수 있습니다. 하지만 중요한 만큼 이전에 배웠던 것들과는 다르게 매우 복잡하게 진행이 됩니다. 하나의 리스트를 두 개의 균등한 크기의 리스트로 분할하고 부분 리스트를 합치면서 정렬하여 최종..