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

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 종만북 두번째 문제 게임판 덮기이다. 어려서 엄마손잡고 교보문고에 갔을 때 이런 비슷한 이런 장난감을 홍보하는걸 봤던 기억이 난다. 그 때 장난감 체험을 했었는데 공간지각력이 오진다고 직원이 엄청 치켜세워줬었다. 그때는 정말 내가 공간지각력이 뛰어난줄 알았는데 커서 보니깐 그냥 카카오맵 보고 집 찾아갈 수 있는 정도인 것 같다ㅋㅋㅋ 종만..

https://www.algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 www.algospot.com 종만북 대망의 첫번째 문제 소풍이다. 어느 유치원에서 소풍을 갈 때 두명씩 짝을 지어주는데 서로 친구가 아닌 학생들끼리 짝을 지어주면 서로 싸우기 때문에 무조건 친구들끼리만 짝을 지어줘야 하는 문제이다. 친하지 않은 학생들끼리 짝이되면 서로 알아가려고 하면 좋을텐데 안드로메다 유치원 익스프레스반은 상당히 보수적인 아이들이 모여있는 것 같아 보인다. 전체 테스트 ..

종만북 문제 모음 algospot.com :: JMBook 문제들 링크 JMBook 문제들 링크 1장 문제 해결과 프로그래밍 대회 제목 링크 난이도 록 페스티벌 FESTIVAL ★☆☆ 2~5장은 문제/예제 없음. 6장 무식하게 풀기 제목 링크 난이도 소풍 PICNIC ★☆☆ 게임판 덮기 BOARD www.algospot.com 코드포스 Codeforces codeforces.com 백준(BOJ) Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net