푼 날짜 : 2024.10.11푼 문제 : [12851] / 숨바꼭질 2사용한 언어 : python알고리즘 : BFS 접근 방식 : 사실 저번에 풀다가 "가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성" 에서 막혔었다.1 21 + 1 => 21 * 2 => 2 요런 테케의 경우 방법이 2가지인데 방문 처리를 해버리는 순간 조건문 안에 안들어가서 고민을 좀 했다. visited[i] == -1 or visited[i] == visited[now] + 1 디버깅 하다가 요렇게 수정하고 바로 통과 !역시 오늘도 하나 배워갑니다.. 코드 :import sysfrom collections import dequeN, K = map(int, sys.stdin.readline().split(..
푼 날짜 : 2024.10.08푼 문제 : [14501] / 퇴사사용한 언어 : python알고리즘 : DP 접근 방법 : 1) 상담횟수와 금액 배열을 따로 만들자! 금액이 높다고 출력 X상담을 제일 많이 한 날의 금액을 출력 O 따라서 두 값을 적절히 저장할 배열이 필요하다. 2) 계산이 불가능 한 경우를 먼저 지우자! 오늘부터 상담을 시작했을 때 퇴사 전 끝내지 못할 경우 (i + lst[i][0] > N)예를 들어 8일에 상담이 끝나는데 7일에 2일이 걸리는 상담은 불가능하다. 오늘 기준으로 이전 상담을 완료하지 못한 경우 (j + lst[j][0] > i)예를 들어 오늘이 5일인데 2일에 4일짜리 상담을 했다면 오늘 기준으로 상담이 완료되지 않았으므로 상담 불가.3) 계산 시에는 오늘 날짜를 기..
푼 날짜 : 2024.10.02푼 문제 : [2491] / 수열사용한 언어 : python알고리즘 : DP 점화식 :max_dp[i] = max_dp[i-1]+1 (if lst[i-1] min_dp[i] = min_dp[i-1]+1 (if lst[i-1] >= lst[i]) 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력해야 하므로 dp 배열을 2개로 나누었다. 조건은i) 같거나 커지는 것ii) 같거나 작아지는 것 이므로이전 값과 비교해서 연속적으로 이전 값과 같거나 커질 때, 이전 값과 같거나 작아질 때를 계산했다.이후 각 배열의 max값을 찾아 더 큰 값을 출력하도록 구현했다. 코드 :import sy..
푼 날짜 : 2024.10.01푼 문제 : [2749] / 피보나치 수 3사용한 언어 : python알고리즘 : 분할정복, 거듭제곱, DP 푼 방법 : n의 범위를 잘 확인해야 한다. 값의 범위가 1000000000000000000 까지 가능하므로 메모리 초과가 날 가능성을 대비해야 한다!다행히 출력 시에는 1000000으로 나눈 나머지를 출력한다. 요기서 뽀인트🌟🌟 피사노 주기(Pisano Period)에 대해 알고 계신가요? 전 이 문제를 풀면서 알게 되었답니다. ദ്ദി・ᴗ・)✧ 피사노 주기란 ?피보나치 수를 K로 나눈 나머지의 주기를 의미한다!일정 주기가 반복되므로 해당 주기를 사용해 문제를 풀면 된다. 그래서 주기는 어떻게 구하는데 ?mod = 10^k 일 때, k > 2 라면, 주기..
푼 날짜 : 2024.09.21푼 문제 : [11659] / 구간 합 구하기 4사용한 언어 : python알고리즘 : 누적합 푼 방법 :구간이 정해질 때마다 합을 계산하는 것이 아닌 미리 누적된 합을 구해서 구간에 맞는 값을 출력하도록 했다.따라서 미리 반복문으로 합을 계산했고 start와 end값을 받아 sum_배열의 인덱스 end의 값에서 start-1의 값을 빼줬다. 코드: import sysN, M = map(int, sys.stdin.readline().split())lst = list(map(int, sys.stdin.readline().split()))sum_ = [0 for _ in range(N+1)]sum_[1] = lst[1]for i in range(1, N+1): sum_..
푼 날짜 : 2024.09.21푼 문제 : [11055] / 가장 큰 증가하는 부분 수열사용한 언어 : python알고리즘 : DP 점화식 :dp[i] = max(dp[i], dp[j]+lst[i]) (if lst[j] 여기서 뽀인트🌟 는 i번째 반복이 끝날 때 현재 dp[i]와 lst[i]를 비교해서 큰 값을 넣어주는 것!안그러면 lst[i]는 0보다 큰 수 인데 dp[i]에는 0이 들어가 있게 된다. 이렇게 되면 다음 계산에 영향을 준다!! 코드 :import sysN = int(sys.stdin.readline())lst = list(map(int, sys.stdin.readline().split()))dp = [0 for _ in range(N)]dp[0] = lst[0]for i in ..
![]()
푼 날짜 : 2024.09.14푼 문제 : [9465] / 스티커사용한 언어 : python알고리즘 : DP 점화식 :dp[0][i] = max(dp[1][i-1]+sticker[0][i], dp[1][i-2]+sticker[0][i]) dp[1][i] = max(dp[0][i-1]+sticker[1][i], dp[0][i-2]+sticker[1][i]) 점화식 도출 과정은 다음과 같다.아래와 같은 예시가 있을 때를 기준으로 계산해보겠다. 이는 sticker배열이다.501010020403050701060 dp 배열은 초기값을 이렇게 설정해주었다.5040 30100 초기값을 이렇게 설정한 이유는 다음과 같다.스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수..
![]()
푼 날짜 : 2024.09.13푼 문제 : [1149] / RGB거리사용한 언어 : python알고리즘 : DP 점화식 :dp[i][0] = colors[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = colors[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = colors[i][2] + min(dp[i-1][0], dp[i-1][1]) 초기값은 dp[0]을 colors[0]을 넣어주고 시작했다.그리고 dp테이블을 하나씩 채워나가는데, i번째의 0번째 요소를 채우기 위해서는 i-1번째의 0번이 아닌 1번과 2번 중 더 작은 값을 더해서 채워준다. 이렇게 해야 값을 최소로 만들며 더해갈 수 있기 때문이다. 코드 :impor..
