seonz.log seonz.log

💻 Algorithm/Python

• [Python] 백준 - 2579 계단 오르기 (DP)

  💻 Algorithm/Python 2021. 10. 26. 13:08

  👆 첫 번째 시도 (인덱스 에러) - dp 테이블 만들어서 d[1], d[2]값을 미리 지정해주는 경우는 입력값 n이 1, 2일 상황도 생각해야 한다. - 백준에서 런타임 에러(IndexError) 나면 문제 조건에서 입력값 범위 확인하기 n = int(input()) steps = [int(input()) for _ in range(n)] d = [0] * n d[0] = steps[0] d[1] = steps[0] + steps[1] d[2] = steps[2] + max(steps[0], steps[1]) for i in range(3, n): d[i] = steps[i] + max(d[i-2], d[i-3] + steps[i-1]) print(d[n-1]) ✌ 두 번째 시도 (성공) - 낮은 계단..

  Read More
• [Python] 백준 - 1912 연속합 (DP)

  💻 Algorithm/Python 2021. 10. 25. 01:11

  👆 첫 번째 시도 (시간초과) - 이중 for문으로 각 원소 i마다 앞 원소들과의 부분합을 구하여 그 중 가장 큰 값을 d[i]에 저장 - d[i] 중 가장 큰 값을 출력 n = int(input()) array = list(map(int, input().split())) d = [min(array)] * n for i in range(n): sum = 0 for j in range(i, -1, -1): sum += array[j] d[i] = max(d[i], sum) print(max(d)) ✌ 두 번째 시도 (성공) - 각 원소 i마다 그 앞의 부분합을 구할 필요는 없음 - 어차피 음수가 포함되면 최댓값은 물 건너가므로 i 직전 원소와의 합만 확인하면 됨 n = int(input()) array =..

  Read More
• [Python] 이코테 - 정렬된 배열에서 특정 수의 개수 구하기 (이진탐색)

  💻 Algorithm/Python 2021. 10. 20. 14:55

  문제 👆 첫 번째 시도 - bisect 라이브러리를 사용하면 쉽게 정답을 얻을 수 있다. from bisect import bisect_left, bisect_right n, x = map(int, input().split()) array = list(map(int, input().split())) diff = bisect_right(array, x) - bisect_left(array, x) if diff == 0: print(-1) else: print(diff) 📌 bisect 라이브러리 - bisect_left(a, x): 배열 a에 원소 x가 들어갈 수 있는 가장 왼쪽 인덱스를 반환 - bisect_right(a, x): 배열 a에 원소 x가 들어갈 수 있는 가장 오른쪽 인덱스를 반환

  Read More
• [Python] 이코테 - 떡볶이 떡 만들기 (이진탐색)

  💻 Algorithm/Python 2021. 10. 20. 00:05

  문제 👆 첫 번째 시도 (선형탐색) - 이진탐색 파트인 건 알지만 왜 이진탐색을 써야 하는지 몰랐음 - 절단기의 높이를 가장 긴 떡의 길이로 설정하고 1씩 줄여나가면서 잘린 떡의 길이(rest)의 합을 계산 n, m = map(int, input().split()) height = sorted(list(map(int, input().split())), reverse=True) for i in range(height[0], 0, -1): rest = list(map(lambda x: x-i if x>i else 0, height)) if sum(rest)>=m: print(i) break ✌ 두 번째 시도 (이진탐색) - 떡의 길이와 절단기의 높이는 0부터 10억까지의 정수 중 하나이다. - 이렇게 큰 탐..

  Read More
• [Python] 백준 - 11047 동전 0 (Greedy)

  💻 Algorithm/Python 2021. 10. 3. 17:35

  👆 첫 번째 시도 (시간초과) - k값보다 큰 동전값은 삭제하고 동전값을 내림차순으로 정렬 - while문을 돌면서 동전값 하나씩 빼 줌 n, k = map(int, input().split()) coin = [int(input()) for _ in range(n)] coin = list(filter(lambda x: x = 0: k -= i cnt += 1 if k == 0: break print(cnt) ✌ 두 번째 시도 (성공) - k값보다 큰 동전값은 삭제하고 동전값을 내림차순으로 정렬 - k를 동전값으로 나눈 몫을 cnt에 더해서 카운팅 n, k = map(int, input().split()) coin = [int(input()) for _ in range(n)] coin = list(filt..

  Read More