Data Structure & Algorithm
[99클럽 코테 스터디 31일차 TIL] 줄세우기 - 백준 2631
LIS 변형 문제이다. https://www.acmicpc.net/problem/2631문제 내용KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다.선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다.선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다.이동 도중에 보니 아이들의 번호순서가 바뀌었다.그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다.그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.3 7 5 2 6 1 4아이들을 순서대로 줄을 세우기 위해, 먼저 4..
[99클럽 코테 스터디 30일차 TIL] 상자넣기 - 백준 1965
동적계획법인데 이전 문제 너무 똑같다! https://www.acmicpc.net/problem/1965정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.상자의 크기가 주어질 때, 한 번에 넣을..
[99클럽 코테 스터디 29일차 TIL] 파도반 수열 - 백준 9461
피보나치 수열과 비슷한 문제였다. https://www.acmicpc.net/problem/9461오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.[입력]첫째 줄에 테스트 케이스의 개수 T가 주어진다.각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)..
[99클럽 코테 스터디 28일차 TIL] 가장 큰 증가하는 부분 수열 - 백준 11055
LIS 변형 문제가 나왔다. https://www.acmicpc.net/problem/11055수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고,합은 113이다.[입력]첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)[출력]첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.풀이 접근가장 긴 증가하는 수열(Longest..
[99클럽 코테 스터디 27일차 TIL] 가장 긴 감소하는 부분 수열 - 백준 11722
동적 계획법은 아직 미숙하다. https://www.acmicpc.net/problem/11722수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.[입력]첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)[출력]첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.풀이 접근DP Table을 이용한다.var dp = Array(repeating: 1, count: nums.cou..