Young

https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 문제 상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까? 예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 www.acmicpc.net 전형적인 조합론 문제입니다. n개 중에서 k개를 뽑는 함수를 만들고, next_permutaion 함수를 사용해 순열을 구합니다. 이때 ..

https://www.acmicpc.net/problem/10655 10655번: 마라톤 1 문제 농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다. 마라톤 코스는 N (3 ≤ N ≤ 100000) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다. 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한개를 www.acmicpc.net 그리 어렵지 않습니다. 하지만 O(N^2) 알고리즘은 절대 통하지 않습니다. 효율성을 위해서 우선 전체 길이를 구해놓고 시작하면 O(..

https://www.acmicpc.net/problem/17827 17827번: 달팽이 리스트 첫째 줄에 노드의 개수 N(2 ≤ N ≤ 200,000), 질문의 횟수 M(1 ≤ M ≤ 200,000), N번 노드가 가리키는 노드의 번호 V(2 ≤ V ≤ N)가 공백으로 구분되어 주어진다. 둘째 줄에 N개의 정수 C1, C2, …, CN이 공백으로 구분되어 주어진다. 이때 Ci는 i번 노드에 저장된 값을 뜻한다. (1 ≤ Ci ≤ 1,000,000) 셋째 줄부터 M개의 줄에 걸쳐 각 질문에 해당하는 K(1 ≤ K ≤ 109)가 주어진다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ..

https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] ↓ ↓ ↑ ↑ A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5] ↓ ↑ A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4 www.acmicpc.net 그냥 구현 문제입니다. 주어지는 R 값이 매우 큰데 이대로 한 칸씩 돌리면서 돌면 당연히 시간초과가 나겠죠. 배열의 고리의 길..

예상 난이도 : 6 / 10이번 문제는 '소문난 칠공주'(https://www.acmicpc.net/problem/1941) 입니다. 이 문제가 좋다고 생각하는 이유는 'dfs와 bfs와 백트래킹을 모두 연습해 볼 수 있는 문제'이기 때문입니다.개인적으로 너무 좋다고 생각합니다. 우선 25개의 자리 중 7자리를 선택하는 것부터 시작해보겠습니다. 이 문제는 '완전 탐색의 기본' 이라는 글을 완전히 숙지했다는 가정하에 설명합니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include #include #include #include us..

종만북에서 나오지만요. '중복없이 몇 개 중에 몇 개를 선택하는 방법' 너무 중요하게 다루고 있죠.완전 탐색의 기본 중에 기본 어떤 상황에서 물어봐도 바로 나와야 할 대답입니다. 우선 간단한 for문으로 고르는 방법부터 알아보겠습니다. 123456for(int i = 0; i

예상 난이도 : 5 / 10이번 문제는 '전공책'(https://www.acmicpc.net/problem/16508) 입니다. 이 문제가 좋다고 생각하는 이유는 '비트 연산에 대해서 연습, 완전 탐색을 다른 방식으로 접근하는 방법을 연습,최적화하는 방법에 대한 연습'을 해볼 수 있어서 입니다. 이 문제는 '완전탐색' 문제입니다.전공책의 갯수가 16개밖에 되지 않습니다. 모든 조합을 다 만들어봐도 2^16개 정도밖에 되지 않으니다 해봐도 무방합니다. 조건을 조금 추가해서 최적화 시킬 수도 있습니다. 우선 이런 작은 수의 완전탐색을 푸는 간단한 방법은 비트맵을 이용하는 겁니다.int 변수는 총 32비트로 32개 원소를 완전탐색할 때 쓸 수 있습니다. 원소의 갯수가 더 많다면 long long이나배열까지 쓸..

이번 문제는 'round robin'(https://www.acmicpc.net/problem/9436) 문제 입니다. 당분간은 '구현' 문제 위주로 업로드를 할 예정입니다. 이 문제가 좋다고 생각하는 이유는 'round robin 알고리즘에 대해서 생각해 볼 수 있고,언뜻 보면 쉬워보이는데 막상 구현하면 막히는 문제'이기 때문입니다. 저번 LRU Caching 문제와 비슷합니다. list를 사용해서 구현하면 아주 간단히 구현할 수 있습니다.문제가 영어라서 부담스러울 수 있지만 구현을 연습하기에 좋은 문제입니다. list에 대해서는 LRU 문제에서 자세히 설명했으니 생략하겠습니다. 1234 list ls; for (int i = 0; i