Patrick's Devlog

1. 개요 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1-1. 설명 최소힙을 이용해 다음과 같은 연산을 지원하는 프로그램을 작성한다 - 배열에 자연수 x를 넣음 - 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 1-2. 제한 사항 - 첫줄에 연산의 개수 N이 주어지며, N은 1 이상 100,000 이하 - 다음 N개 줄에 연산에 대한 정보를 나타내는 정수 ..

1. 개요 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1-1. 설명 2차원 세계 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 비는 충분히 많이 오며, 고이는 빗물의 총량은 얼마인지 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 2차원 세계의 세로 길이 H와 2차원 세계 가로 길이 W가 주어지며, 1 이상 500 이하 정수 - 두번째 줄에는 블록이 쌓인 높이를 의미하는 0 이상 H 이하 정수가 왼..

1. 개요 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1-1. 설명 R x C로 된 보드가 있다. 각 보드 칸에는 대문자 알파벳이 하나씩 적혀 있으며, 좌측 상단 칸에 말이 놓여있다. 말은 상하좌우로 인접한 네 칸 중 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀있는 알파벳은 지금까지 지나온 모든 칸에 적혀있는 알파벳과 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두번 지날 수 없다. 좌측 상단에서 시작해 말이 최대한 몇칸을..

1. 개요 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 1-1. 설명 젤다의 전설 시리즈 주인공, 링크는 도둑 루피만 가득한 N x N 크기 동굴의 제일 위쪽에 있다. 젤다는 어떠한 이유로 인해 동굴안쪽까지 들어와버렸다. 그래서 제일 오른쪽 아래인 출구로 이동해야 하는 상황이다. 각 칸마다 도둑루피가 존재하는데, 이 칸을 지나면 해당 도둑루피 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 해 동굴 건너편까지 이동..

1. 개요 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 1-1. 설명 N x N의 표에 수 N^2개가 채워져 있다. 이때 채워진 수에는 특징이 있는데, 모든 수는 자신의 한칸 위에 있는 수보다는 크다. N x N 표가 주어졌을 때 N번째 큰수를 찾는 프로그램을 작성한다. 표에 채워진 수는 모두 다르다. 1-2. 제한 사항 - 첫 줄에 N이 주어지며, N은 1 이상 1,500 이하 - 다음 N개 줄에 각 줄마다 N개의 수가 주어지며, 이 수는 -10..

1. 개요 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 1-1. 설명 10,000 이하 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중 그 합이 S 이상이 되는 것중, 가장 짧은 길이를 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 N과 S가 주어지며, N은 1 이상 100,000 이하, S는 1 이상 100,000,000 이하 - 둘째 줄에는 수열이 주어짐 2. 구현 2-1..

1. 투 포인터 알고리즘 투포인터 알고리즘 or 슬라이딩 윈도우라고 부르며, 배열에 순차적으로 접근해야 할 때 두 개의 점 위치를 기록하며 처리하는 알고리즘이다. 정렬되어 있는 두 리스트 합집합에도 사용된다. 문제 상황에 맞게 투 포인터를 적절히 사용하면 된다. 정확한 사용법은 아래의 예제를 확인해보자. 2. 특정 합을 가지는 부분 연속 수열 찾기 예제 특정 숫자의 배열이 주어질 때, 해당 배열의 연속 수열 합이 특정값을 가지는 것을 확인하는 문제이다. 앞 전에 풀었을땐, 완전 탐색으로 했으나 이번에는 투 포인터 알고리즘을 사용해보았다. 대략적인 순서는 우선 start와 end를 0으로 초기화 한 후, 현재 부분 배열 합이 특정값과 동일하면 count를 하나 올려준다. 그러나, 현재 부분 배열 합이 특정..

1. 개요 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 1-1. 설명 이번 영어 시험에서 틀린 문제를 바탕으로 영단어를 암기하려고 한다. 그 과정에서 효율적으로 영단어를 외우기 위해 단어장을 만든다. 단어장의 단어순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다 - 자주 나오는 단어일수록 앞에 배치 - 해당 단어 길이가 길수록 앞에 배치 - 알파벳 사전 순으로 앞에 ..