문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 solved.ac 난이도: Sliver 3 비트 마스크로 분류되어 풀어보았는데 사실상 메모리 제한이 크기 때문에 다른 기법으로도 충분히 해결 가능했던 문제이다. 본인은 비트마스크로 모든 경우의 수를 살펴보는 브루트포스 알고리즘을 사용했다. 비트 마스크로 사람의 수(player_num)를 반으로 나눈 팀을 형성하기 위해 아래와 같이 1~(1

에라토스테네스의 체 "에라토스테네스의 체(Sieve of Eratosthenes)"는 3세기의 그리스 수학자 에라토스테네스가 정리한 소수를 찾는 방법이다. n이하의 자연수에서 소수의 배수를 차례대로 소거하여 최종적으로 n이 남아있다면 n은 소수임을 알아낼 수 있다. 에라토스테네스의 체 구현에는 해당 수가 소수인지 아닌지만 저장하는 bool형의 자료구조가 필요하며, 아래 두 가지의 최적화를 거친다. 1. n이 인수가 있다면 인수는 √n 이하의 수와 그 이상의 수의 쌍으로 이루어지기 때문에 √n의 수까지만 확인해도 판정이 가능하다. 2. i의 배수를 지울때는 i*i이하의 값들은 이미 i이하의 값의 배수(ex. i*3, i*4, i*5 ... i*(i-1) 는 이미 소거)이므로 i*i이상의 값부터 소거하면 된..

문제 https://algospot.com/judge/problem/read/PASS486 algospot.com :: PASS486 비밀번호 486 문제 정보 문제 재훈이는 한 번 담배를 끊겠다고 다짐할 때마다 이메일 계정 비밀번호를 바꾸는 습관이 있습니다. 재훈이는 비밀번호를 항상 "no-smok**X**" 와 같이 정하는데, 여기서 X algospot.com 풀이 종만북 난이도: 중 에라토스테네스의 체를 활용한 소인수 분해를 이용해야해서 어려웠던 문제이다. 특히 소인수 분해까지는 구현해도 수학적인 최적화를 진행하지 않으면 제 한 시간 안에 맞출 수 없다. 해당 문제에서 사용되는 에라토스테네스의 체와 소인수 분해는 아래 링크에서 확인하자. 에라토스테네스의 체와 소인수 분해 어떤 수n의 약수의 개수를 ..

문제 https://algospot.com/judge/problem/read/POTION algospot.com :: POTION 마법의 약 문제 정보 문제 마법의 약 수업 시간에 교수님의 설명을 안 듣고 졸던 헤리는 실수로 냄비에 몇 가지 재료의 양을 잘못 넣고 말았습니다. 약의 색깔이 심상치 않게 변하는 것을 눈치챈 algospot.com 풀이 유클리드의 최대공약수 알고리즘을 활용하는 문제이다. 해당 문제에서 다른 건 몰라도 한 가지 확실한 것은 (이미 넣은 재료양)/(레시피 재료 양)의 비가 최대인 것보다 크거나 같은 크기의 약을 만들어야 한다는 것이다. 이러한 비를 already_put / recipe (최대비)라고 나타내 보자. 이보다 크거나 같은 비는 k/b(넣을 약의 비)라고 나타내면 아래와..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. 연습 문제 링크 백준 - 나무 자르기(2805) + parametric search - Silver 3 백준 - 숫자구슬(2613)★ + parametric search - Gold 2

문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 solved.ac 난이도: Silver 3 이분 탐색의 응용인 parametric search를 이용하는 대표적인 문제이다. 이분 탐색(binary search)과 parametric search의 차이점은 라몽님의 게시글을 참조하자. 이진탐색(Binary Search)와 Parametric Search - 라몽의 배움일기 left는 0에서부터 r..

문제 https://www.acmicpc.net/problem/2613 2613번: 숫자구슬 첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 그리디 문제로 분류되었지만 이분 탐색을 응용한, parametric search를 사용해야 했던 문제이다. 이분 탐색(binary search)과 parametric search의 차이점은 라몽님의 게시글을 참조하자. 이진탐색(Binary Search)와 Parametric Search - 라몽의 배움일기 해당 문제의 풀이는 다음과 같다. ..

문제 https://www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 정렬을 해서 푸는 것까지는 생각해냈지만 0을 지나는 노선의 처리하지 못하여 틀린 그리디 문제. 해당 문제는 0을 지나지 않는 노선(line_v)와 0을 지나는 노선(cross_line_v)로 나누어 해결해야 한다. 1. 0을 지나지 않는 노선(line_v) 해당 노선들은 시작점(start)을 기준으로..

문제 https://www.acmicpc.net/problem/2513 2513번: 통학버스 첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2second)); else right_v.push_back(make_pair( abs(school_pos - it->first),it->second)); } Colored by Color Scripter cs 그 후 먼 곳부터 정렬되도록 left_v, right_v를 내림차순으로 정렬해준다. 이제 먼 곳부터 방문하면서 정원을 채우는 코드를 구현한다. 1. 남은 자리(left_sit) 보다 해당 위치(apt_idx)에서 태울 학생 수가 적다면 모두 태우고 해당 위치의 학생 수는 0으로,..

문제 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 solved.ac 난이도: Silver 2 간단한 그리디 알고리즘 문제. 주식은 낮을 때 사서 높을 때 팔아야하는 것처럼 해당 문제도 같은 방식으로 풀 수 있다. 주가를 입력받은 stock_value을 역순으로 진행하면서 두가지를 확인하면 쉽게 구할 수 있다. 1. 현재(day)의 주가가 지나온 주가 중에서 최대 주가(max_stock)보다 작다면 해당 주식은 구매해서 ma..