728x90 반응형 알고리즘109 [백준] 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. [백준] 11050번: 이항 계수 1 - python https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 뭔가 코딩으로는 이렇게 구현하면 안될 것 같은데 고등학교 수학 공식을 그대로 적용한 아래 코드; 사실 손으로 풀때도 5C2 = 5 * 4 / 2 * 1 로 하는데 이항 계수 2에서는 이런식으로 안하면 시간초과가 뜨게 하지않을까 예상한다. 수학의 정석 내용 그대로 구현한 코드 n, k = map(int, input().split()) parent = 1 for _ in range(1, n+1): parent *= _ child1 = 1 for _ in range(1, n-k.. 2024. 3. 28. 이전 1 ··· 16 17 18 19 20 21 22 ··· 28 다음 728x90 반응형
