코딩 테스트
[백준] 2565번 전깃줄(feat. 다이나믹 프로그래밍, LIS)
[백준] 2565번 전깃줄(feat. 다이나믹 프로그래밍, LIS)
2023.02.04https://www.acmicpc.net/problem/2565 문제 접근 첫 번째 단계(문제 요약 및 조건 파악 하기) 입력으로 첫번쨰 줄에 n이 주어지고, 두번째 줄부터 n + 1 번째 줄 까지 각각 A to B가 주어진다. (전깃줄의 연결 정보) 이 그림에 대한 입력은 아래와 같다. 8 1 8 3 9 2 2 4 1 6 4 10 10 9 7 7 6 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구해야 한다. 두 번째 단계(문제 핵심 파악 하기) 모든 전깃줄을 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력해야 한다. 전깃줄이 서로 교차하지 않기 위해서는, 1번에서 출발한 전깃줄의 도착지점은 그 이후의 번호에서 출발한 전깃줄의 도착지점들보다 낮은 ..
[백준] 17216번 가장 큰 감소 부분 수열(feat. 다이나믹 프로그래밍, LDS)
[백준] 17216번 가장 큰 감소 부분 수열(feat. 다이나믹 프로그래밍, LDS)
2023.02.02https://www.acmicpc.net/problem/17216 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악) 가장 큰 감소 부분 수열의 요소 합을 구하는 문제이다. 예를 들어 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 인 경우에 가장 합이 큰 감소 부분 수열은 A = {100, 60, 8, 7, 6, 5} 이다. 입력으로는 수열의 크기 N (1
[백준] 11054번 가장 긴 바이토닉 부분 수열(feat. 다이나믹 프로그래밍, LIS, LDS)
[백준] 11054번 가장 긴 바이토닉 부분 수열(feat. 다이나믹 프로그래밍, LIS, LDS)
2023.02.02https://www.acmicpc.net/problem/11054 첫 번째 단계(문제 요약 및 조건 파악하기) 문제에서 말하는 바이토닉 수열에 대해서 간단하게 정리하면, 어떤 특정 수 X를 기준으로 왼쪽은 X보다 작은 LIS, 오른쪽은 X보다 작은 LDS 인 수열이다. 예를 들어, {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} 은 바이토닉 수열이 아니다. 입력 조건으로는, 수열의 크기 N은 1 arr[j] and dp_left[i] < dp_left[j]: dp_left[i] = dp_left[j] dp_left[i] = dp_..
[백준] 11053번 가장 긴 증가하는 부분 수열(feat. 다이나믹 프로그래밍, LIS)
[백준] 11053번 가장 긴 증가하는 부분 수열(feat. 다이나믹 프로그래밍, LIS)
2023.02.01https://www.acmicpc.net/problem/11053 문제 접근 첫 번째 단계(문제 요약 및 조건 파악) 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하는 문제이다. 입력 조건은 수열의 크기 N은 1 arr[j] and dp[i] < dp[j]: dp[i] = dp[j] dp[i] = dp[i] + 1 print(max(dp)) DP문제는 DP테이블을 어떻게 정의하느냐가 관건.
[백준] 10844번 쉬운 계단 수(feat. 다이나믹 프로그래밍)
[백준] 10844번 쉬운 계단 수(feat. 다이나믹 프로그래밍)
2023.02.01https://www.acmicpc.net/problem/10844 문제 접근 첫 번째 단계 (문제 요약 및 조건 파악) 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다, (0으로 시작하는 수는 계단수가 아니다) N이 주어지면, 길이가 N인 계단 수가 총 몇개 있는지 구해야 한다. N은 1
[백준] 1789번 수들의 합(feat. 그리디, 수학)
[백준] 1789번 수들의 합(feat. 그리디, 수학)
2023.01.26https://www.acmicpc.net/problem/1789 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) 서로 다른 N개의 자연수의 합을 S라고 한다. S가 주어졌을 때, N의 최댓값은 얼마인지 구해야 한다. 입력으로는 자연수 S(1