JayTech의 기술 블로그

힙은 쉬우면서 어려운 자료구조이다. 개념은 매우 쉬운데 구현에 있어서 놓치기 쉬운 부분들이 있기 때문이다. 문제 자체는 단순한 힙의 구현이다. 힙에 저장하는 부분이다. 저장할 때에는 위에 있는 노드와 비교를 진행한다. public static void push(int n) { heap[++index] = n; // 정렬 for (int i = index; i > 1; i /= 2) { if (heap[i] > heap[i/2]) { int temp = heap[i]; heap[i] = heap[i/2]; heap[i/2] = temp; } else { break; } } } 여기서 중요한 것은 인덱스의 범위이다. for 문안의 조건을 잘 생각해야 한다. 두 번째로 조금 까다로운 값 꺼내기 작업이다. pu..

창고에 보관되는 토마토가 인접하면 서로 익는다고 한다. BFS로 풀면 되는 문제이지만 BFS문제마다 하나씩 포인트가 있다. 이 문제는 한 점에서만 탐색이 이루어지는 것이 아니라 동시에 여러 곳에서 BFS가 일어난다. 상자 안에 토마토가 여러개 있을 수 있으므로 각 지점부터 BFSF를 진행해 주어야 한다. 그래서 배열을 초기화 하는 과정에서 토마토가 들어 있다면 큐에 하나씩 넣어주어야 한다. 전체 소스 import java.util.*;import java.io.*; public class Q7576 { static int row; static int col; static int[][] tomato; static int[] moveX = {0, -1, 0, 1}; static int[] moveY = {-..

문제 출처 : https://www.acmicpc.net/problem/11052 이 문제는 다이나믹 프로그래밍으로 풀 수 있다. 문제가 장황하여 주의력이 산만해지지만 침착하게 읽어보자. 카드팩의 배열이 배열의 인덱스는 카드의 갯수이고 배열의 값은 카드의 금액이다. 이 두가지 정보가 한 배열에 들어 있기 때문에 조금 헷갈릴 수 있다. 123456789101112131415161718192021222324import java.util.*; public class Q11052 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] card = new int[n+1]; in..

백준 알고리즘 2156번 Dynamic Programming 문제를 풀어보았다. 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 ..