전체 글

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

푼 날짜 : 2024.09.011푼 문제 : [1303] / 전쟁 - 전투사용한 언어 : python  푼 방법 :DFS로 접근하였다. N명이 뭉쳐있을 때는 N*N의 위력을 낼 수 있다.  같은 병사가 몇 명이 뭉쳐있는지를 계산하고 그 인원의 제곱을 구한다.우리 병사와 적국 병사의 위력의 총합을 출력한다. 범위 계산과 추가적으로 현재의 target과 일치하면 지속해서 DFS를 실행하고 아니라면 제곱값을 총합에 더하여 다음 과정을 진행하도록 구현했다.  코드 :import sysN, M = map(int, sys.stdin.readline().split())graph_ = []visited = [[0 for _ in range(N)] for _ in range(M)]for _ in range(M): ..

푼 날짜 : 2024.09.06푼 문제 : [13549] / 숨바꼭질3사용한 언어 : python  푼 방법 :BFS로 접근했다.여기서 이전 문제들과 달랐던 점은 다른 이동은 1초 후 이동, 순간이동을 하는 것은 0초 라는 것! 따라서 계산 순서를 [순간이동(*2칸), -1칸, +1칸] 으로 두고 코드를 작성하였는데 지금 생각해보니 순간이동 가능한 범위(max는 동생의 위치 *2 정도로 잡으면 될 것 같다.)를 먼저 다 계산하고 추후 계산(+1, -1)을 해도 될 것 같다는 생각이 들었다.   코드 :import sysfrom collections import dequeN, K = map(int, sys.stdin.readline().split())dx = ['*', '-', '+']def BFS(vis..