최소 신장 트리 그래프에서 모든 노드를 연결할 때 사용된 Edge들의 가중치의 합을 최소로 하는 트리이다. 특징 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다. N개의 노드가 있을 때 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개이다. 핵심 이론 모든 Edge들을 '가중치'를 기준으로 오름차순 정렬 후, 가중치가 낮은 Edge부터 연결한다. 이때 사이클이 형성되지 않을 때만 연결한다. 1. Edge 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기 그래프를 Edge 중심 형태로 Edge 리스트로 저장한다. edge class는 시작 노드, 끝 노드, 가중치로 구성된다. 사이클 여부를 확인하기 위해 유니온 파인드 배열(parent)를 인덱스의 값으로 초기화..

벨만-포드 알고리즘 벨만-포드 알고리즘 한 정점에서 다른 모든 정점간의 최단 거리를 구하는 알고리즘이다. 특징 • 음의 간선을 포함하는 그래프에서 사용한다. • 음의 사이클의 존재여부를 판단할 수 있다. 시간 복잡도 • O(VE) - V : 정점의 개수 E : 간선의 개수 주요 아이디어 노드의 수가 N개일 때 N-1번 동안 모든 Edge를 탐색하면서 최단 경로를 구한다. 그러므로 시간 복잡도가 O(VE)이다. 아무리 멀리 떨어진 노드라고 할지라도 N-1개의 간선을 지나면 어떠한 노드라도 도달할 수 있다. 그래서 벨만 포드 알고리즘은 보통 N-1번만큼 반복하여 최단경로를 알아낸다. 또한 벨만 포드 알고리즘은 주로 음의 사이클 존재 여부를 판단할 때 더 많이 쓰인다. 이때는 N번만큼 반복하며 N번일 때 최단..

본 포스팅은 Do it! 알고리즘 코딩 테스트 : 자바편을 참고하여 작성되었습니다. 유니온 파인드 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘이다. 핵심 이론 union, find 연산 union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a,b가 a ∈ A, b ∈ B일 때 union(a,b)는 A ∪ B이다. find 연산 : 특정 노드 a에 관해 a가 속합 집합의 대표노드를 반환하는 연산이다. 노드 a가 a ∈ A일 때 find(a)는 A집합의 대표 노드를 반환한다. 알고리즘 구현 방법 ❶ 유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것이다..

1. 서론 이분 탐색 알고리즘 관련 문제를 풀다가 잘 이해가 안되는 부분이 2가지 있었는데 바로 원하는 값과 탐색 값이 같을 때 어디서 처리를 해야할지, 두 번째로 low와 high값 중 어떤 것을 결과로 선택 해야할지이다. 여러 블로그들을 방문하여 내가 고민했던 문제를 어떻게 생각했는지 알아봤는데 설명이 잘 되어있는 블로그에서는 대부분 Lower bound와 Upeer bound 중 하나를 선택해서 구현했다. 그래서 이 두 개념에 대해 알아보고자 한다! 2. Lower bound Lower bound 알고리즘 찾고자 하는 값(크거나 같은)의 시작위치를 알아낸다. 시간 복잡도 : O(logn) 2.1 동작 방식 1. 배열의 중간 값을 가져온다. 2. 중간 값과 검색값을 비교한다. 중간 값이 검색 값보다 ..

DFS DFS는 깊이 우선 탐색으로, 한 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 검색 속도 자체는 BFS에 비해 느리지만 조금 더 간단하다. 스택 혹은 재귀함수를 이용하여 구현한다. class Graph{ private int V; private LinkedList adj[]; Graph(int v){ V = v; adj = new LinkedList[v]; for(int i=0; i

합병 정렬 개념 리스트를 두 개의 균등한 크기로 분할하고 분할된 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하기를 반복하면서 전체를 정렬한다. 분할 정복 기법 알고리즘 중 하나이다. 분할 정복 기법 (divide and conquer) 문제를 작은 2개의 문제로 분리하고 각 문제를 해결 후, 결과를 모아서 원래의 문제를 해결하는 전략 구체적인 알고리즘 합병 정렬은 다음 3가지 단계를 반복하며 정렬을 한다. 분할(Divide) : 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 충분히 작아질 때까지 분할을 반복한다. 결합(Combine): 정렬된 부분 배열들을 하나의 배열로 통합한다. 부분 리스트의 크기가 1개가..

알고리즘 퀵 정렬은 기준값(pivot)을 선정해 해당 값도가 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 평균적인 시간 복잡도는 O(nlogn)으로 다른 O(nlogn)의 알고리즘 중 가장 빠르다고 평가 된다. 구체적인 내용 기준점을 정하고 기준점을 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 이동 시키며 정렬을 진행 한다. 이때 기준점이 되는 레코드는 한 번 정렬이 완료되면 더 이상 자리가 바뀌지 않는다. partition 함수를 통해 피봇을 기준으로 왼쪽, 오른쪽을 나누게 된다. 최종적으로 피봇의 위치는 low가 higt보다 커지는 순간으로 결정된다. 이렇게 피봇을 기준으로 한 번 정렬된 리스트는 다시 왼쪽, 오르쪽 리스트로 쪼개져 partition 함수를 호출하며 리스..

알고리즘 손 안의 카드 정렬을 하는 것과 유사하다. 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입! 왼쪽 리스트에 정렬이 완료된 요소를 1개, 2개 점점 개수를 늘려가면서 정렬이 완료된다. 구체적인 알고리즘 1. 인덱스 1부터 시작한다. 2. 현재 삽입될 요소인 i번째 요소를 key 변수에 복사 3. i-1번째 부터 역순으로 조사 4. j가 0보다 작아지거나 key값보다 정렬된 배열에 있는 값이 크면 5. j번째는 j+1번째로 이동한다. 6. j를 하나 감소한다. 7. j번째 정수가 key보다 작으므로 j+1번째가 key값이 들어갈 위치이다. 코드 // 정렬 - 삽입 정렬 int i,j; for(i= 1; i=0&&num..

알고리즘 개념 인접한 2개의 레코드를 비교하며 정렬 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환 1회전이 돌때 마다 정렬이 완료된 레코드가 가장 오른쪽에 1개씩 추가됨 코드 - Java // buble sort for(int i = N-1; i >=0 ; i--) { int chage = 0; for(int j=0; j arr[j+1]) { chage++; int tem = arr[j]; arr[j] = arr[j+1]; arr[j+1]= tem; } } if(chage == 0) break; } 시간 복잡도 분석 비교 횟수 (n-1) + (n-2) .. 2 + 1 = (n * (n+1)) / 2 시간 복잡도: O(n^2) 최선, 평균, 최악 모두 같다. 이동 횟수 최악의 ..

선택 정렬 개념 제자리 정렬 (in-place sorting)이다. 입력 배열 외에는 추가 메모리를 요구하지 않는 정렬이다. 정렬된 해당 요소가 넣어질 위치가 정해져 있다. 자료 이동 횟수가 미리 결정된다. → n-2번 구체적인 설명 선택 정렬이란 첫 번째 위치부터 차례대로 정렬이 안된 요소 중 가장 작은 것(큰 것)을 선택하여 위치를 교환하여 점점 정렬을 완료해나가는 기법이다. 첫번째 루프일 때 첫번 째 요소를 두번 째 요소부터 마지막 요소까지 비교하여 가장 작은 값을 찾으면 해당 요소와 교환한다. 두번 째 루프일 때 두번 째 자료를 세번 째 요소 부터 마지막 요소까지 비교하여 가장 작은 요소를 찾으면 해당 요소와 교환한다. 이렇게 n-1 요소까지 반복한다. 시간 복잡도 비교 횟수 (n-1) + (n-..