Study Log Study Log

https://www.acmicpc.net/problem/2579 다이나믹 프로그래밍으로 풀기 위해 점화식을 세우는 것이 힘들어 구글링을 통해 일부 해결하였다. i - 2 계단 밟는 경우와 i - 3 계단 밟는 경우로 나뉘는 것은 알았는데, 그 이후 코드를 어떻게 짜야할 지 감이 안와서 어려움을 겪었던 문제였다. 다이나믹 프로그래밍 문제들을 반복해서 풀면 조금 나아질 것 같다..! 계단 값 저장하는 리스트를 계속 n개로 저장해서 런타임 에러가 발생했었다 😭 # 2579 : 계단 오르기 import sys imput = sys.stdin.readline n = int(input()) # 계단 값 저장하는 리스트 n개로 저장하면 런타임에러(인덱스에러) 발생 stair = [0] * 301 for i in r..

https://www.acmicpc.net/problem/11727 이코테 다이나믹 프로그래밍의 바닥공사 예제와 푸는 방식이 같아서 쉽게 할 수 있던 문제였다. # 112727 : 2xn 타일링 2 import sys input = sys.stdin.readline n = int(input()) # dp 테이블 초기화 d = [0] * 1001 d[1] = 1 # 2x1 타일 채우는 방법 1가지 d[2] = 3 # 2x2 타일 채우는 방법 3가지 for i in range(3, n + 1): # i - 1 번째 타일까지 채웠다고 가정하면, 2x1 타일 채우는 방법 1가지 # i - 2 번째 타일까지 채웠다고 가정하면, 2x2 타일 채우는 방법 2가지 # 2x1 타일 2개로 채우는 방법은 i-1번째까지 채..

Ch8. 다이나믹 프로그래밍중복되는 연산을 줄이자최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다.그래서 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 💡다이나믹 프로그래밍 : 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 다이나믹 프로그래밍 사용 조건큰 문제를 작은 문제로 나눌 수 있다.작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 피보나치 수열을 이러한 조건을 만족하는 대표 문제이다. 이 문..

https://www.acmicpc.net/problem/1920 이코테 이진 탐색 챕터의 부품 찾기 예제와 비슷해서 금방 풀 수 있던 문제였다.n 개의 정수 리스트를 set()함수로 정렬한 후 m개의 정수 리스트를 하나씩 확인하여 풀었다. # 1920 : 수 찾기 n = int(input()) n_list = set(map(int, input().split())) m = int(input()) m_list = list(map(int, input().split())) for i in m_list: # 해당 수가 존재하는 지 확인 if i in n_list: print(1) else: print(0) Uploaded by Notion2Tistory v1.1.0

https://www.acmicpc.net/problem/2110 이진 탐색으로 푸는 문제 같은데 중간점을 이용해서 공유기 개수를 세는 방법이 떠오르지 않아 구글링을 통해 해결했다. 생각하지 못했던 부분은 다음과 같다.시작점은 집들 사이의 최솟값, 끝점은 집들 사이의 최댓값으로 설정공유기 위치는 현재위치와 다음 집이 공유기 사이의 거리 이상인 곳에 설치 이 문제는 sys.readline 을 사용해서 입력값을 받지 않으면 시간 초과가 발생한다. # 2110 : 공유기 설치 import sys input = sys.stdin.readline n, c = map(int, input().split()) house = [int(input().rstrip()) for _ in range(n)] house.sort(..

https://www.acmicpc.net/problem/1072 시간 초과가 발생했던 코드# 1072 : 게임 import sys input = sys.stdin.readline x, y = map(int, input().split()) z = int((y / x) * 100) new_z = z count = 0 while z == new_z: x += 1 y += 1 new_z = int((y / x) * 100) count += 1 if new_z != z: print(count) elif x == y: print(-1) break아마 1씩 증가해서 승률을 다시 측정해서 시간 초과가 발생한 것 같다. 구글링을 해보니 이진 탐색을 통해 문제를 해결한 경우가 많았다. 찾아보니 내가 놓친 히든 케이스가 ..

https://www.acmicpc.net/problem/2512 이진 탐색을 이용해서 풀었고, 이코테의 이진탐색 챕터의 떡볶이 떡 만들기와 비슷해서 금방 풀 수 있었던 문제였다. # 2512 : 예산 import sys input = sys.stdin.readline n = int(input()) request = list(map(int, input().rstrip().split())) m = int(input()) start = 0 end = max(request) result = 0 # 상한액 while start = mid: total += mid # 요청한 예산이 상한액보다 작을 경우 else: total += x # 예산이 충분할 경우 if total

https://www.acmicpc.net/problem/2805 이 문제는 이코테 이진 탐색 챕터의 떡볶이 떡 만들기 예제와 거의 똑같아서 금방 풀었다. 최종 나무의 길이와 필요한 나무의 높이를 비교하며 start, end 위치를 조정해나가면 풀 수 있다. # 2805 : 나무 자르기 n, m = map(int, input().split()) height = list(map(int, input().split())) start, end = 0, max(height) result = 0 while start mid: total += x - mid if total < m: end = mid - 1 else: result = mid start = mid + 1 print(result) Uploaded by N..