백준 1021 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 전 나의 생각 양방향 순환 큐와 탐색 조건이 주어질 때 원하는 위치의 원소값을 얻기 위한 최소 계산 횟수를 구해야 한다. 조건 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른..
알고리즘 및 자료구조
백준 20366 https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 풀이 전 나의 생각 N개의 눈덩이가 주어졌을 때 2개의 눈덩이로 만든 눈사람 2개의 지름 차이가 최소가 되는 경우를 구해야 한다. 조건 - N (4 ≤ N ≤ 600) - Hi (1 ≤ Hi ≤ 109) - i (1 ≤ i ≤ N) 과정 문제를 푸는 방법은 두 가지가 있다. 첫 번째로 2중 for문을 이용하여 푸는 방법이 있다. 하지만 여기서 주의할 ..
백준 2283 https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net 풀이 전 나의 생각 수직선 상에 구간 N개와 두 정수 A, B (A < B) 가 주어질 때, A와 B에 포함 되어있는 구간의 합이 K가 되도록 하는 A와 B의 값을 구해야 한다. 조건 - 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000 - 양 끝점의 위치는 0 이상 1,000,000 이하의 정수 과정 (0, 0)부..
백준 2461 https://www.acmicpc.net/problem/2461 2461번: 대표 선수 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 www.acmicpc.net 풀이 전 나의 생각 KOI 중학교의 학급 N개와 각 학급의 학생 수 M이 주어질 때, 각 학급의 대표의 최댓값과 최소값의 차이가 최소가 되는 경우를 구해야 한다. 조건 - 1 ≤ N, M ≤ 1,000 - 능력치는 0이상 109이하 과정 N과 M이 1000개로 주어졌다고 가정 했을 때 단순 for문을 이용해서 모든 경우를 탐색할 시 1000 ^ 1000의 횟수가 나오..
백준 20922 https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 풀이 전 나의 생각 수열 N이 주어질 때, 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구해야 한다. 조건 - (1 > arr[i]; } while (end < N) { // 끝 포인터의 원소가 K개 미만 이라면 끝 포인터, 현재 연속된 부분 수열 길이 증가 if (visited[arr[end]] < K) { visited[arr[end]]++; end++; ..
백준 2531 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 전 나의 생각 회전 초밥의 벨트 상태가 주어졌을 때 쿠폰 초밥과 연속해서 먹을 수 있는 수를 고 려하며 최대 연속해서 먹을 수 있는 초밥의 가짓수를 구해야 한다. 조건 원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한..
백준 22862 https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 풀이 전 나의 생각 길이가 N인 수열이 주어질 때, K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해야 한다. 조건 - 1 K; for (int i = 0; i > val; vec.push_back(val); } //시작 포인터, 끝 포인터, 홀수, 짝수, 최종값 int start = 0, end = 0..
백준 5214 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 풀이 전 나의 생각 하이퍼튜브의 정보가 주어졌을 때, 1번역에서 N번역으로 갈 수 있는 최소 역의 수를 구해야 한다. 조건 - (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) - K는 서로 연결하는 역의 번호 과정 처음 문제를 보면 서로 역을 연결하고 있다는 키워드를 볼 수 있다. 그래서 자연스럽게 그래프를 떠올릴 수 있고 어떻게든 주어진 역..
