본문 바로가기

알고리즘 & 자료구조16

[자료구조] 우선순위 큐 (+JAVA) 우선순위 큐일반적인 큐는 FIFO(First In First Out) 구조로 먼저 삽입된 값이 먼저 나오게 되는 구조이다.하지만, 우선순위 큐의 경우 FIFO구조가 아닌 우선순위가 높은 순으로 먼저 나오게 되는 구조를 일컫는다.일반적으로 숫자의 경우 오름차순 및 내림차순을 이용하여 우선순위가 높은 순으로 구현을 하게 되고,객체의 경우 비교할 값을 설정하여 우선순위를 지정하게 된다. 우선순위 큐 선언방법import java.util.PriortyQueue;PriortyQueue pq = new PriorityQueue();객체Wrapper 클래스를 이용하여 기본형들을 사용또는, Custom 객체를 이용하여 사용기본 타입Wrapper 클래스byteByteshortShortintIntegerlongLongfl.. 2024. 12. 2.
그리디 알고리즘 그리디 알고리즘이란?그리디 알고리즘 (욕심쟁이 알고리즘)이란?"매 선택에서 지금 이순간 당장 최적의 답을 선택하여, 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘이다.그리디 알고리즘을 선택하면, 매 선택이 그 순간에 대해서는 최적의답이지만 그걸 종합적으로 확인해보면 최적이라는 보장이 있지 않다.즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해일 때 사용해야하는 알고리즘 그리디 알고리즘 핵심 이론그리디 알고리즘 수행과정1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약조건에 벗어나지 않는지 검사3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다.(전.. 2024. 11. 26.
이진탐색 이진탐색이란?원하는 데이터를 빠르게 찾기 위한 알고리즘이진 탐색은 데이터가 정렬되어있는 상태에서 중앙값을 이용해서 찾고자 하는 값과 비교해가며 찾는 알고리즘(코딩테스트에서 부분 문제로 많이 출제 됨)기능특징시간복잡도Target 데이터 탐색중앙값 비교를 통한 대상 축소 방식O(logN) 이진탐색 핵심이론pre) 오름차순으로 정렬현재 데이터 셋에서 중앙값을 설정한다중앙값 > Target 값 일때, 중앙값 기준으로 왼쪽 데이터 셋 설정중앙값 1~3을 반복하다가, 중앙값 == Target 일때 탐색 종료 EX) 48을 찾아라20303340 454850xxxx454850xxxxx48 (탐색 종료)50 이진탐색 구현import java.util.Arrays;public class App { public sta.. 2024. 11. 21.
[BFS] 너비 우선 탐색 너비우선탐색(BFS) 이란?그래프를 완전탐색하는 방법 중 하나로,시작 노드에서 시작해 가장 가까운 노드를 먼저 탐색하면서 탐색하는 알고리즘FIFO 구조로 탐색을 하며, 목표 노드에 도착하는 경로가 여러개 일 경우 최단경로를 보장한다.시간복잡도 O(노드 수 + 에지 수)로 이루어져 있다. 너비우선탐색의 핵심이론DFS와 마찬가지로 방문한 노드의 경우 체크하는 배열이 필요.또한, 인접 리스트를 구현하여 에지로 구성되어있는 배열을 구현해야함DFS와 다른점이 있다면, 스택으로 제거하는 것이 아닌 큐의 형태로 먼저 들어온 순서부터 제거하며 삽입 및 삭제를 진행.과정첫번째 노드부터 큐에 삽입하여, 큐를 시작하고 인접해 있는 노드를 차례대로 큐에 삽입한다큐에 먼저 들어간 노드부터 삭제하며, 인접한 노드들이 있다면 차례.. 2024. 11. 18.
소수 찾기 에라토스테네스의 체수학자 에라토스테네스가 발견한 소수를 찾는 방법을 일컫는다.2,3,5,7을 제외한 해당 수의 배수를 제거하면, 소수인 숫자를 찾을 수 있다. 에라토스테네스의 체 과정한 자리 수의 소수 인 경우는 2,3,5,7이다. 해당 수의 경우에는 소수이므로 따로 저장2의 배수를 가지는 수는 소수가 아니므로 모두 제거3의 배수를 가지는 수는 소수가 아니므로 모두 제거5의 배수를 가지는 수는 소수가 아니므로 모두 제거7의 배수를 가지는 수는 소수가 아니므로 모두 제거위의 과정에서 2,3,5,7를 제외한 해당수의 배수가 아닌 수를 구함해당 숫자들이 소수 구현public class App { public static void main(String[] args) throws Exception { .. 2024. 11. 16.
[탐색] 깊이우선탐색 깊이 우선 탐색이란?그래프 완전 탐색 기법 중 하나이며,그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 진행하는 알고리즘기능특징시간복잡도그래프완전탐색- 재귀함수로 구현- 스택 자료구조 이용O(노드 개수 + Edge 개수) 깊이우선 탐색 주의할점재귀함수를 이용하므로, 스택 오버플로우에 주의해아한다주로 사용되는 문제 유형 : 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬 깊이우선 탐색 핵심 이론한 번 방문한 노드를 다시 방문하면 안됨후입선출(LIFO) 구조를 가진다 (스택 사용)이론을 이용하기 위해서, 스택으로 구현한 것이며 주로 재귀함수를 이용하여 사용한다방문할 스택 + 방문한 곳 저장할 배열탐색 순서 : 1 -> 3 -.. 2024. 11. 15.

티스토리툴바