반갑습니다!

12096번: boj.kr 풀이 이 문제는 알고리즘 문제는 아니다. 문제를 보면 전혀 감이 오질 않는다. 혹시나하는 마음에 페이시 소스를 살펴보면 몇 가지 힌트를 얻을 수 있다. 페이지 소스에는 총 4가지의 주석이 숨겨져 있다. 66y47KCc7J2YIOygleuLteydgA 7JWM66Ck7KSEIOyImCDsl4bri6Q 7ZWY7KeA66eMIO2ejO2KuOuKlCDsnojri6Q 7Z6M7Yq464qUIGh0dHBzOi8vc3RhcnRsaW5rLmlvLyDsl5Ag7J6I64qUIOOFiOOFjuOFguOFjg 각각의 주석을 Base64로 디코딩하게 되면 아래와 같은 힌트를 얻게 된다. 문제의 정답은 알려줄 수 없다 하지만 힌트는 있다 힌트는 https://startlink.io/ 에 있는 ㅈㅎ..

15663번: N과 M (9) boj.kr 풀이 엄청 많은 시리즈가 있는 문제이다. N개의 자연수 중에서 M개를 고르는 것은 백트래킹을 사용해서 어렵지 않게 구현할 수 있다. 하지만 이 문제에는 중복이 발생하기 때문에 중복을 제거해야한다. 아래의 코드에서는 set을 사용해서 중복을 제거했는데, 수열을 string으로 변환해서 set에 넣어주는 방식으로 구현했다. 또한 수열은 사전 순으로 출력해야하므로 맨 처음 입력받은 N개의 자연수를 정렬한 뒤 백트래킹했다. 코드 C++

5557번: 1학년 boj.kr 풀이 동적계획법으로 해결해야하는 문제이다. 문제를 읽고 단순하게 생각하면 DFS를 사용해서 해결할 수 있을 것 같지만, DFS를 사용하면 최대 O(2^100)의 복잡도를 가지기 때문에 시간초과가 발생한다. 따라서 다른 방법을 고민해봐야하는데, 문제에 중간에 나오는 수 모두 0 이상 20 이하라는 말이 나온다. 이 점을 이용해서 dp[숫자 인덱스][중간의 나오는 수]는 숫자 인덱스까지 수를 더했을 때 중간의 나오는 수가 될 수 있는 가지수를 구할 수 있다. 코드 C++

1644번: 소수의 연속합 boj.kr 풀이 소수를 찾아 배열에 모두 저장한 뒤, 투 포인터 알고리즘으로 해결하면 된다. 아래의 코드에서는 에라토스테네스의 체를 사용해 소수를 판별했다. 코드 C++ Python3

2631번: 줄세우기 boj.kr 풀이 이 문제는 LIS 알고리즘을 통해 해결할 수 있다. 키 순서가 오름차순으로 정렬된 아이들은 이동시킬 필요가 없다. 나머지 아이들을 최장 증가 수열에 속해있는 아이들 사이에 넣어주면 되기 때문에 LIS 알고리즘을 통해 최장 증가 수열의 길이를 계산한 뒤, 전체 어린이 숫자에서 빼주면 정답이 된다. 아래의 코드는 O(nlogn)의 복잡도를 갖는 LIS 알고리즘을 구현했다. 코드 C++