Cos Pro 1급 - 샘플 문제 6차 8번 - 지그재그 수열 구하기
문제 지문 #8 수열 S가 주어질 때, 이 수열의 연속된 부분 수열 중 지그재그 수열 길이의 최댓값을 구하려 합니다. 지그재그 수열이란 첫 번째 원소부터 인접한 원소의 차이가 증가 → 감소 → 증가 → 감소... 혹은 감소 → 증가 → 감소 → 증가... 순으로 나타나는 수열을 말합니다. 단, 수열의 길이는 3 이상이어야 합니다. 예를 들어 수열이 [ 2, 5, 7, 3, 4, 6, 1, 8, 9]인 경우, 연속된 부분 수열 [5, 7, 3, 4]가 부분 수열 중 가장 긴 지그재그 수열이 됩니다. 부분 수열 중 가장 긴 지그재그 수열의 길이를 구하기 위해 다음과 같이 프로그램 구조를 작성했습니다. 1. 각 숫자가 바로 이전 숫자보다 증가했는지, 혹은 감소했는지 표시한 배열을 만듭니다. 1-1. "증가"는..
2022. 11. 18.
Cos Pro 1급 - 샘플 문제 6차 4번 - 카드 섞기
문제 지문 #4 1부터 n까지 숫자가 적힌 카드 뭉치를 다음 규칙에 따라 카드 뭉치를 섞었을 때, 아래에서부터 k번째에 있는 카드에 적힌 숫자를 알아내려 합니다. 카드 뭉치 가장 아래에는 1이 쓰여있으며, 위로 갈수록 숫자가 커집니다. 카드 뭉치를 섞는 규칙은 다음과 같습니다. 1. 카드 뭉치를 정확히 반으로 나눕니다. 2. 두 개로 나뉜 카드 뭉치를 교차로 섞어서 카드 뭉치 하나를 만듭니다. 이때, 항상 1이 적힌 카드가 있는 뭉치를 아래로 놓고 섞습니다. 3. 위 과정을 반복합니다. 예를 들어, 1부터 6까지 숫자가 적힌 카드 뭉치를 3번 섞는다면 과정별로 아래에서부터 적힌 숫자는 다음과 같습니다. 횟수 카드 뭉치 1 [1, 4, 2, 5, 3, 6] 2 [1, 5, 4, 3, 2, 6] 3 [1, ..
2022. 11. 17.
Cos Pro 1급 - 샘플 문제 6차 3번 - 큰 수와 작은 수의 차이 구하기
문제 지문 #3 자연수가 들어있는 배열에서 숫자 K개를 선택하려 합니다. 이때, 선택한 숫자 중 가장 큰 수와 가장 작은 수의 차이가 최소가 되도록 해야 합니다. 예를 들어 배열에 들어있는 숫자가 [9, 11, 9, 6, 4, 19]이고, K = 4 라면 숫자 4개를 [9, 11, 9, 6]로 뽑으면 (가장 큰 수 - 가장 작은 수) = (11 - 6) = 5가 됩니다. [9, 9, 6, 4]와 같이 숫자를 뽑아도 (가장 큰 수 - 가장 작은 수) = (9 - 4) = 5가 됩니다. 그러나 가장 큰 수와 가장 작은 수의 차이가 5보다 작아지도록 숫자 4개를 선택하는 방법은 없습니다. 자연수가 들어있는 배열 arr, 선택해야 하는 숫자 개수 K가 매개변수로 주어질 때, 선택한 숫자 중 가장 큰 수와 가장 ..
2022. 11. 17.
