프로그래밍/Algorithm 8

[백준] 11279 최대 힙 풀이

힙은 쉬우면서 어려운 자료구조이다. 개념은 매우 쉬운데 구현에 있어서 놓치기 쉬운 부분들이 있기 때문이다. 문제 자체는 단순한 힙의 구현이다. 힙에 저장하는 부분이다. 저장할 때에는 위에 있는 노드와 비교를 진행한다. 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..

[백준] 7576 토마토 풀이

창고에 보관되는 토마토가 인접하면 서로 익는다고 한다. 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 = {-..

[백준] 11052번 카드 구매하기

문제 출처 : 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 - 포도주 시식

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

[알고리즘] 알고리즘 수업내용정리

알고리즘 : 문제를 해결 하는 방법, 추상적, 개략적으로 기술한 조리법 알고리즘을 구체적으로 표현한 것이 프로그램이다. * 알고리즘의 정확성 (Correctness)허용된 입력에 대해서 제대로 동작해야 함정확히 우리가 기대하는 것을 수행해야 함 * 프로그램 오류1) 문법 오류 (Syntax Error)- 명령문 끝에 세미콜론 등 2) 의미상의 오류 (Semantic Error)- 2 * 5 와 2 ** 5 3) 논리적인 오류 (Logical Error, Algorithmic Error)- 가장 치명적인 오류 * 부정확한 알고리즘 결과- Abort (Abnormal Termination)- 무한 루프 (Infinite Loop)- 정상적으로 끝났지만 잘못된 결과를 출력 * 시간 복잡도 분석- 하드웨어 환경..