본문 바로가기

전체 글

 (65)
위상 정렬 알고리즘(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) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기' 문제라고도 불린다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 예를 들어 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등의 다양한 사례가 존재한다. 이런 사례에 맞는 알고리즘을 알고 있다면 문제를 조금 더 쉽게 풀 수 있다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 또한 실제 코딩 테스트에서는 최..
람다(lambda) - Python lambda는 함수를 생성할 때 사용하는 예약어로 def와 동일한 역할을 한다. 보통 함수를 한 줄로 간결하게 만들 때 사용한다. def를 사용해야 할 정도로 복잡하지 않거나 def를 사용할 수 없는 곳에 주로 쓰인다. 사용법은 다음과 같다. lambda 매개변수1, 매개변수2, ... : 매개변수를 사용한 표현식 한 번 직접 만들어 보자. add = lambda a, b: a + b result = add(3, 4) print(result) add는 두 개의 인수를 받아 서로 더한 값을 돌려주는 lambda 함수이다. lambda 예약어로 만든 함수는 return 명령어가 없어도 결괏값을 돌려준다. 위 예제는 def를 사용한 다음 함수와 하는 일이 완전 동일하다. def add(a, b): return..
다이나믹 프로그래밍(Dynamic Programming) 중복되는 연산을 줄이자 컴퓨터를 활용해도 해결하기 어려운 문제는 무엇일까? 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 컴퓨터의 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점은 많은 제약을 발생시킨다. 그래서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 다이나믹 프로그래밍(Dynamic Programming) 기법으로 '동적 계획법'이라고도 한다. 프로그래밍에서 다이나믹은 '프로그램이 실행되는 도중에'라는 의미이..

티스토리툴바