은로그
[자료구조] Java 우선순위 큐(Priority Queue)
우선순위 큐(Priority Queue) Priority Queue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이며, 힙(Heap)이라고도 부른다. 일반적인 큐의 구조 FIFO (First In First Out)을 가진다. 우선순위를 먼저 결정하고, 우선순위가 높은 데이터가 먼저 나가는 구조이다. Heap을 이용하여 구현하는 것이 일반적이다. 데이터 추출 시, 루트 노드를 얻어 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입 후 아래 노드로 내려가면서 정렬하는 방식으로 진행된다. 최대 힙 = 최대 값이 우선..
[필수 알고리즘] 그리디 알고리즘(Greedy Algorithm) 이해
그리디 알고리즘 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란, "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 루트 노드부터 시작하여 거쳐 가는 노드 값의 최대로 구한다면, 값은 5+7+9 = 21로 다음과 같지만 거쳐가는 노드의 경우에서 가장 큰 값(최적의 값만) 구한다면, 값은 5+10+4 = 19 가 된다. 이처럼, 그리디 알고리즘은 최적의 값을 도출해내지 못하지만 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다. 그리디 알고리즘 기법 활용..
[필수 알고리즘] 이분 탐색(Binary Search) 이해
이분/이진 탐색 Binary Search 정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제. 이진 탐색은 오름차순으로 정렬된 리스트에서 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있다. 이진 탐색 기법 활용 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 사용한다. 이때, 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 배열의 중간 값을 가져온다. 중간 값과 검색 값을 비교한다. 중간 값이 검색 값과 같다면 종료한다. (..
[필수 알고리즘] 동적계획법 DP (Dynamic Programming) 이해
동적계획법 DP (Dynamic Programming) 동적 계획법은 프로그래밍 대회 문제에 자주 출현하는 알고리즘 기법 중 하나이며, 프로그램이 실행되는 도중, 실행에 필요한 메모리를 기억하여 할당하는 기법을 의미한다. : 큰 문제를 작은 문제로 나눈 뒤, 기억하여 푸는 기법 공간복잡도를 늘리는 대신 시간복잡도는 줄이는 방식이다. 중복되는 부분 문제 피보나치 수열을 예시로 코딩하려고 한다. 점화식이 F(n) = F(n-1) + F(n-2)이기 때문에 단순 재귀 함수로 구현된다. public class fibonacciEx{ static int fibonacci(int n){ if(n == 0) return 0; if(n == 1) return 1; return fibonacci(n - 2) + fibo..
[백준 / Java] 7579번 토마토
사용한 알고리즘 (BFS) BFS https://cobi-98.tistory.com/36 [필수 알고리즘] BFS 너비 우선 탐색 (Queue 구조) 이해 BFS 너비 우선 탐색 (Breadth-First Search) 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색한다. 그렇게 되 cobi-98.tistory.com 🔒 7579번 토마토 ✔ 문제 설명 🚩 요구사항 분석 토마토 생성자 추가 (VO) int [ ][ ][] M, N, H 상자(box) 생성 상하좌우로 이동할 수 있는 배열(dx, dy, dz) 생성 익은 토마토 queue에 추가 큐가 빌 때까지 반복 이동할수 있는 경로(상자에..