문제 출처: https://www.acmicpc.net/problem/25682 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 분석 해당 문제는 누적합 관련 알고리즘을 풀면서 발견한 문제입니다. 기존의 체스판 다시 칠하기의 최적화 버전으로, 더 큰 사이즈의 보드와 줄어든 시간 제한의 차이가 있습니다. 기존 체스판 다시 칠하기는 브루트 포스(brute force) 방식으로, 8 x 8 크기의 체스판을 다시 칠하는 최소 개수를 구하는 문제였습니다. 여기에 8로 고정이었던 체스판의 크기를 k로, 시간 제한을 2초 -> 1초로, 보드의 N과 M의 최대..
문제 출처:https://www.acmicpc.net/problem/2822 2822번: 점수 계산 8개 줄에 걸쳐서 각 문제에 대한 참가자의 점수가 주어진다. 점수는 0보다 크거나 같고, 150보다 작거나 같다. 모든 문제에 대한 점수는 서로 다르다. 입력으로 주어지는 순서대로 1번 문제, 2번 문 www.acmicpc.net 문제 분석 이 문제는 총 8개의 점수 중 가장 큰 5개의 합을 출력하고 각각의 순서를 출력하면 됩니다. 다만 순서를 출력할 때는 오름차순으로 두어야하기 때문에 저는 이 문제를 풀기 위해서 sort를 2번 사용했습니다. 각 점수들을 pair형태로 를 입력합니다 pair를 내림차순으로 정렬합니다 가장 큰 5가지의 숫자들을 사용하기 때문에 5가지의 숫자들로 sum을 구하고, 그 숫자들..
문제 출처:https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 이 문제는 queue를 통해서 구형했습니다. 제일 아래로 옮기는 카드는 pop으로 빠져나온 후 push로 넣어주고, 버리는 카드는 추가안해주면 됩니다. 코드는 다음과 같습니다: #include #include using namespace std ; int main(){ ios::sync_with_stdio(false) ; cin.tie(NULL) ; cout.tie(NULL) ; que..
문제 출처:https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 분석 출처 : https://www.gleammath.com/post/solve-this-deadly-puzzle-investigating-the-josephus-problem 해당 문제는 요세푸스 순열이라하는 문제입니다. 없어지는 자리를 순서대로 출력하면 되죠. 이 문제는 queue로 해결할 수 있습니다. 자리에서 일어나서 다시 맨 뒤로 앉는다고 생각하면 이해가 쉬울 것입니다. 1번부터 N번까지 queue에 넣습니다. O(n) count = K - 1로 설정합니다..
문제 출처:https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 코드는 다음과 같습니다: #include #include using namespace std ; int main(){ ios::sync_with_stdio(false) ; cin.tie(NULL) ; cout.tie(NULL) ; int N, num ; queue q ; string input ; cin >> N ; for(int i = 0 ; i < N ; i..
