반갑습니다!

2959번: 거북이 boj.kr 풀이 이 문제에서 4개의 정수로 직사각형을 만들어야한다. 예시로 들어온 1, 2, 3, 4를 생각해보면 거북이는 가로로 3과 4만큼 이동하고 세로로는 1과 2만큼 이동한다. 따라서 1 x 3의 직사각형이 된다. 즉, 작은 정수 2개, 큰 정수 2개가 각각 가로 / 세로가 된다. 따라서 정렬을 해준 뒤, 가로에서 작은 수 x 세로에서 작은 수를 구하면 된다. 코드 C++

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++