알고리즘

푼 날짜 : 2024.10.12푼 문제 : [2096] / 내려가기사용한 언어 : python알고리즘 : DP  접근 방식 :처음에 일반적인 DP로 풀다가 메모리 초과가 났다.생각해보면 DP는 현재값 계산을 위해 이전 값을 활용하기 때문에 다음 계산 전 현재 값을 이전 값으로 덮어씌웠다.# 덮어쓰기dp[0][0] = dp[1][0]dp[0][1] = dp[1][1]dp[0][2] = dp[1][2]dp2[0][0] = dp2[1][0]dp2[0][1] = dp2[1][1]dp2[0][2] = dp2[1][2] 이렇게 하면 모든 DP 배열을 채우지 않고 단순하게 계산할 수 있다.  코드 :import sysN = int(sys.stdin.readline())dp = [[0, 0, 0], [0, 0, 0]]..

푼 날짜 : 2024.10.12푼 문제 : [7569] / 토마토사용한 언어 : python알고리즘 : BFS  접근 방식 :dx = [1, -1, 0, 0, 0, 0]dy = [0, 0, 1, -1, 0, 0]dz = [0, 0, 0, 0, 1, -1] 위 아래 왼쪽 오른쪽 앞 뒤 이렇게 6방향을 처리해줘야 했으므로 위와 같이 구성했다.사실 그렇게 어렵지는 않은 문제라 나머지는 코드의 주석으로 확인하면 좋을 것 같다 !   코드 :import sysfrom collections import dequeM, N, H = map(int, sys.stdin.readline().split())graph_ = [[] for _ in range(H)]for i in range(H): for _ in range..

푼 날짜 : 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 ..