실력진단 결과 코드트리 3주차 실력진단 결과 오늘의 학습 Two Pointer & 두 포인터 다음 문제는 어떻게 해결해 볼 수 있을까요? [6, 3, 2, 4, 9, 1] 와 같이 숫자들이 주어졌을 때, 특정 구간을 잘 골라 구간 내 숫자의 합이 10을 넘지 않으면서 가장 큰 구간의 크기를 구하는 프로그램을 작성해보세요. 무작정 코드를 작성한다면, 모든 구간 O(N^2)개를 잡아보면서 그 안에 있는 숫자를 전부 더해 합이 10을 넘지 않는 경우 중 구간 크기의 최댓값을 구하면 되므로 O(N^3)이 소요됩니다. 이 방법에 대한 코드는 다음과 같습니다. public class Main { public static void main(String[] args) { int[] arr = new int[]{0, 6..
실력진단 결과 코드트리 2주차 실력진단 결과 오늘의 학습 이진탐색 & 이분탐색 업/다운 게임이라는 것을 들어보셨나요? 한 사람이 수를 생각하고, 다른 사람이 수를 예측해서 부르면 그것보다 큰지, 작은지 불러주면서 최대한 빨리 그 수를 맞추는 게임입니다. 많은 사람들이 수를 처음 예측할 땐 범위의 가운데에 해당하는 숫자를 부르고, 그 이후엔 업/다운에 맞춰 특정 구간의 가운데를 부르는 방법으로 수를 추측합니다. 이진탐색의 아이디어도 저것과 동일합니다. 찾아야 하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소관계에 따라 특정 구간으로 이동하는 것을 반복하는 것입니다. 업/다운 게임에서 비춰보면, '다운'이라는 말을 들으면 우리는 그 값보다 더 작은 값을 선택해야 하고, '업'을 외쳤다면 더 ..
실력진단 결과 코드트리 1주차 실력진단 결과 오늘의 학습 +1 -1 Technique 다음 문제는 어떻게 해결해 볼 수 있을까요? 1개의 선분이 주어졌을 때, x = k 직선과 만나는 서로 다른 선분의 수는 몇 개인지를 판단하는 프로그램을 작성해보세요. 단, 주어지는 x 좌표는 모두 다름을 가정해도 좋습니다. 예로, 다음 그림에서의 답은 2가 됩니다. 눈으로 봤을 때는 지극히 당연히 2개라는 것을 알 수 있지만, 이를 컴퓨터가 계산하기 쉽게 나타내기 위해서는 어떻게 해야 할까요? 바로 선분마다 시작점에는 +1, 끝나는 지점에는 -1을 적은 뒤, 빨간선 앞에 있는 점들에 적혀있는 숫자들을 전부 더해주면 됩니다. 이 의미는 곧 앞에 시작, 끝 지점이 전부 다 있는 선분들은 0으로 처리하고, 단 시작점만 나온..
1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 세그먼트트리 : 최소 Height를 갖는 Index 저장 분할 정복 : 최소 Height를 기준으로 왼쪽 범위, 오른쪽 범위 다시 분할 정복 제목 히스토그램 조건 시간 제한 : 0.7 초 메모리 제한 : 128 MB 문제 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다. 이러한 히스토그..
16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 1부터 1,000,000까지 가능한 최대 길이 찾기 → 이분 탐색 제목 과자 나눠주기 조건 시간 제한 : 1 초 메모리 제한 : 256 MB 문제 명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다. 조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다. 그런..
11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net Ctrl + A / Ctrl + C를 눌렀을 때의 최댓값 갱신 제목 크리보드 조건 시간 제한 : 1 초 메모리 제한 : 256 MB 문제 크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다. 화면에 A를 출력한다. Ctrl-A: 화면을 전체 선택한다 Ctrl-C: 전체 선택..
28432번: 끝말잇기 첫 줄에 끝말잇기 기록의 길이 $N$ 이 주어집니다. $(1 \le N \le 100)$ 둘째 줄부터 다음 $N$개의 줄에는 끝말잇기의 기록 $S_1, \cdots, S_N$이 한 줄에 하나씩 주어집니다. 여기서, 하나의 $S_i$는 “?” 로 www.acmicpc.net ?가 처음 단어인지, 끝 단어인지, 중간 단어인지 그리고 중복이 없는 지 제목 끝말잇기 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 끝말잇기는 단어를 중복하지 않고 단어의 맨 끝 글자에 이어서 말하는 놀이입니다. 끝말잇기 기록은 단어들의 나열로 이루어집니다. 올바른 끝말잇기 기록은 각 단어의 마지막 글자가 다음 단어의 첫 글자이며, 단어가 중복되어서 나타나면 안 됩니다. 끝말잇기 기록이 주어지는..
28431번: 양말 짝 맞추기 $6$이 쓰여 있는 양말 두 개를 한 짝으로, $8$이 쓰여있는 양말 두 개를 한 짝으로 만들면 $3$이 남습니다. www.acmicpc.net 해시셋 제목 양말 짝 맞추기 조건 시간 제한 : 0.5 초 메모리 제한 : 1024 MB 문제 양말 5개가 주어집니다. 각 양말에는 숫자가 하나씩 쓰여있습니다. 같은 숫자가 쓰인 양말 두 개를 모으면 양말 한 쌍이 됩니다. 쌍을 만들 수 있는 양말을 두 개씩 두 쌍 빼면 남는 양말에 쓰인 숫자는 무엇인가요? 입력 각 양말에 쓰인 숫자 5개가 한 줄에 하나씩 주어집니다. 입력으로 주어지는 모든 숫자는 0 이상 9 이하입니다. 항상 양말을 두 개씩 두 쌍 만들 수 있는 입력만 주어집니다. 출력 첫 줄에 남는 양말에 쓰인 숫자를 출력하세..
16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 구현 제목 배열 돌리기 3 조건 시간 제한 : 2 초 메모리 제한 : 512 MB 문제 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → 7 4 6 2 3 1 7 4 6 2 3 ..
11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 2개의 우선순위 큐 제목 절댓값 힙 조건 시간 제한 : 1 초 메모리 제한 : 256 MB 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N..
14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인 www.acmicpc.net arr[0] = Integer.MAX_VALUE 범위 밖 범위 index 0참조 제목 수열과 쿼리 16 조건 시간 제한 : 2 초 메모리 제한 : 512 MB 문제 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 10^9) 2 i j : Ai, Ai..
1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 모든 쌍을 찾기에는 시간이 없다. 하나의 임의의 노드를 정하고 최대의 길이를 가지는 노드가 그 쌍에 속할 확률이 높다. 제목 트리의 지름 조건 시간 제한 : 2 초 메모리 제한 : 256 MB 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 ..
