(Python/플5)백준 알고리즘 14003번: 가장 긴 증가하는 부분 수열
문제바로가기 문제:수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력:첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)출력:첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다. 풀이: 시간 초과 코드import sysN = int(sys.stdin..
2024. 8. 14.
(Python/🥈2)백준리즘알고리즘 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의 가장 긴 감소하는 부분 수열의 길이를 출력한다. import syssys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')n = int(input())lst = list(map..
2024. 5. 18.
(Python/🥇4)백준알고리즘 10942번: 팰린드롬?
문제 바로가기 문제: 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자. S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다. S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다. S = 3, E = 3인 경우 1은 팰린드롬이다. S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다. 자연수 N개와..
2023. 7. 24.
LIS 최장증가수열
최장증가수열이란 : 가장 긴 증가하는 수열을 말한다. [1,4,3,6,4,8] 이런식으로 주어졌을때 가장 긴 증가하는 수열은 [1,3,4,8] 4이다. 이러한 문제를 풀때는 dp를 사용하여야 하는데, 각 idx까지의 최장증가 수열을 dp에 저장하는 것이다. 주어진 idx 보다는 작지만 가장 긴 수열에 + 1을 해주면된다. idx 가 0 일때 는 dp[0] = 1 1일때는 dp[1] = 2 dp[2] = 2 dp[3] = 3 dp[4] = 3 dp[5] = 4 이렇게 하려면 이중 포문을 사용해야한다. for i in range(N): for j in range(i): if lst[i] > lst[j]: dp[i] = max(dp[i], dp[j] + 1) 그것을 식으로 나타나면 이렇게 된다. 기본문제: h..
2023. 6. 13.
