nsbg 🌞

🧠 개념특정 노드에서 다른 모든 노드까지의 최단 경로를 탐색하는 알고리즘 ✨ 특징음수 가중치 엣지가 존재하더라도 최단 경로를 구할 수 있음다익스트라 알고리즘은 모든 가중치가 양수인 경우만 처리 가능그래프 전체에서 음수 사이클의 존재 여부를 판단할 수 있음시간 복잡도 O(VE) → 노드 수 V, 엣지 수 E ⚙️ 동작 원리엣지 리스트로 그래프 구현(엣지 중심으로 동작하는 알고리즘이기 때문) 및 최단 경로 리스트 초기화모든 엣지를 확인해 최단 경로 리스트 업데이트최단 경로 리스트를 업데이트하기 위한 반복 횟수는 노드 개수-1 노드 개수가 N이고 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 최대 엣지 개수가 N-1D[s] ≠ ∞ 이고 D[e] > D[s]+w 이면 D[e] = D[s]..

개념자료 간의 연결 형태에 따라 자료구조의 종류를 구별했을 때, 자료를 순차적으로 나열한 형태를 선형 자료구조라고 한다. 하나의 자료 뒤에 다른 하나의 자료가 오는 형식으로 선형 자료구조 안에서도 기본, 제한으로 나뉜다. 이 글에서는 제한 선형 자료구조에 속하는 스택, 큐, 덱에 대해 정리한다.  스택(Stack)  스택, 큐, 덱의 가장 큰 차이점은 데이터의 출입 방향이다. 스택은 데이터가 들어오고 나가는 길이 한 방향 밖에 없어서 데이터를 스택에서 뺄 경우 위의 사진과 같이 들어온 곳으로 나가게 된다. 책을 쌓는 것처럼 아래쪽부터 값이 차곡차곡 쌓이기 때문에 나중에 들어온 데이터가 먼저 나가는 LIFO(Last In First Out, 후입선출) 구조이다. 위 이미지처럼 세로 형태로 스택을 설명하는 ..

개념배열을 둘로 분할하고 분할한 배열을 재귀 호출로 정렬하여 하나의 배열로 만든다는 점이 합병정렬과 비슷하지만, 좌/우를 균등분할하는 것이 아니다. pivot(기준 원소)을 선정하여 pivot보다 작은 원소는 모두 왼쪽 배열로, 크거나 같은 원소는 모두 오른쪽 배열로 가도록 분할한다.* 위의 이미지에서 검은색 배경의 숫자가 pivot 특징▪ 불안정 정렬▪ 비교 정렬(값 비교에 기반한 정렬 알고리즘)▪ 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 위치가 결정되기 때문에 반드시 끝나는 알고리즘이라는 것을 보장 가능 흐름① pivot 선정② [분할] pivot보다 작은 원소들이 앞에 오고, 뒤에는 값이 크거나 같은 모든 원소들이 오도록 배열을 둘로 분할③ [정복] 부분 배열을 정렬(배열의 크기가 충분..

개념문제의 입력 사례를 두 개 이상의 작은 케이스로 분할한 후 분할한 입력의 답을 바로 구할 수 있다면 원래 문제의 답은 분할로 얻은 답들을 통해 구할 수 있는 방식. 상위 입력 사례의 해답을 하위 입력 사례 해답을 이용해 구하기 때문에 하향식(top-down) 풀이 방식에 속한다. 예시1) 이분탐색10121516182025274243이분탐색을 사용하려면 배열이 이미 정렬된 상태여야 한다. 위와 같은 배열에서 27이 배열 안에 있는지 확인한다고 가정하자. ① [분할] 가운데에 위치한 원소를 기준으로 배열을 나누고 찾는 값이 가운데 원소보다 작으면 왼쪽 배열, 크면 오른쪽 배열을 선택② [정복] ①에서 선택한 부분에 찾고자 하는 값이 있는지 재귀적으로 이분 검색③ [병합] ②에서 얻은 답으로 전체에 대한 ..

개념매 순간마다 그 상황에서 가장 최적인 선택을 하는 방식. 각 단계에서 내린 결정이 전체로 봤을 때도 최적일 거라는 보장은 없다.위 사진을 참고하여 세 숫자의 합이 가장 커질 수 있는 경우를 생각해보자. 실제로 가장 큰 수는 109지만 Greedy algorithm의 결과로 나온 값은 25가 된다. 여기서 첫 줄의 '매 순간마다 그 상황에서 가장 최적인 선택을 하는 방식'을 떠올릴 수 있다. Greedy algorithm에 따른 숫자 선택 과정은 아래와 같다. ① 7에서 시작② 3과 12를 만났을 때 더 큰 수인 12 선택(3을 선택할 경우 99로 갈 수 있지만 미래의 선택에 대해서 생각하지 않음)③ 12에서 5, 6을 만났을 때 더 큰 수인 6 선택하지만 탐욕법을 이용해 항상 부분 최적해를 구할 수 ..

Brute-force (=exhaustive search) 컴퓨터의 계산 능력을 이용해 가능한 경우의 수를 모두 나열하면서 답을 찾는 방법 1. 재귀 호출과 완전 탐색 ◽ 재귀 호출 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 과정 재귀 호출에 사용되는 함수가 재귀 함수 ex) 1부터 n까지의 합 Base case : 더 이상 나눌 수 없는 가장 작은 단위의 작업 ex) 1부터 n까지의 합에서 n이 1이면 return 1 존재하는 모든 입력이 base case의 답을 이용해 계산될 수 있도록 base case를 선택해야 함 🔑 Boggle game ① 문제의 분할 ▫ 시작 위치 글자가 주어진 단어 첫 글자와 다르면 False..