본문 바로가기

無汗不成

Programming

 (12)
[자료구조] 우선순위 큐(Priority Queue), Heap 우선순위 큐 우선순위를 가진 항목들을 저장하는 큐 우리가 정한 우선순위대로 정해진 큐 원래라면 1차선 도로처럼 FIFO 순서대로 나아가는 것을 큐(Queue)다. 2차선처럼 우선순위가 높은 데이터가 먼저 나가는 것이 우선순위 큐다. 숫자의 크기를 가지고 일단 우선순위 큐를 만들어보자. 우선순위 큐(heap)은 2가지로 구분 최소 우선순위 큐 (min heap) 최대 우선순위 큐(max heap) 우선순위 큐 구현방법 3가지가 존재한다 1. 배열을 이용한 우선 순위 큐 정렬이 안된 배열 정렬이 된 배열 삽입 - O(1) 가장 뒤에 삽입 삭제 - O(n) 처음부터 끝까지 모든 요소를 check하여 삭제 삽입 - O(n) 모든 요소와 삽입할 요소의 우선순위를 비교하여 삽입위치 결정(이진탐색) 삭제 - O(1)..
[java] 자바 문법 기초 배열 같은 자료형의 값 여러 개를 저장하는 연속된 공간 배열을 선언하는 4가지 방법 // 배열 선언 첫 번째 방법 String[] coffees = new String[4]; // 두 번째 방법 String coffees[] = new String[4]; // 세 번째 방법(선언과 동시에 초기화) String[] coffees = new String[] {"아메리카노", "카페모카", "라떼", "카푸치노"}; // 네 번째 방법 String[] coffees = {"아메리카노", "카페모카", "라떼", "카푸치노"}; 배열 순회 public static void main(String[] args) { // 배열의 순회 String[] coffees = {"아메리카노", "카페모카", "라떼", "카푸..
[stack] 백준 24463번, 미로 https://www.acmicpc.net/problem/24463 24463번: 미로 첫 번째 줄에는 미로의 크기 $N, M$이 주어진다. $(3 \le N, M \le 2,001$, $N, M$은 홀수$)$ 두 번째 줄부터는 미로의 정보가 주어진다. 두 번째 줄부터 $N$줄에 거쳐 각 줄에는 길이가 $M$이고 .과 +만으로 이 www.acmicpc.net 입력 첫 번째 줄에는 미로의 크기 N, M이 주어진다. (3≤N, M≤2,001, N, M은 홀수) 두 번째 줄부터는 미로의 정보가 주어진다. 두 번째 줄부터 N줄에 거쳐 각 줄에는 길이가 M이고 .과 +만으로 이루어진 문자열이 주어진다. 같은 지점으로 돌아오는 길이 존재하지 않고, 두 구멍 사이를 이동할 수 있는 미로만 주어진다. 출력 주어진 미로..
[행렬누적합] 백준 1749번, 점수따먹기 https://www.acmicpc.net/problem/1749 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 입력 첫째 줄에 N (1 < N < 200), M (1 < M < 200)이 주어진다. 그다음 N개의 줄에 M 개씩 행렬의 원소가 주어진다. 출력 첫째 줄에 최대의 합을 출력하라. 예제 입력1 3 5 2 3 -21 -22 -23 5 6 -22 -23 -25 -22 -23 4 10 2 예제 출력 1 16 코드 from sys import stdin r_line = stdin.readline h, w = m..
[MST] Prim & Greedy MST 중 prim알고리즘은 그리디알고리즘을 만족하는 몇 안 되는 알고리즘이다. 여기서 mst = minimum spaning tree로 최소신장트리이다. 신장트리 중 가중치의 총합이 가장 최소임을 의미한다. 특징으로는 1. 간선의 가중치의 합이 최소여야 한다. 2. n개의 정점을 가지는 그래프에 대해 반드시 (n-1) 개의 간선만을 사용해야 한다. 노드 1번에서 가질 수 있는 간선의 수 : 2(N-1) 노드 2번에서 가질 수 있는 간선의 수 : 2(N-2) 노드 3번에서 가질 수 있는 간선의 수 : 2(N-3) 이를 모두 더하면 2(N-1 + N-2 + N-3 + .... + N-N) 2*(N^2 - (N(N+1)/2)) E = N(N-1) 이다. 이때 prim알고리즘은 현재 보이는 것 중 가장 좋은 ..
[dp] 백준 13703번, 물벼룩의 생존확률 https://www.acmicpc.net/problem/13703 13703번: 물벼룩의 생존확률 수면에서 k 센티미터 아래에 있는 물벼룩은 1초마다 각각 1/2의 확률로 위 또는 아래로 1 센티미터 이동한다. 물벼룩은 수면에 닿자마자 기다리고 있던 물매암이들에 의해 먹혀 없어진다. 예를 www.acmicpc.net 문제 수면에서 k 센티미터 아래에 있는 물벼룩은 1초마다 각각 1/2의 확률로 위 또는 아래로 1 센티미터 이동한다. 물벼룩은 수면에 닿자마자 기다리고 있던 물매암이들에 의해 먹혀 없어진다. 예를 들어, 수면아래 2 센티미터에 있던 물벼룩은 3초 동안 "위위위, 위위아래, 위아래위, ..., 아래아래아래"의 8가지 방법으로 움직일 수 있고, 이 방법들의 확률은 모두 1/8로 같다. 이 중,..
[브루트포스] 백준 1018번, 체스판 다시 칠하기 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은..
[dp] 백준 22968번 균형 https://www.acmicpc.net/problem/22968 22968번: 균형 이진 탐색 트리의 한 종류인 AVL Tree는 "높이 균형 성질"이라는 성질을 이용해 트리의 균형을 맞춘다. 또한, 높이 균형 성질을 만족하는 이진 탐색 트리는 전부 AVL Tree이다. 트리 $T$의 모든 내부 www.acmicpc.net 문제 이진 탐색 트리의 한 종류인 AVL Tree는 "높이 균형 성질"이라는 성질을 이용해 트리의 균형을 맞춘다. 또한, 높이 균형 성질을 만족하는 이진 탐색 트리는 전부 AVL Tree이다. 트리 T의 모든 내부 정점 v에 대해, v의 왼쪽 부트리와 오른쪽 부트리의 높이 차이가 1 이하일 때, T는 높이 균형 성질을 만족한다고 부른다. 위 그림에서, 왼쪽에 있는 트리는 모든 내부..

티스토리툴바