그건 장난감이 아니라 돌이야

https://www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net C로 문제풀던 시절에 세그먼트 트리를 공부하고 풀었던 문제이다. 어느 구간의 비디오를 빌려올 때 그 구간에 모든 비디오가 다 있는지 체크하는 문제이다. 당연히 브루트 포스로 범위 안을 모두 확인해보면 TLE가 난다. 문제를 푸는 핵심은 어느 구간 [x, y]의 비디오를 빌려왔다고 가정하면 그 구간의 비디오 번호의 최댓값과 최솟값이 있을 것인데 겹치는 번..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 암호를 구성하는 여러 조건이 주어졌을 때 주어진 조건을 모두 충족하는 가능한 모든 암호를 구하는 문제이다. 암호를 구성하는 조건들은 다음과 같다. 1. 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다. 2. 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되어있다. 모음인지 자음인지 구별하는 함수와 알파벳 순인지 구별하는 함수를 만들어서 구현했다. 사실 알파벳 ..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 어느 수들이 주어지고 그 수들이 상근이가 가지고 있는 수 중 존재하는지 알아내는 문제이다. 브루트 포스로 모든 수를 비교해보고 푼다면 O(N^2)이므로 TLE가 나는 문제였다. 상근이가 가진 수들을 먼저 정렬해주고 이분탐색으로 풀면 되는 문제이다. 나는 재귀로 구간을 반반 나눈 다음에 두 구간 중 수가 포함될 가능성이 있는 구간만 재귀로 똑같이 탐색하는 함수를 구현했..

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m (0 ≤ m ≤ n ≤ 2,000,000,000, n ≠ 0)이 들어온다. www.acmicpc.net 조합의 끝자리 0의 개수를 출력하는 문제이다. 끝자리 0의 개수를 새기위해선 식에 10이 몇번 곱해져있는가를 구하면 되는데 이건 식에 2와 5가 곱해진 횟수중 더 작은 것의 횟수와 같다. (2와 5의 곱이 10이므로) nCm = n! / (n-m)!m! 이므로 n!에 곱해져있는 2의 횟수와 5의 횟수에 각각 (n-m)!와 m!에 곱해져있는 2의 횟수와 5의 횟수를 빼면 된다. 2의 횟수와 5의 횟수를 새는 방법은 예를 들어 24!의 2의 갯수와 5의 갯수를 샌다고 가정하면 2의 갯수는..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 탐색을 통해 이분 그래프인지 아닌지 판별하는 문제이다. 문제에서 설명하는 이분 그래프의 설명은 다음과같다. "그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다." 쉽게 비유를 들면 사람들이 잔뜩 있는데 사람이 각각 정점이라고 하면 남자와 여자 두 성..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 독일 로또에서 로또번호를 뽑는 경우의 수를 모두 출력하는 문제이다. 알고스팟에 PICNIC 문제와 비슷한 함수를 구현해서 풀어보았다. 다른점이 있다면 이 문제는 테스트 케이스가 여러개가 주어지기 때문에 테케마다 원본 벡터를 초기화 해야하기 때문에 매 테스트 케이스마다 벡터를 새로 선언해서 원소를 넣어주고 solve함수에 인자로 주었다. #include #include #include #..

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 길이가 같은 정수배열 A와 B의 인덱스가 같은 항끼리의 곱의 합이 최소가 되게 만드는 문제이다. 나름 문제를 어렵게 만들기위해 배열 B에 있는 수를 재배열하면 안된다고 문제에 명시해두었다. 하지만 배열 A를 마음껏 재배열 할 수 있으므로 사실 B의 순서는 아무런 의미가 없다. N이 4라고 가정하면 S = A[0]*B[0] + A[1]*B[1] + A[2]*B[2] + A[3]*B[3] 일 ..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 오늘 가볍게 풀어본 문제는 요세푸스 문제이다. 요세푸스 문제에는 스토리가 있다. 요세푸스는 유대와 로마가 전쟁일 때 유대군 장교로 참전한 적이 있었는데 유대군이 전쟁에서 밀리자 항복대신 차라리 자살을 하자는 동료들의 의견이 강세였다고한다. 근데 그냥 자살하기는 뭐했는지 원모양으로 둘러서서 정해진 순서만큼 건너뛰면서 죽이기로 했다고 한다. 하지만 동료들과 다르게 현명한 요세푸스는 자살하고 싶지 않아서 어디에 서야지 끝까지 살아남을 수 있는지를 찾아서 마지막까지 살아남아 로마에 항복했다는 이..

https://www.algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 www.algospot.com 이번 문제에서는 정말 중요한 것을 배웠다. 일단 문제를 봤을 때 풀이는 어렵지않게 떠올렸고 O(4^10)인 것 까지 금방 계산해서 완탐으로 풀 수 있겠다! 라고 생각했었다. 그렇게 구현이 다 끝났고 테스트 케이스도 다 맞았다. 그런데 뭔가 이상했다... 2 12 6 6 6 6 6 12 12 12 12 12..

https://www.algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 www.algospot.com 종만북 두번째 문제 게임판 덮기이다. 어려서 엄마손잡고 교보문고에 갔을 때 이런 비슷한 이런 장난감을 홍보하는걸 봤던 기억이 난다. 그 때 장난감 체험을 했었는데 공간지각력이 오진다고 직원이 엄청 치켜세워줬었다. 그때는 정말 내가 공간지각력이 뛰어난줄 알았는데 커서 보니깐 그냥 카카오맵 보고 집 찾아갈 수 있는 정도인 것 같다ㅋㅋㅋ 종만..