Data Structure & Algorithm/코테 스터디 TIL
[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..
[99클럽 코테 스터디 26일차 TIL] 돌 게임 - 백준 9655
문제 이름이 돌 게임이라서 순간 다른 게임을 생각했다. https://www.acmicpc.net/problem/9655돌 게임은 두 명이서 즐기는 재밌는 게임이다.탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.[입력]첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)[출력]상근이가 게임을 이기면 SK를,창영이가 게임을 이기면 CY을 출력한다.풀이 접근문제에서 "두 사람이 완벽하게 게임을 했을 때"라는 문장을 "두 사람은 매번 이기기 위한 최선의 선택을 한다."라고 이해했..