본문 바로가기
728x90

분류 전체보기149

[백준] 11053번: 가장 긴 증가하는 부분 수열 - python https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net DP문제로 연속합과 비슷하게 가장 길게 증가하는 부분의 길이를 dp로 저장해 풀어나가는 방식이다. DP에 저장하기까지 생각이 꽤 오래걸렸다. 공부를 더 해야겠다. n = int(input()) arr = list(map(int, input().split())) dp = [1] * (n+1) for i in range(1.. 2024. 3. 30.
[백준] 1912번: 연속합 - python https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 구간의 최대 연속합을 구하는 문제 저장소를 만들어 현재까지의 최대 연속합을 저장해 나가면서 풀면 된다. 여기서 최대 연속합이 되는 경우는 3가지 경우인데 첫번째 경우는 -1 3 처럼 3이 현재값이 최대인경우 두번째는 3 2 처럼 전의 최장합과 바로 앞 원소가 더해져야 최대인 경우 세번째는 -1 2 3 처럼 자기 자신과 그 전 원소가 최대인 경우 이 모든 경우를 저장하며 끝까지 이어나간다음 dp의 최대값을 도.. 2024. 3. 30.
[백준] 2193번: 이친수 - python https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 공부하다가 머리식힐겸 DP문제 한문제 항상 DP는 옆에 주석으로 패턴을 남기면서 풀면 잘 풀리는 것 같다. 간단히 패턴을 찾았다. n = int(input()) dp = [0] * 91 dp[1] = 1 dp[2] = 1 dp[3] = 2 #100 101 dp[4] = 3 #1000 1010 1001 dp[5] = 5 #10000 10100 10010 10001 10101 for i i.. 2024. 3. 29.
[백준] 11000번: 강의실 배정 - python https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 처음보고 회의실 문제랑 비슷하다고 생각해서 그 메커니즘으로 정렬 후 arr에 배열이 없을때까지 제거하면서 cnt를 증가시켜주는 방식으로 코드를 구현했다. 그러나 시간초과가 발생하면서 뇌정지가 왔다. 처음 짠 코드 n = int(input()) arr = [] for i in range(n): start, end = map(int, input().split()) arr.append((start, end)) arr.sort(key=lambda x:.. 2024. 3. 28.
728x90

티스토리툴바