알고리즘

그리디 알고리즘(탐욕법)이란? : 현재 상황에서 가장 좋은 것만 고르는 방법을 의미합니다. 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 합니다.

다이나믹 프로그래밍이란? > 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법입니다. 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. 동적 계획법이라고도 부릅니다. 조건 다이나믹 프로그래밍은 문제가 다음의 조건을

유클리드 호제법은 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘입니다. 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 합시다. 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다. 유클리드 호제법의 아이디어를 그대로 재귀

DFS(Depth-First Search) > DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.

BFS(Breadth-First Search) > BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다. 동작 과정 BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다. 탐색 시작 노드를 큐에 삽입하

이진 탐색 > 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법입니다. 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다.

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다.Step 0 처리되지 않은 데이터 중 가장 작은 0을 선택해 가장 앞인 7과 바꿉니다. Step 1 처리되지 않은 데이터 중 가장 작은 1을 선택해 가장 앞인 5와 바

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다. 삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작합니다. Step 0 첫 번째 데이터 7은 그 자체로 정렬이 되어있다고 판단하고, 두 번째 데이터인 5가 어떤 위치로

기준 데이터를 설정하고 그 기준보다 작은 데이터의 위치를 바꾸는 방법입니다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘입니다. 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다. 가장 기본적인 퀵 정렬은 첫 번째 데이터

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 알고리즘입니다. \- 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능합니다. 데이터의 개수가 N, 데이터(양수) 중 최대값이 K일 때, 최악의 경우에도 수행 시간

트리의 순회는 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을 의미합니다. 대표적인 트리 순회 방법은 전위 순회, 중위 순회, 후위 순회가 있습니다. 위 그림의 트리를 예제로 구현해보겠습니다. 트리 구현을 위해 다음과 같은 클래스를 정의합니다.

다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산합니다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작합니다. 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됩니다. 매 상황에서 가장 비

벨만 포드 최단 경로 알고리즘

신장 트리는 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 합니다. 최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 어떻게 해야 할까요?