Data Structure & Algorithm (31) 썸네일형 리스트형 위상 정렬 알고리즘(Topological Sort Algorithm) - 그래프 이론 위상 정렬(Topology Sort)은 정렬 알고리즘의 일종이다. 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 조금 더 이론적으로 설명하자면, 위상 정렬이란 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 현실 세계에서 위상 정렬을 수행하게 되는 전형적인 예시로는 '선수과목을 고려한 학습 순서 설정'을 들 수 있다. 예를 들어 컴퓨터공학과 커리큘럼에는 '자료구조' 과목을 수강한 뒤에 '알고리즘' 강의를 수강하는 것을 권장한다. 이때 '자료구조' 및 '알고리즘'을 각각의 노드로 표현하고, '자료구조'에서 '알고리즘'으로 이어질 수 있도록 방향성을 갖는 간선을 그릴 수 있다. 다시 말해 그래프상에서 선후 관계가 있다면.. 크루스칼 알고리즘(Kruskal Algorithm) - 그래프 이론 신장 트리 신장 트리는 그래프 알고리즘 문제로 자주 출제되는 문제 유형이다. 기본적으로 신장 트리(Spanning Tree)란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다. 그래서 이러한 그래프를 신장 트리라고 부르는 것이다. 예를 들어 다음 왼쪽과 같은 그래프에서는 여러 개의 신장 트리를 찾을 수 있다. 바로 오른쪽이 그 중 하나이다. 반면에 다음 왼쪽 그림은 그래프가 '노드 1'을 포함하고 있지 않기 때문에 신장 트리에 해당하지 않는다. 또한 오른쪽 그림은 사이클이 존재하므로 신장 트리가 아니다. 크루스칼 알고리즘 우리는 다양한 문제 상황에서 가.. 서로소 집합 알고리즘(Disjoint Sets Algorithm) - 그래프 이론 수학에서 서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어 집합 {1, 2}와 집합 {3, 4}는 서로소 관계이다. 반면에 집합 {1, 2}와 집합 {2, 3}은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아니다. 서로소 집합 자료구조를 설명하려면 서로소 집합 개념이 필요하다. 서로소 집합 자료구조는 몇몇 그래프 알고리즘에서 매우 중요하게 사용되므로 그래프 알고리즘 이론 전에 설명하고자 한다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다. 서로소 집합 자료구조는 union과 find 이 2개의 연산으로 조작할 수 있다. union(합집합) 연산은 2개의 원소가 포함된 .. 그래프 이론 지금까지 코딩 테스트에서 출제 비중이 높은 알고리즘 유형들을 다루어 보았다. 이번에는 지금까지 다루지 않았던 그래프 알고리즘을 추가로 다룰 것이다. 이전에 'DFS/BFS'와 '최단 경로'에서 다룬 내용은 모두 그래프 알고리즘의 한 유형으로 볼 수 있다. 이외에도 그래프 알고리즘은 굉장히 다양한데, 코딩 테스트에서 출제 비중이 낮은 편이지만 꼭 제대로 알아야 하는 알고리즘이다. 여기서 다루는 개념들을 바르게 이해할 수 있다면 코딩 테스트에서 만나게 될 다양한 응용문제들도 해결할 수 있을 것이다. 크루스칼 알고리즘(Kruskal Algorithms)은 그리디 알고리즘으로 분류되며, 위상 정렬 알고리즘(Topology Algorithms)은 앞서 배운 큐 자료 혹은 스택 자료구조를 활용해야 구현할 수 있다... 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm) 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 다익스트라 최단 경로 알고리즘과 이 부분에서 차이가 있다. 플로이드 워셜 알고리즘의 소스코드는 매우 짧아서 다익스트라 알고리즘과 비교하면 구현 과정에서 어려움을 겪지는 않을 것이다. 다만, 핵심 아이디어를 이해하는 것이 중요하다. 다익스트라 알고리즘은 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다. 플로이드 워셜 알고리즘 또한 단계마.. 다익스트라(Dijkstra) 최단 경로 알고리즘 가장 빠르게 도달하는 방법 최단 경로(Shortest Path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기' 문제라고도 불린다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 예를 들어 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등의 다양한 사례가 존재한다. 이런 사례에 맞는 알고리즘을 알고 있다면 문제를 조금 더 쉽게 풀 수 있다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 또한 실제 코딩 테스트에서는 최.. 다이나믹 프로그래밍(Dynamic Programming) 중복되는 연산을 줄이자 컴퓨터를 활용해도 해결하기 어려운 문제는 무엇일까? 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 컴퓨터의 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점은 많은 제약을 발생시킨다. 그래서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 다이나믹 프로그래밍(Dynamic Programming) 기법으로 '동적 계획법'이라고도 한다. 프로그래밍에서 다이나믹은 '프로그램이 실행되는 도중에'라는 의미이.. 이진 탐색(Binary Search) 알고리즘 순차 탐색 이진 탐색에 대해 알아보기 전에 가장 기본 탐색 방법인 순차 탐색에 대해 먼저 이해할 필요가 있다. 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점이 있다. 순차 탐색은 이름처럼 순차로 데이터를 탐색한다는 의미이다. 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단하다. 순차 탐색은 정말 자주 사용하는데, 리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서.. 이전 1 2 3 4 다음
