99클럽 코테 스터디 32일차 TIL : 백준 11054번, 최장 증가 부분 수열
1. 오늘의 문제 보자마자 최장 증가 부분 수열임을 알아지만 푸는데 꽤나 오랜 시간이 걸렸다. 자꾸 반례에 걸렸는데, 왜 걸리는지조차 알기가 쉽지 않았다. 결국 백준에서 검색을 통해 반례를 찾아보았다. 더보기문제 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그..
2024. 11. 28.
99클럽 코테 스터디 30일차 TIL : 백준 1965번, 최장 증가 부분 수열
1. 오늘의 문제 오늘의 문제는 최장길이 부분수열의 변형이다. 이 문제는 유형이 달라도 거의 복붙이라 별로 어렵지 않음. 더보기문제 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.상자의 크기..
2024. 11. 26.
