[알고리즘] 그래프 알고리즘

1. 최소 신장 트리1) 정의신장트리란 가중 무방향 그래프에서 모든 정점을 포함하는 트리를 의미합니다. 즉 정점이 n개라면 트리에는 n-1개의 간선이 존재합니다.  이 중 최소(비용) 신장 트리는 아래와 같은 정의를 만족하는 트리입니다.2) 최소 신장 트리를 구하는 알고리즘모든 간선 중에서 정점을 모두 연결하면서 가중치의 합을 가장 작게 만드는 (n-1)개의 간선을 고르는 과정이라고 할 수 있습니다. Greedy_MST ( G ) { T ← Ø ; // 최소 신장 트리의 간선 집합 while ( T가 신장 트리를 만들지 않았음 ) { 최선의 간선 (u, v) 선택; T ← T ∪ { (u, v) }; } return (T); }위 코드에서 최선의 간선이라는 것은 사이클을 형성하지 않으며 ..

• format_list_bulleted 알고리즘
• · 2024. 5. 20.
• textsms

[알고리즘] 그래프의 기본 개념과 순회

1. 그래프란? 1) 그래프에서 사용되는 주요 용어1] 인접, 부수두 정점 x,y 사이에 간선이 있으면 정점 x와 y는 인접한다고 하며, 해당간선은 정점 x와 y에 부수되었다고 합니다.2] 부분 그래프원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프를 부분 그래프라고 합니다. 위 그림에서 G2는 G1의 부분 그래프라고 할 수 있습니다.3] 경로그래프에서 정점 v1으로부터 vn까지의 경로란 간선 (v1,v2), (v2,v3),....,(v(n-1),vn) 으로 연결된 v1,v2,...,vn을 의미하며 이 때 경로상의 존재하는 간선의 개수를 경로의 길이라고 합니다.4]차수해당 정점에 부수된 간선의 수를 의미하며, 방향 그래프에서는 이러한 차수를 세분화하여 정점으로 들어오는 간선의 수를 진입차수라..

• format_list_bulleted 알고리즘
• · 2024. 5. 13.
• textsms

[알고리즘] 탐색

탐색이란 여러개의 원소로 구성된 데이터에서 원하는 값을 갖는 원소를 찾는 것을 의미합니다. 이때 주어진 데이터의 형태는 리스트, 트리, 그래프 등이 있고, 탐색 중에서도 내부탐색, 외부탐색이 있습니다.  그리고 탐색을 할때는 초기화, 삽입, 삭제 등 관련 연산등도 고려해야 합니다. 이러한 탐색방법에는 리스트형태(순차 탐색, 이진탐색), 트리형태(이진탐색트리, 2-3-4 트리, 레드-블랙 트리, B-트리), 해시테이블(해시 함수) 등이 있습니다. 1. 순차탐색리스트 형태로 주어진 원소들을 처음부터 하나씩 차례로(순차) 비교하면서 원하는 값을 갖는 원소를 찾는 방법입니다.1) 탐색연산의 알고리즘 SequentialSearch(A[],n,x) // A[] : 입력배열, n: 입력크기(탐색할 데이터의 개수), ..

• format_list_bulleted 알고리즘
• · 2024. 4. 27.
• textsms

[알고리즘] 데이터 분포 기반 알고리즘

데이터 분포기반 알고리즘은 이미 얻어진 데이터 분포정보를 활용하는 정렬 알고리즘입니다. 이러한 데이터 분포 기반 알고리즘에는 계수정렬, 기수정렬, 버킷정렬 등이 있으며 선형시간 O(n)이 가능합니다. 데이터 분포기반 알고리즘의 단점으로는 입력값의 범위를 미리 알아야 하며 특정조건에 맞게 제한적으로만 사용 가능하기 때문에 보편적이지 못한 정렬 알고리즘이 됩니다.1. 계수정렬주어진 데이터 중에서 자신보다 작거나 같은 값을 같는 데이터의 개수를 계산하여 정렬할 위치를 찾아 정렬하는 방식입니다. 계수정렬은 입력값이 어떤 작은 정수 범위내에 있다는 것을 알고있는 경우에만 적용가능합니다. k보다 작거나 같은 값을 갖는 데이터의 개수를 알고 있을 때 이 데이터의 개수의 의미는 정렬 순서상 k의 마지막 위치를 의미합니..

• format_list_bulleted 알고리즘
• · 2024. 4. 27.
• textsms

[알고리즘] 비교 기반 알고리즘

내부정렬이란 정렬 중 전체데이터를 주기억 장치에 저장한 후 정렬을 수행하는 방식의 정렬입니다. 이러한 내부정렬에는 정렬방식에 따라 비교 기반 알고리즘과 데이터 분포 기반 알고리즘으로 나눌 수 있습니다. 비교 기반 알고리즘은 직접적인 데이터 비교를 통해 알고리즘을 수행하는 방식입니다. 이러한 비교 기반 알고리즘의 종류에는 선택정렬, 버블정렬, 삽입정렬, 셸정렬, 퀵정렬, 합병정렬, 힙정렬 등이 있습니다. 비교 기반의 알고리즘의 성능을 측정하는 방법은 키값의 비교횟수가 적으면 성능이 좋다고 할 수 있습니다. 비교 기반 알고리즘 중 선택정렬, 버블정렬, 삽입정렬, 셸정렬은 시간복잡도가 O(n^2)이며 퀵 정렬, 합병정렬, 힙정렬의 시간복잡도는 O(nlogn)입니다. 1. 선택정렬선택정렬은 입력배열에서 가장 작..

• format_list_bulleted 알고리즘
• · 2024. 4. 27.
• textsms

[알고리즘] 정렬 관련 개념

1. 안정적 정렬안정적인 정렬이란 동일한 값을 갖는 데이터가 여러개 있을 때 정렬전의 상대적위치가 정렬후에도 그대로 유지되는 정렬을 의미합니다. 예컨대 입력데이터가 아래와 같이 존재한다고 가정해 보겠습니다.10,20,30,50,40,20,60 위에 정렬전 데이터에는 동일한 데이터인 20이 존재합니다. 앞의 20을 A 뒤의 20을 B라고 하겠습니다. 데이터를 정렬하면 아래의 두가지 케이스로 나뉠 수 있습니다.10,20(A),20(B),30,40,50,60 10,20(B),20(A),30,40,50,60 위의 첫번째 케이스를 '안정적'이라고 하고 두번째 케이스를 '불안정적'이라고 합니다. 따라서 안정적인 정렬이란 첫번째 케이스처럼 정렬되는 것을 의미합니다. 2. 제자리 정렬입력 배열이외의 별도로 필요한 저장..

• format_list_bulleted 알고리즘
• · 2024. 4. 27.
• textsms

[알고리즘] 분석

1) 정확성 분석유효한 입력에 대해 유한시간 내에 정확한 결과를 만들어 내는지 확인하는 것입니다.이러한 확인은 수학적 기법을 사용하여 이론적으로 증명합니다. 2) 효율성 분석효율성 분석은 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정, 평가하는 것입니다.이러한 효율성 분석에는 공간복잡도, 시간복잡도가 있습니다. 1. 공간복잡도컴파일하는 시점에서 발생하는 메모리와 알고리즘을 수행할때 필요한 메모리가 있는데 이러한 총 메모리양이 필요한지 측정하는 것입니다. 2. 시간복잡도시간 복잡도는 알고리즘의 실행부터 완료까지 걸리는 시간을 분석하는 것입니다. 알고리즘의 수행시간은 각 연산이 수행되는 횟수의 합이라고 볼 수 있습니다이러한 수행시간에 영향을 미치는 요인에는 여러가지가 있습니다. 첫번째로 입력크기 입니다.예..

• format_list_bulleted 알고리즘
• · 2024. 4. 27.
• textsms

알고리즘 개요

1. 알고리즘이란?주어진 문제를 해결하거나 함수를 계산하기 위해 따라야 할 명령어들을 단계적으로 나열한 것이라고 할 수 있습니다. 2. 알고리즘을 만족하기 위한 조건1. 입출력 : 0개 이상의 외부입력과 1개 이상의 출력을 생성해야 합니다.2. 명확성 : 각 명령은 모호하지 않고 단순 명확해야 합니다.3. 유한성 : 한정된 수의 단계를 거친 후에는 반드시 종료해야 합니다.4. 유효성 : 모든 명령은 컴퓨터에서 수행할 수 있어야 합니다.5. 효율성 : 효율성은 알고리즘을 만족하기 위한 필수 조건은 아닙니다. 그러나 실용적관점에서는 효율성도 상당히 중요합니다. 왜냐하면 알고리즘을 구성하더라도 무한한 시간이 걸린다면 문제해결을 할 수 없다고 볼 수 있기 때문입니다.3. 알고리즘의 생성단계1) 설계일반적/ 범용..

• format_list_bulleted 알고리즘
• · 2024. 4. 27.
• textsms