전체 글 (9) 썸네일형 리스트형 [알고리즘] 최단 경로 알고리즘 비교 및 사용 케이스 정리 그래프 이론에서 최단 경로를 찾는 문제는 가중치가 존재하지 않는 그래프에서 가장 짧은 경로를 찾는 문제와 가중치가 존재하는 가중 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제로 나눌 수 있습니다. 이때 가중치의 경우 비용, 시간, 수수료 등의 이름으로 주어질 수 있으며 심지어 이러한 가중치들은 음수로 주어지는 경우도 존재합니다. 본 포스팅에서는 다양한 최단 경로 문제를 해결하기 위해 존재하는 여러 알고리즘에 대해 비교 분석하며 사용해야하는 케이스들을 정리하도록 하겠습니다. 그리고 각각의 알고리즘에 대한 자세한 내용과 코드 분석은 이후에 포스팅하도록 하겠습니다. 최단 경로 문제 종류 먼저 최단 경로 문제의 유형을 알아보도록 하겠습니다. 단일-출발(Single-Source) 최단 경로 .. [알고리즘] PS 및 알고리즘 코드 작성 언어별 비교 프로그램 개발 또는 특정 프레임워크 사용이 아니라 Problem Solving 즉, 알고리즘 및 코딩 테스트 문제 해결을 위해서는 다양한 프로그래밍 언어를 고려해볼 수 있습니다. 그 중에서 대표적으로 많이 사용되는 언어 세 가지를 비교해보고 특징을 살펴보고자 합니다. 여기서 다룰 세 가지의 언어는 당연하게도 C++, Java, Python이 되겠습니다. 저는 주로 C++ > Python >>> Java 의 순으로 보통 사용하지만 요즘은 Python 리스트와 문자열의 압도적인 편리함 때문에 점차 그 사용빈도가 C++과 가까워지고 있습니다. Java 는 입출력 작성부터 코드가 길어지고 역량이 부족한 저에게는 귀찮고 불편한 존재라고 느껴져서.. 정말 가끔 Java 공부를 위해서 사용하곤 합니다. 그럼에도 각 .. [알고리즘] 너비 우선 탐색(BFS, Breadth-First Search) 구현 꿀팁 아닌 꿀팁(?) 너비 우선 탐색(Breadth-First Search) 알고리즘은 깊이 우선 탐색(Depth-First Search) 알고리즘과 마찬가지로 완전 탐색(맹목적 탐색)의 일종입니다. 하지만 특정 루트의 최대한 깊은 루트를 탐색하는 DFS와 다르게 BFS는 특정 노드의 인접한 노드들부터 탐색합니다. 주로 큐 자료구조를 사용해서 인접노드들을 차례로 탐색하게 됩니다. 보통 '가중치가 없거나 일정한 간선을 가진 노드들의 최단 경로'를 구할 때 사용하는 알고리즘입니다. 개요 DFS(깊이우선탐색) 알고리즘 포스팅과 마찬가지로 본 포스팅에서는 BFS(너비우선탐색)의 개념과 이론 설명은 생략하도록 하겠습니다. 개념 및 이론 이해가 필요한 분들께서는 서적과 다른 인터넷 사이트를 참고해주시면 감사하겠습니다. 본 포스팅에서는 .. [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) 구현 꿀팁 아닌 꿀팁(?) 깊이 우선 탐색(Depth-First Search) 알고리즘은 완전 탐색(맹목적 탐색)의 일종으로 특정 루트에서 최대한 깊은 루트까지 탐색하고 다시 돌아와 다른 루트를 탐색하는 방식의 알고리즘입니다. 주로 재귀 호출을 통해 구현하며 스택을 사용해 구현할 수도 있습니다. 반복되는 함수 호출이 있기 때문에 메모리 초과를 주의해야 합니다. 개요 사실 DFS(깊이우선탐색), BFS(너비우선탐색), Backtracking(백트래킹)과 같은 기본적인 완전탐색 알고리즘은 학부 수업에서 반드시 가르치는 내용이고 알고리즘 학문에서도 기초적인 수준의 내용이므로 본 포스팅에서는 개념과 이론에 대해서는 생략하겠습니다. 충분한 이론 설명이 필요한 분들께선 서적과 다른 인터넷을 참고해주시면 감사하겠습니다. 본 포스팅에서는 DFS.. [알고리즘] 최소 신장 트리(Minimum Spanning Tree / MST) 개요 및 개념 임의의 정점(Vertex or Node)에서 다른 정점으로 연결된 모든 간선(Edge)들이 가중치를 가졌을 때, 모든 정점을 연결한 가장 적은 가중치의 합을 가지는 트리(Tree)를 만들려면 어떻게 해야할까요? 트리(Tree)란 순환(Cycle)을 가지지 않는 연결 그래프이며 임의의 두 정점에 대해 경로는 반드시 1개만 존재합니다. 최소 신장 트리(MST)란? 신장 트리(Spanning Tree)는 무향 연결 그래프 G가 있을때, G의 부분 그래프이며, G의 모든 정점을 포함하는 트리(Tree) 구조인 그래프라고 할 수 있습니다. 위 그림과 같이 무향 그래프 G의 모든 정점을 포함하는 트리를 신장트리, Spanning Tree 라고 합니다. 그리고 만약 여기서 간선들이 가중치를 가졌다면 가중치의 합을 최.. [알고리즘] 유니온-파인드(Union-Find) & 서로소 집합(Disjoint Set) 개요 및 개념 상호 배타적, 즉 공통 원소가 없는 집합 간의 관계를 서로소 집합이라고 합니다. 그리고 이렇게 교집합이 공집합인 집합(서로소 집합)들을 효율적으로 관리(확인[Find]과 조작[Union])하기 위한 자료구조를 유니온-파인드라고 합니다. 서로 다른 집합을 병합(Union)하고 원소가 어느 집합에 속해있는지 확인(Find)하기 위한 연산을 제공하기 때문에 이러한 이름이 붙게 되었습니다. 원소의 같은 집합 찾기 문제나 같은 동맹군 찾기 문제에 활용할 수 있는 자료구조입니다. 유니온-파인드(Union-Find)란? Union 연산은 다음과 같은 기능을 합니다. 어떤 두 원소 \( a,b \) 에 대해서 각 원소가 속한 집합을 하나로 합치는 연산 \( a \in A, b \in B \) 에 대해서, \( unio.. [알고리즘] 트라이(Trie) 개요 및 개념 여러 개의 문자열이 등록된 사전을 만들고 특정 문자열이 이 사전안에 등재된 문자열인지 확인하려면 어떻게 해야할까요? 단순히 일일이 비교해서 확인해보면 되지만 이 경우 최악의 경우에 \( O(nm) \)의 수행시간이 필요합니다. 혹은 이진 탐색을 사용하여 \( O(m\textbf{log}n) \)으로 단축시킬 수 있지만 정렬 과정에서 \( O(mn\textbf{log}n) \)의 시간이 걸리게 됩니다. 이러한 문자열 검색의 시간복잡도를 단축시키기 위해서는 프레드킨이 명명한 Retrieval Tree 알고리즘이 필요합니다. (Prefix Tree, Digital Search Tree 라고도 합니다.) 트라이(Trie)란? 트라이는 탐색 트리의 일종으로 문자열을 빠르게 검색할 수 있는 자료 구조입니다. K진 .. [번역] 학생을 위한 Google Developers 테크 라이팅(1) 본 글은 Google Developers 에서 제공하는 Technical Writing For students 자료를 바탕으로 한국어로 번역/정리한 글입니다. 원문은 다음 링크에서 확인할 수 있습니다. https://developers.google.com/tech-writing/overview Overview of technical writing courses | Technical Writing The following table summarizes the technical writing courses: Title Summary Pre-Class In-Class Technical Writing One Learn the critical basics of technical writing. Take this .. 이전 1 2 다음
