본문 바로가기

문제 노트/백준

 (102)
개미( BOJ 2136 ) 문제 : https://www.acmicpc.net/problem/2136 2136번: 개미 길이가 L(2 ≤ L ≤ 1,000,000,000)인 막대기 위에 N(1 ≤ N ≤ 100,000)마리의 개미들이 서로 다른 위치에 살고 있다. 개미들은 크기가 매우 작기 때문에 이 문제에서는 개미가 크기가 없는 점이라고 생각 www.acmicpc.net 문제 파악하기 길이가 L인 막대기 위에 있는 N마리의 개미 중 가장 늦게 떨어지는 개미의 번호와 시간을 구하는 문제입니다. N마리의 개미는 왼쪽 또는 오른쪽 방향으로 움직이며 서로 만나면 반대 방향으로 이동합니다. 개미들이 부딪히는 모든 경우를 시뮬레이션하는 방법을 가장 먼저 떠올릴 수 있지만 개미가 많아질수록 구현도 어려워지고 시간 복잡도 역시 증가합니다. 그..
유클리드 게임( BOJ 4342 ) 문제 : https://www.acmicpc.net/problem/4342 4342번: 유클리드 게임 유클리드 게임은 두 명이서 하는 게임이고, 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다. 이때, www.acmicpc.net 문제 파악하기 주어진 두 개의 자연수를 사용하여 유클리드 게임을 했을 때, 선공을 하는 사람(동혁)이 이기는지 후공을 하는 사람(동규)이 이기는지 확인하는 문제입니다. 두 사람은 항상 최적의 방법으로 게임을 한다는 설명을 통해 우리는 시작부터 승자와 패자가 결정되었다는 걸 확인할 수 있습니다. 그럼 두 개의 숫자를 가지고 누가 이기는지 어떻게 알 수 있을까요? 이는 유클리드 게임을 분석하..
옥토끼는 통신교육을 풀어라( BOJ 17838 ) 문제 : https://www.acmicpc.net/problem/17383 17383번: 옥토끼는 통신교육을 풀어라!! 옥토끼가 이런 식으로 문제를 풀면 tncks0121은 옥토끼가 5, 10, 15, 20, 25, 30, 34분에 문제를 풀었으므로 최대 5분동안 휴식을 한 것으로 간주한다. www.acmicpc.net 문제 파악하기 옥토끼가 N개의 문제를 푸는데 필요한 시간 간격의 최댓값이 가장 작아지는 경우를 구하는 문제입니다. 옥토끼는 한 번에 2개의 문제를 풀 수 있으며, 선택한 문제는 끝까지 해결한다고 합니다. 입력된 예시(3 4 5 9 10 14 15)를 보면서 문제를 자세히 이해해보겠습니다. 만약 가장 단순하게 입력된 순서대로 문제를 선택해서 해결한다면 아래와 같은 결과가 나오게 됩니다. ..
게리멘더링( BOJ 28433 ) 문제 : https://www.acmicpc.net/problem/28433 28433번: 게리맨더링 길이 $N$인 수열 $A_1, A_2, \cdots, A_N$이 주어집니다. 이 수열을 원하는 개수의 연속된 구간으로 나누어서, 각 구간의 합을 계산합니다. 합이 양수인 구간의 개수가 합이 음수인 구간의 개수를 초과 www.acmicpc.net 문제 파악하기 합이 양수인 구간을 음수인 구간보다 많이 만들 수 있는지 판단하는 문제입니다. 각 테스트케이스마다 최대 200,000개의 숫자가 주어지기 때문에 단순히 모든 경우를 확인하는 전탐색 알고리즘보다 효율적인 알고리즘이 필요합니다. 다행히 문제를 잘 살펴보면 나름 규칙성을 찾을 수 있습니다. 그럼 어떤 규칙을 찾을 수 있을까요? 문제 해결하기 문제를 관찰..
하늘에서 떨어지는 1, 2, ... , R-L+1개의 별( BOJ 17353 ) 문제 : https://www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net 문제 파악하기 주어진 N개의 수열을 대상으로 [ L, R ] 구간에 1, 2, ... , R-L+1의 값을 더하는 쿼리와 X 위치의 값을 구하는 쿼리를 수행하는 문제입니다. 수열의 범위가 최대 100,000개이며 쿼리의 수가 최대 100,000개이기 때문에 효율적인 자료구조가 필요합니다. 또한, 수행할 쿼리 역시 모든 구간에 동일한 값을 더하는 작업..
0과 1( BOJ 8111 ) 문제 : https://www.acmicpc.net/problem/8111 8111번: 0과 1 각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다. www.acmicpc.net 문제 파악하기 0과 1로 이루어졌으며 길이가 100 이하인 숫자 중 N의 배수를 구하는 문제입니다. 최대 길이가 정해져있지만 모든 경우를 확인하기에는 2100이라는 경우의 수는 너무 많습니다. 그렇기에 굳이 확인할 필요가 없는 숫자는 확인하지 않아도 되며, 이 때 사용할 수 있는 도구는 바로 나머지 연산입니다. 문제 해결하기 나머지 연산을 어떻게 활용하면 불필요한 탐색을 제거할 수 있을까요? 우리가 사용하는 숫자는 0과 1이며 나누는 숫자는 항상 N..
좋은 수( BOJ 5624 ) 문제 : https://www.acmicpc.net/problem/5624 5624번: 좋은 수 정수 N개로 이루어진 수열 A가 있다. 이때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러 번 더해도 된다) 수열이 주어졌을 때 www.acmicpc.net 문제 파악하기 N개의 정수 중 자신보다 앞에 있는(왼쪽에 위치한) 3개의 숫자들의 합으로 나타낼 수 있는 숫자의 개수를 구하는 문제입니다. N의 범위가 최대 5,000이기 때문에 3개의 숫자를 모두 확인할 수는 없습니다. 맨 첫 번째 숫자부터 하나씩 배열에 체크하면서 각각의 숫자를 만들 수 있는지 여부를 체크하면 되며, 이 경우 동적 프로그래밍 기법을 활용할 수 있습니다. 문제 ..
Swapity Swapity Swap( BOJ 18783 ) 문제 : https://www.acmicpc.net/problem/18783 18783번: Swapity Swapity Swap Initially, the order of the cows is $[1,2,3,4,5,6,7]$ from left to right. After the first step of the process, the order is $[1,5,4,3,2,6,7]$. After the second step of the process, the order is $[1,5,7,6,2,3,4]$. Repeating both steps a second time yields t www.acmicpc.net 문제 파악하기 모든 운동이 끝났을 때, N마리 소들의 배치를 출력하는 문제입니다. 소들은 M개의..

티스토리툴바