그냥 하는 노트와 메모장

배낭 문제(냅색) 시리즈 - BOJ 12865 평범한 배낭, BOJ 12920 평범한 배낭2, Algospot SUSHI [분류 : 다이나믹 프로그래밍] 냅색 문제들을 모아 풀이를 공유하는 포스팅입니다. 이 포스팅은 희한한 냅색 문제들 보는 대로 갱신됩니다. 1. BOJ 12865 평범한 배낭 더보기 일반적으로 알고있는 냅색을 사용하면 된다. 시간 복잡도는 O(NK)가 된다. 재귀적으로 처리해도 좋고, 일차원 배열을 만들어서 큰 값에서 작은 값으로 내려가면서 데이터 오염을 피하며 dp를 구성해도 좋다. #include #include #include using namespace std; const int MAX_N = 100; int N, dp[MAX_N][100001], w[MAX_N], v[MAX_N..

* Algospot - 정렬 게임(SORTGAME, ) [ 분류 - BFS ] 간단한데, 이상하게 자꾸 시간초과가 뜨는 문제다. * 접근 방법 1. 길이가 x인 수열을 한 번 이상의 연산을 수행했을 때, 정렬 결과로 나올 수 있는 경우의 수는 x!이다. 2. 내부에서 연산을 수행하는 속도는 약 O(x)다. 따라서 1.의 결과로 보면 속도는 최대 8!*8이다. 3. 하지만 이를 들어오는 쿼리마다 수행할 수는 없으므로 "미리" 저장을 해놓고 들어오는 입력에 따라 O(C lg(x!*x)) 시간으로 찾을 수 있도록 한다. 4. 최대가 8이므로 길이 8짜리만 구하고, 나머지 길이에 대해서는 남는 부분을 오름차순으로 채우고 찾으면 된다. - 코드 #include #include #include #include #i..

* Algospot - 어린이날 (CHILDRENDAY, https://algospot.com/judge/problem/read/CHILDRENDAY) [ 분류 - BFS/ Mathematics ] 접근 방식이 다소 까다롭다. N명 중 M이 하나씩 더 받기 위해선 N%ans = M이며 이 나머지에 대해 사이클이 존재함을 알아야 한다. 또한 이를 증명하는 페르마의 소정리에 대해 알고 있어야 한다. * 접근 방법 1. 찾고자 하는 ans에 대해 N%ans = M이기 위해선 기저(시작 지점)은 숫자(한자리 수)부터 시작한다. 여기에 하나씩 이어붙이며 진행하는 BFS를 구성한다. 2. 나머지이기 때문에 후보를 [0, N]으로 줄일 순 없다. 적어도 하나 이상의 장남감을 줘야하기 때문에 [0, 2*N]가 후보가 ..