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

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

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

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

전략 패턴은 정책(policy) 패턴이라고도 하며, 객체의 행위를 바꾸고 싶은 경우 '직접' 수정하지 않고 전략이라고 부르는 '캡슐화한 알고리즘'을 컨텍스트 안에서 바꿔주면서 상호 교체가 가능하게 만드는 패턴입니다. 우리가 어떤 아이템을 살 때 LUNACard로 사는

팩토리 패턴

싱글톤 패턴이란? 싱글톤 패턴은 하나의 클래스에 오직 하나의 인스턴스만 가지는 패턴입니다. 싱글톤 패턴의 장점 비용이 적게든다. 싱글톤 패턴의 단점

이 문제는 아주 평범한 배낭에 관한 문제이다.한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.준서가 여행에 필요하다고 생각하는 N개의

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면

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

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

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

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

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

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐

CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당합니다. 프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정합니다. 이 알고리즘은 CPU 이용률은 높게, 주어진 시

멀티프로세싱 멀티프로세싱은 여러 개의 프로세스, 즉 멀티프로세스를 통해 동시에 두 가지 이상의 일을 수행할 수 있는 것을 말합니다. 이를 통해 하나 이상의 일을 병렬로 처리할 수 있으며 특정 프로세스의 메모리, 프로세스 중 일부에 문제가 발생되더라도 다른 프로세스를 이

프로세스(process)는 컴퓨터에서 실행되고 있는 프로그램을 말하며 CPU 스케줄링의 대상이 되는 작업(task)이라는 용어와 거의 같은 의미로 쓰입니다. 스레드는 프로세스 내 작업의 흐름을 지칭합니다. 프로그램이 메모리에 올라가면 프로세스가 되는 인스턴스화가 일어

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

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