문제 https://www.acmicpc.net/problem/1322 1322번: X와 K 첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 X + Y = X | Y 를 만족시키는 K번째로 작은 자연수 Y를 찾는 문제. 조금만 생각해보면 X+Y의 값이 X | Y 과 같기 위해서는 X와 Y의 비트들 중에서 1이 서로 겹치게 등장하면 안 된다는 것을 알 수 있다. 단순히 브루트포스로 해결하려 하면 X + Y = X | Y인 Y값을 1부터 K번째 수가 등장할 때까지 반복해야 하는데 K는 최대 2,000,000,000이므로 시간 안에 해결하는 것은 불가능하다. 따라서 비트마스크를 이용하여 K..

문제 https://www.acmicpc.net/problem/2064 2064번: IP 주소 네트워크에 연결되어 있는 컴퓨터들은 각각 하나의 IP 주소를 갖게 된다. 그리고 이러한 IP 주소를 갖는 컴퓨터들이 여러 개 모여서 하나의 IP 네트워크를 구성하게 된다. IP 네트워크는 ‘네트워 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 비트 마스크로 메모리나 계산 시간을 최적화하는 다른 문제들과 다르게 비트 마스크만을 이용하는 문제. 해당 문제에 등장하는 기법은 실제로 IPv4의 서브넷에 사용된다. 서브넷, 서브넷 마스크를 알아두면 문제를 훨씬 잘 이해할 수 있으므로 새로비님의 게시글을 통해 알아보고 오자. 서브넷, 서브넷 마스크 확실하게 짚고 넘어가자 - 새로비 즉, 컴퓨터들..

문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 이 문제도 비트마스크로 풀었지만 사실 DFS방법의 백트래킹으로도 충분히 시간 내에 해결 가능하다. 또한 본인은 비트마스크와 브루트포스만으로 해결했지만 백트래킹을 같이 활용한다면 훨씬 빠르게 해결이 가능하다. 남극언어의 단어들은 모두 'a', 'c', 'i', 'n', 't' 를 가져야만 한다. 따라서 비트마스크 표현 시 비트들은 모두 해당 ..

문제 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 - 라몽의 배움일기 해당 문제의 풀이는 다음과 같다. ..