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.
99클럽 코테 스터디 29일차 TIL : 백준 9461번, 수학
1. 오늘의 문제 오늘은 삼각형을 붙이는 문제였다. 마치 피보나치 수열같은 느낌? 처음에는 규칙이 없는 것처럼 보이지만 5, 7, 9... 에서 부터 규칙이 보이기 시작한다. 다음 숫자는 그 이전의 숫자 + 이전 숫자의 -4 인덱스 값이다. 더보기문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.N이 주어졌을 때, P(N)을 구하는 프로그램..
2024. 11. 25.
99클럽 코테 스터디 27~28일차 TIL : 백준 11055, 최장 증가 부분 수열
1. 오늘의 문제 오늘 문제는 어제 나왔던 최장 증가 부분 수열의 응용버전이다. 어제 나왔던 문제와 비슷함. 27일차 TIL은 도저히 쓸 시간이 나지 않아서 오늘거로 때우려고 한다. 역시 매일 과제가 있는 프로젝트는 주말이 위기다. 더보기문제수열 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가 주어진다. ..
2024. 11. 25.
