알고리즘 개념정리

이진 탐색

이진 탐색 알고리즘 오름차순 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 시간 복잡도: O(logN) 동작 과정 0) 오름차순 정렬된 데이터에서 값이 '4'인 원소 찾기 1) 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거) 2) 중간점보다 4가 작으므로 시작점: 0, 끝점: 3, 중간점: 1 3) 중간점보다 4가 크므로 시작점: 2, 끝점: 3, 중간점: 2 예제코드 반복 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in..

퀵 정렬

퀵 정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다. 시간 복잡도 평균의 경우: O(NlogN) 최악의 경우: O(N^2) 동작 과정 0) 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다. 1) 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '9'가 선택되고 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '2'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다. 2) 현재 피벗의 값은 '..

삽입 정렬

삽입 정렬 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다. 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 최선의 경우 O(N) 시간 복잡도: O(n^2) 구현 과정 0) 첫 번째 데이터 '7'은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈지 판단한다. '7'의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재한다. 1) 이어서 '9'가 어떤 위치로 들어갈지 판단한다. 2) 이어서 '0'이 어떤 위치로 들어갈지 판단한다. 3) 이어서 '3'이 어떤 위치로 들어갈지 판단한다. 4) 이러한 과정을 반복하며 정렬이 완료된다. 예..

선택 정렬

선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 시간 복잡도: O(n^2) 선택 정렬 동작 과정 0) 정렬할 데이터를 준비 1) 처리되지 않은 데이터 중 가장 작은 값인 '0'을 선택하여 가장 앞의 '7'과 바꾼다. 2) 처리되지 않은 데이터 중 가장 작은 값인 '1'을 선택하여 가장 앞의 '5'과 바꾼다. 3) 처리되지 않은 데이터 중 가장 작은 값인 '2'를 선택하여 가장 앞의 '9'과 바꾼다. 4) 처리되지 않은 데이터 중 가장 작은 값인 '3'을 선택하여 가장 앞의 '7'과 바꾼다. 5) 이러한 과정을 반복하면 다음과 같이 정렬이 된다. 구현 코드 import java.util.*; public class Main { public s..

BFS (Breadth-First Search)

BFS BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. BFS는 최단거리, 또는 최소횟수를 구하라는 문제에서 사용된다. BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. BFS 동작 과정 0) 아래의 그래프를 번호가 낮은 인접 노드부터 순서대로 방문한다. 1) 노드 '1'을 큐에 삽입하고 방문한다. 2) 노드 '1'을 꺼낸 뒤, 노드 '1'가 방문하지 않은 인접 노드인 노드 '2', '3', '8'을 큐에 삽입하..

DFS (Depth-First Search)

DFS DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 문제가 어떤 경우의 수를 구한다거나 하면 사용한다. DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. DFS 동작 과정 0) 아래의 그래프를 번호가 낮은 인접 노드부터 순서대로 방문한다. 1) 노드 '1' 방문 2) 노드 '1'이 방문하지 않은 인접 노드 '2', '3', '8..

큐 (Queue)

큐 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다. 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다. 예제 코드 import java.util.LinkedList; //import import java.util.Queue; //import public class Main { public static void main(String[] args) { Queue q = new LinkedList(); //int형 queue 선언, linkedlist 이용 queue.add(1); // queue에 값 1 추가 queue.add(2); // queue에 값 2 추가 queue.offer(3); // queue에 값 3 추가 queue.poll(); // queue에..

스택 (Stack)

스택 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다 예제코드 import java.util.Stack; //import public class Main { public static void main(String[] args) { Stack stack = new Stack(); //정수형 스택 선언 stack.push(1); //stack에 값 1 추가 stack.push(2); //stack에 값 2 추가 stack.push(3); //stack에 값 3 추가 stack.pop(); //stack에 값 제거 stack.clear(); //stack의 전체 값 제거 (초기화) stack.peek(); //stack의 가장 상단의 값 반환 stack.size(); //stack의 크기 ..