계수 정렬 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을대 사용 가능하고, 이 경우에 매우 빠르게 동작한다. 동작 예시 0) 데이터 - List 객체 1) 원소를 모두 순회하여, List 객체의 인덱스에 해당 숫자가 나오면 +1을 해준다. - 원소 '7' - 원소 '5' 2) 모든 원소를 순회한 결과 3) 리스트의 원소를 순회하며 개수만큼 출력한다. 예제코드 public class M12_계수정렬 { public static final int MAX_VALUE = 9; public static void main(String[] args) { int n = 15; // 모든 원소의 값이 0보다 크거나 같다고 가정 int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4,..

퀵 정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. - 가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot 이라고 불린다.)로 설정한다. 동작 예시 0) 0번째 원소 '5'가 피벗이다. 1번째 원소인 '7'은 '5'보다 크고, 마지막 원소인 '8'은 '5'보다 크다. 대신 '8' 앞의 원소인 '4'가 '5'보다 작다. - 따라서 '7'과 '4'의 위치를 바꾼다. 1) 피벗은 그대로 '5'다. 왼쪽에서부터 '5'보다 큰 데이터를 선택한다. 원소 '9'와 오른쪽의 '5'보다 작은 '2'를 바꾼다. 2) 왼쪽에서부터 피벗 '5'보다 큰 데이터는 '6'이고, 오른쪽에서부터 '5'보다 작은 데이터는 '1'이다. - 위치가 엇가리게 되었을 경우 피벗 '5'와..

삽입정렬 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야한다. 구현 예시 0) 0번째 인덱스가 아닌 1번째 인덱스부터 시작한다. 원소 5를 기준으로 자신의 위치 앞의 '7' 원소의 왼쪽/오른쪽 둘 중 선택하여 삽입된다. - 원소 '5'는 원소 '7'보다 작으므로 '7'의 왼쪽에 삽입된다. 1) 2번째 원소인 '9'가 앞의 원소인 '7', '5'의 왼쪽/오른쪽 중 어디로 삽입될지 결정한다. 2) 3번째 원소인 '0'이 앞의 원소 '9', '7', '5' 의 왼쪽/오른쪽 중 어디로 삽입될지 결정한다. 3) 4번째 원소인 '3'이 앞의 원소 '9', '7', '5', '0' 의 왼쪽/오른쪽 중 어디로 삽입될지 결정한다. 4) 이러한 과정이 반복된다. 예제코드 import java.util.st..

선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 구현 예시 0) 정렬할 데이터 1) 0번째 인덱스인 '7'을 대상으로, 1번째 ~ 마지막까지의 인덱스의 원소 중 작은 값을 선택한다. 2) 1번째 인덱스인 '5'를 대상으로, 2번째 ~ 마지막까지의 인덱스의 원소 중 작은 값을 선택한다. 3) 2번째 인덱스인 '9'를 대상으로, 3번째 ~ 마지막까지의 인덱스의 원소 중 가장 작은 값을 선택한다. 4) 이러한 과정을 반복하면 오름차순으로 정렬된다. 예제 코드 import java.util.stream.IntStream; public class M9_선택정렬 { public static void main(String[] args) { int n =..

메모이제이션 (Memoization) 메모이제이션이란, 컴퓨터 프로그램이 동일한 계산을 반복해야할 때, 이전의 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법(Dynamic Programming)의 핵심이 되는 기술이다. 예시 (피보나치 수열) - 앞의 2개의 인덱스 원소의 합이 그 다음 인덱스 원소가 된다. Input : 5 Output : 1 1 2 3 5 0번쨰 + 1번째 = 2번째 원소 1) 1 + 1 = 2 1번째 + 2번째 = 3번째 원소 2) 1 + 2 = 3 2번째 + 3번째 = 4번째 원소 3) 2 + 3 = 5 메모이제이션 구현 코드 public class Memoization { private static ..

이진 탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 탐색 범위를 반으로 좁혀가면서 탐색 - 이진 탐색을 하기 위한 전제 조건(precondition) : 탐색을 실시하기전에 오름차순 정렬이 되어있어야 한다. 동작 예시 0) 오름차순 정렬된 데이터 중에서 값이 4인 원소를 찾아보자. 1) 시작점 0, 끝점 9, 중간점 (9 / 2 = 4) 2) 중간점보다 4가 작으므로 시작점 0, 끝점 3, 중간점 1 3) 중간점보다 4가 크므로 시작점 2, 끝점 3, 중간점 2 예제코드 import java.util.Scanner; public class M14_이진탐색 { public static void main(String[] args) { Scanner sc = new Sc..

들어가기전, 큐 https://devfunny.tistory.com/710 큐 (Queue) 큐 - 선입선출 : 먼저 들어 온 데이터가 먼저 나가는 형식 예제코드 import java.util.LinkedList; import java.util.Queue; /** * Queue */ public class M2_Queue { public static void main(String[] args) {.. devfunny.tistory.com BFS - 너비 우선 탐색 - 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. - 큐 자료구조를 이용한다. [수행 과정] 1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다 2) 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드..

큐 - 선입선출 : 먼저 들어 온 데이터가 먼저 나가는 형식 예제코드 import java.util.LinkedList; import java.util.Queue; /** * Queue */ public class M2_Queue { public static void main(String[] args) { Queue queue = new LinkedList(); queue.offer(5); // push 5 queue.offer(3); // push 3 queue.offer(2); // push 2 queue.poll(); // pop 5 queue.offer(1); // push 1 queue.poll(); // pop 3 while (!queue.isEmpty()) { System.out.printl..

들어가기전, 스택 (Stack) https://devfunny.tistory.com/708 스택 (Stack) 스택 1) 선입후출 : 먼저 들어온 데이터가 나중에 나가는 형식 예제코드 import java.util.Stack; /** * Stack */ public class M1_Stack { public static void main(String[] args) { Stack stack = new Stack.. devfunny.tistory.com DFS - 깊이 우선 탐색 - 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. - 스택 또는 재귀함수를 사용한다. [수행 과정] 1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라..

스택 1) 선입후출 : 먼저 들어온 데이터가 나중에 나가는 형식 예제코드 import java.util.Stack; /** * Stack */ public class M1_Stack { public static void main(String[] args) { Stack stack = new Stack(); stack.push(5); // push 5 stack.push(3); // push 3 stack.push(8); // push 8 stack.pop(); // pop 8 stack.push(2); // push 2 stack.pop(); // pop 2 while(!stack.isEmpty()) { System.out.println(stack.peek()); // 최상위 데이터 peek stack...

구현 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. (구현 유형) - 완전 탐색 : 모든 경우의 수를 다 계산하는 해결 방법 - 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 구현에서의 까다로운 문제 유형 1) 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 2) 특정 소수점 자리까지 출력해야 하는 문제 3) 문자열이 입력으로 주어졌을 대 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 4) 어떻게 풀면 될지 대략 감은 오는데, 막상 코드로 옮기려니 무엇부터 작성해야 할지 모른다. 5) 적절한 라이브러리를 찾아서 사용해야 하는 문제

그리디 알고리즘 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구하며, 이러한 그리디 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야한다. 문제 유형을 분석하기 어렵다면, 해당 문제가 그리디 알고리즘으로 풀이할 수 있는게 아닌건지 생각해봐야한다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 것이므로 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게모르게 제시해준다. 문제 상황 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶다. 1) 일반적인 상황에서 그리디 알고..

lowerBound [1, 1, 2, 2, 2, 2, 3] 의 배열에서 2가 나오는 첫번째 인덱스를 구하고 싶은 경우 ... /** * 처음으로 나오는 target 보다 작은 수 */ private static int lowerBound() { int start = 0; int end = arr.length; // start 가 마지막 인덱스 직전까지 체크되어야한다. while (start < end) { int mid = (start + end) / 2; /* target 이 중간값보다 작거나 같다면, 끝을 중간값으로 */ if (X = arr[mid]) { /* target 이 중간값보다 크거나 같다면, 시작을 중간값 다음으로 */ start = mid + 1; } else { /* target 이 ..

위상 정렬 알고리즘 정렬 알고리즘의 일종이다. 위상 정렬이란, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다. 예시의 상황을 보자. 예시 자바 공부의 커리큘럼에는 순서가 있다. 1) JAVA 2) JSP 3) Spring 이때 우리는 각 과목을 노드로 표현하고, 'JAVA' -> 'JSP'로 이어질 수 있도록 방향성을 갖는 간선을 그릴 수 있다. 다시 말해 그래프 상에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다. 책에서의 예시 1) 자료구조 2) 알고리즘 3) 고급 알고리즘 위 3가지로 구성되어있는 과목 커리큘럼이 있다. '알고리즘'의 선수 과목으로 '자료구조'가 있고, '고급 알고리즘'의 선수 과목으로 '자료구조', ..

신장트리 신장 트리는 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다. 최소 신장트리 최소한의 비용으로 구성되는 신장 트리다. 1) 23 + 13 = 36 2) 23 + 25 = 48 3) 25 + 13 = 38 이 경우, 1)번의 경우가 가장 최소한의 비용으로 연결되므로 최소 신장 트리라고 할 수 있다. 크루스칼 알고리즘 (Kruskal) 최소 신장 트리를 찾는 알고리즘 중 대표적인 알고리즘이 '크루스칼 알고리즘'이다. 크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있는데 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. 먼저..