Sort
Sorting Algorithm 선택 정렬 (Selection Sort) 선택 정렬은 이름에 맞게 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 현재 위치에 저장될 값의 크기가 작냐, ...
Post about Algorithm
자료구조 & 알고리즘에 대한 포스트들입니다.
Hash Algorithm
Hash Algorithm 해쉬란? 해쉬는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다 즉 해쉬 알고리즘은 해쉬를 하는 방법에 대해 절차적으로 명세한다 이를 이용해 특정한 배열의 인덱스나 위치를 입력하고 하는 데이터의 값을 이용해 저장...
Data Structure
Q0. 배열(array)에 대해서 설명하시오 고정된 크기를 갖고 순서대로 번호가 붙은 같은 자료형의 원소들이 연속적인 형태로 구성된 자료구조입니다. 이때 각 원소에 붙은 번호를 흔히 인덱스(index)라고 부릅니다. 원소들이 연속적으로 메모리에 배치되어있기 때문에 임의의 첨자를 ...
Kruskal Algorithm
Kruskal Algorithm 개념 최소 비용 신장 트리를 찾는 알고리즘이다. 사이클을 형성하지 않는 그래프를 가리켜 신장 트리라고 한다. 신장 트리는 그래프의 모든 정점이 간선에 의해서 하나로 연결되어 있다. 신장 트리는 그래프...
Floyd-Warshall Algorithm
Floyd-Warshall Algorithm 개념 플로이드-워셜 알고리즘은 모든 최단경로를 구하는 방법이다. 플로이드-워셜 알고리즘에서는 음의 가중치를 가진 간선도 쓸 수 있다. 모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는 2차원 배열이 된다. ...
Dijkstra Algorithm
Dijkstra Algorithm 개념 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구한다. 간선들은 모두 양의 간선들을 가져야 한다. 다익스트라 알고리즘의 기본 로직은, 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며, 최단 거리를...
DFS, BFS
깊이 우선 탐색 (DFS, Depth-First Search) 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다...
Other Algorithms
피보나치 수열 재귀방식 - $O(2^n)$ 재귀는 연속 함수 호출로 인한 스택 오버플로우가 발생할 가능성이 높다. public int recurFibo(int i) { if (i <= 1) { return i; } else { ...