벨만-포드 알고리즘 (Bellman-Ford)알고리즘 개요하나의 출발점에서 나머지 모든 정점까지 최단 경로를 찾는 알고리즘데이크스트라 알고리즘은 음의 가중치를 가진 간선이 있으면 사용할 수 없지만, 벨만-포드는 음의 가중치가 있더라도 최단 경로를 찾을 수 있다 음의 사이클(전체 경로의 가중치 합이 음수인 순환)이 존재하면 최단 경로가 정의될 수 없으므로 사용할 수 없음 동작 방식 그래프의 모든 간선들을 확인하며, 출발점으로부터 각 정점까지의 최소 거리를 반복적으로 갱신정점의 수(|V|)가 n개라면, 최대 (n-1)번 동안 전체 간선을 확인하여 최소 거리를 업데이트매 반복마다 아래 식으로 거리 값을 갱신여기서 d[v]는 출발점에서 정점 v까지의 현재 최단 거리w(u, v)는 정점 u에서 v로 가는 간선의 ..

최소 신장 트리(Minimum Spanning Tree) 신장 트리가중 무방향 그래프에서 모든 정점을 포함하는 트리최소 신장 트리신장 트리 중 간선 가중치의 합이 가장 작은 트리그래프 G=(V,E) 에 대해, 트리 G′=(V′,E′)는 V′=V, E′⊆E 크루스칼 알고리즘간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 골라서 사이클을 형성하지 않으면 해당 간선을 추가하는 방식간선 (u,v)의 두 정점 u,v가 서로 다른 연결 성분에 속하면 해당 간선은 사이클을 형성하지 않음|V|=n개의 정점이 각각의 서로 다른 연결 성분으로 구성된 상태에서 시작해서 간선을 추가할 때마다 연결 성분들이 하나씩 합쳐지고 최종적으로 하나의 연결 성분을 형성함 과정 그래프의 모든 간선을 가중치 기..

그래프의 기본G =(V, E) 그래프 G는 정점(Vertex)와 간선(Edge)으로 구성된다V: 정점(vertex)의 집합E: 간선(edge)의 집합 그래프 구현 방법인접 행렬 정점을 2차원 배열로 표현행과 열에 해당하는 두 정점 사이에 간선이 있으면 1(또는 가중치), 없으면 0공간복잡도 O(V^2) 정점수가 많으면 메모리 낭비 특정 두 정점간 연결 여부를 O(1)로 확인 정점: 0, 1, 2간선: (0-1), (1-2)인접 행렬:[ [0, 1, 0], [1, 0, 1], [0, 1, 0]] 인접 리스트각 정점마다 연결된 정점 리스트를 별도로 저장공간복잡도 O(V + E) (간선 수 만큼 메모리 사용 > 희소 그래프에 적합)정점마다 연결된 간선만 확인해 효율적임 0: [1]1: [0, 2]2: [1..

탐색이란여러개의 원소로 구성된 데이터에서 원하는 값을 갖는 원소를 찾는 과정 순차탐색리스트의 처음부터 끝까지 하나씩 차례로 원소를 확인하면서 원하는 값을 찾는 방식성능과 특징탐색 (Search)원하는 원소를 찾기 위해 리스트의 앞에서부터 하나씩 비교→ 최악의 경우 O(n)삽입 (Insert)리스트의 끝에 추가할 경우는 O(1)(단, 특정 위치에 삽입하면 O(n))삭제 (Delete)특정 원소를 삭제한 뒤 뒤 원소들을 앞으로 당겨야 하므로 O(n)정렬되지 않고 크기가 작은 데이터에 적합, 데이터가 큰경우 부적합 이진탐색 정렬된 리스트에서 원하는 값을 찾기 위해, 매번 탐색 범위를 절반으로 줄여나가는 방식대표적인 분할 정복(Divide and Conquer) 전략 기반 알고리즘탐색방법 리스트의 중간값을 확..

힙 정렬(Heap sort)힙 정렬 개념힙(Heap) 자료구조를 이용한 정렬 알고리즘완전 이진트리 형태로, 특히 최대 힙은 모든 부모 노드가 자식 노드들보다 크거나 같은 값을 갖도록 구성된 트리힙은 임의의 값 삽입 및 최댓값 삭제가 용이함일차원 배열로 구현하여 효율적인 접근 가능초기 힙 생성 방법 1 삽입을 반복하여 힙 구축하기 (상향식)주어진 배열의 원소를 차례로 하나씩 빈 힙에 삽입하면서 최대 힙을 구성하는 방식 춴소를 추가할 때마다 최대 힙 조건을 유지하도록 삽입위치 찾아 힙을 재구성하는 과정이 필요각 원소를 삽입하면서 위쪽(루트방향) 으로 이동하며 힙 성질을 만족시키도록 조정하는 방식 1. 빈 힙에 30 삽입→ [30]2. 45 삽입 (부모와 비교, 더 크므로 교환)→ [45, 30]3. 20 삽..

퀵정렬분할정복 방식으로 동작하는 정렬 알고리즘으로 하나의 배열을 특정기준(pivot) 중심으로 작은 값과 큰값으로 나누고, 나눠진 배열에 재귀적으로 졍렬 반복 동작원리Pivot(피벗): 배열을 나누는 기준이 되는 값. 보통 배열의 첫 번째 요소를 피벗으로 사용하지만, 임의로 선택할 수도 있음분할(Divide): 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시켜 피벗이 제자리를 찾도록 정렬정복(Conquer): 나눠진 두 부분 배열을 다시 퀵 정렬로 정렬.재귀적으로 반복하면서 전체 배열을 정렬하게 됩니다.입력 배열: 30 45 20 15 40 25 35 10피벗: 30→ 분할 후: 25 10 20 15 30 40 35 45설명:- 피벗 30 기준- 30보다 작은 값들: 25 10 20 15 → 왼쪽-..

정렬주어진 데이터를 값의 크기 순서에 따라 재배치 하는것 (오름/내림차순)내부 정렬 정렬한 전체 데이터를 주기억장치에 저장한 후 정렬하는 방식비교기반데이터 분포 기반두 데이터 값 전체를 비교해 어떤값이 큰지 작은지 결정하여 정렬데이터의 분포 정보를 활용해 정렬 선택, 버블, 삽입, 셸, 합병, 퀵, 힙 정렬계수, 기수, 버킷 안정적 Stable 정렬같은 값을 갖는 데이터에 대한 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 방식입력5 1 2 3 6 2 4 정렬 후1 2 2 3 4 5 6 (안정)1 2 2 3 4 5 6 (불안정) 제자리 정렬 in-place입력 배열 이외에 별도로 필요한 저장 공간이 상수 개를 넘지 않는 정렬 입력 크기 n이 증가해도 추가적인 저장 공간 사용하지 않음 선택 ..

1. 알고리즘 분석정확성 분석 유효한 입력에 대해 일정 시간내에 정확한 결과의 생성 여부 효율성 분석 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정/평가공간 복잡도 (space complexity): 메모리의 양 = 정적 공간 + 동적 공간시간 복잡도: 수행시간 = 알고리즘의 실행에서부터 완료까지 걸리는 시간 시간 복잡도알고리즘 수행시간 = Σ{각 연산이 수행되는 횟수}수행 시간에 영향을 미치는 요인 입력크기 (리스트 원소의 개수, 행렬의 크기 등)입력크기 n이 커질수록 수행시간 증가 > 입력크기 n의 함수 f(n)으로 표현 입력 데이터의 상태 S(n) : 크기 n인 입력들의 집합 P(i) : 입력 i가 발생할 확률T(i) : 입력 i 에 대한 알고리즘의 수행시간평균 수행시간 $$ A(n) = \sum..

백트래킹이란 일반적으로 모든 가능한 해를 시도해보며, 조건을 만족하는 해를 찾는 알고리즘이다. 조건을 만족하지 않으면 이전 단계로 돌아가서 다른 가능성을 시도하하기 때문에 "백트래킹(backtrack)"이라고 한다. DFS는 모든 경로를 탐색하는데 백트래킹은 조건이 있어 모든 경로가 아닌 조건에 맞는 경로만 탐색한다는 차이점이 있다. 이전상태로 돌아오는 작업이 필요하기 때문에 스택(혹은 재귀)를 사용하는 DFS를 이용해서 주로 구현한다. DFS를 이용한다면 기본적으로 구성은 비슷하다. 탐색을 멈출 조건문이 제일 처음에 들어가고, 모든 노드 방문을 위한 반복문, 내부에서 본인을 재귀 호출, 요구사항에 맞는 값 리스트에 추가해서 리턴하거나 프린트 말로만 설명하면 헷갈리니까 리트코드에서 예제를 하나 가져와서 ..