Dp

2024년 3월 4일 알고리즘 문제풀이 문제 점프와 순간 이동 난이도 Lv.2 코드 일반적인 DP문제라고 생각했다. 조금 어려운 편이긴 하지만, 기존에 충분히 풀어봤던 유형이라 금방 풀 수 있었다. 도착지로 이동하는 마지막 방법을 점프라고 고정하고 생각했다. 1차 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 def solution(n): # 3칸까지는 고려할 필요 없음 if n <= 3: dp = [0, 1, 1, 2] return dp[n] # 그 이상일 때는 DP # 가장 최대 건전지 사용량은 그곳까지 점프로만 도달했을 때이므로 모든 곳을 최댓값으로 초기화한다. dp = [] for i in range(n + 1): dp.append(i) # 2,3일 때는 알맞게 초기화 dp[2] = 1 dp[3] = 2 # 4 이상일 때부터 DP for i in range(4, n + 1): # 반으로 나누었을 때 몫 k = i // 2 # 홀수여서 딱 절반인 곳이 존재하지 않을 때 if i % 2: # i까지 도달 비용 = 몫까지 도달하는 비용(dp[j]) + 몫부터 i까지 점프하는 비용(i-j) for j in range(k, i): dp[i] = min(dp[i], dp[j] + i - j) # 짝수여서 절반인 곳이 존재할 때 else: # 절반인 곳에서 순간이동하면 도착할 수 있으므로 절반에 도착하는 것과 같은 값 dp[i] = min(dp[i], dp[k]) for j in range(k + 1, i): dp[i] = min(dp[i], dp[j] + i - j) return dp[n] n칸 까지 갈 때, 절반인 n//2를 기준으로 생각하면 된다. 절반도 오지 못했을 떄 점프를 하는 것은 거기서 순간이동 하는 것보다 더 건전지 사용량이 소모될 것이기 때문이다. 예를 들어, 10 칸을 이동한다고 했을 때 ...

2024년 1월 15일 알고리즘 문제풀이 문제 피보나치 수 난이도 Lv. 2 코드 1 2 3 4 5 6 7 8 def solution(n): dp = [0 for _ in range(n+1)] dp[1] = 1 if n<2: return dp[n] for i in range(2,n+1): dp[i] = (dp[i-1]+dp[i-2])%1234567 return dp[n]

2023년 12월 12일 알고리즘 문제풀이 문제 멀리뛰기 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 def solution(n): answer = 0 dp = [0 for _ in range(n+1)] for i in range(1,n+1): if i == 1: dp[i] = 1 elif i == 2: dp[i] = 2 else: dp[i] = (dp[i-1] + dp[i-2])%1234567 answer = dp[n] return answer n번째 칸은 ...

2023년 12월 11일 알고리즘 문제풀이 문제 땅따먹기 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def solution(land): n = len(land) answer = 0 dp = [[0 for _ in range(4)] for _ in range(n)] dp[0] = land[0] def check(next_row,next_col): arr = [] for i in range(4): if i == next_col: continue arr.append(dp[next_row-1][i]) return max(arr) x = 1 while x < n: for i in range(4): dp[x][i] = check(x,i) + land[x][i] x += 1 answer = max(dp[-1]) return answer 각 행에는 4개의 열이 있다. 각 열에 올 수 있는 방법의 경우는 3가지이다. 예를 들어 2행 0열에 오는 방법은 2행 1열, 2행 2열, 2행 3열에서 오는 것이다. 이러한 원리를 바탕으로 DP를 설정했다. ...

2023년 12월 03일 알고리즘 문제풀이 문제 가장 큰 정사각형 찾기 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def solution(board): answer = 1 p = len(board) q = len(board[0]) dp = [[0 for _ in range(q)] for _ in range(p)] dp[0] = board[0] for i in range(p): dp[i][0] = board[i][0] for a in range(p): for b in range(q): if a-1>=0 and b-1>=0 and board[a][b]==1: dp[a][b] = min(dp[a-1][b-1],dp[a-1][b],dp[a][b-1])+1 answer = max(answer,dp[a][b]) return answer*answer 위 코드는 정확성은 통과했지만 효율성에서 문제를 겪었다. 이 로직은 board 상 1인 좌표마다 검사를 해 가장 큰 사각형의 한 변의 길이가 몇인지 모두 탐색한다. board의 좌표 갯수는 1000000 인데, 이를 평균적으로 500개씩 탐색하면 500000000(5억)이나 수행해야 한다. 결국 아래처럼 고쳐 통과되었다. ...

2023년 11월 28일 알고리즘 문제풀이 문제 3 x n 타일링 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def solution(n): dp = [0 for _ in range(5001)] dp[2] = 3 dp[4] = 11 for i in range(1,n+1): if n%2: return 0 if i%2: continue else: if not dp[i]: tmp = 2 tmp += dp[i-2]*dp[2] for x in range(2,i//2): tmp += dp[i-2*x]*2 dp[i] = tmp%1000000007 return dp[n] 진짜 어렵다. 홀수는 나올수 없으므로 무조건 0이라는 것은 일찍 발견했다. 하지만 일반항을 위한 점화식을 구하기가 어려웠다. 처음에 한 추론은 다음과 같다. ...

2023년 11월 17일 알고리즘 문제풀이 문제 2 x n 타일링 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 def solution(n): dp = [0 for _ in range(60001)] x = 1 while x <= n: if x == 1: dp[x] = 1 elif x == 2: dp[x] = 2 else: dp[x] = (dp[x-1] + dp[x-2])%1000000007 x += 1 return dp[n] 많이 볼 수 있는 DP문제이다. 2 x n 일땐 이전 조합들을 합친 것만으로도 다음 갯수를 산출할 수 있어서 크게 어렵지 않다. 수가 커지기 때문에 나머지로 표시해야 한다는 사실을 잠시 잊었다.. ...

2023년 11월 16일 알고리즘 문제풀이 문제 X만큼 간격이 있는 n개의 숫자 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 def solution(x, n): answer = [] d = x num = x while len(answer) < n: answer.append(num) num += d return answer 크게 어려울 것 없는 문제였다. 문제에 제한 조건이 주어지는데 while문에 추가하면 마지막 테스트 케이스에서 틀린다. 문제가 알아서 제한하여 준다는 뜻이니 걸지 말것. ...

2023년 9월 18일 알고리즘 문제풀이 문제 1 백준 1946 문제 링크 1차 시도 나의 생각 서류에서 1등을 한 사람의 면접 성적을 기준으로 삼았다. 이 기준보다 면접 성적이 높은 사람만 합격할 수 있다. 기준보다 면접 성적이 낮은 사람은 서류 성적도 당연히 낮다. 서류 1등의 성적을 기준으로 하였으니까.. 문제는 이 기준에서 설정한 사람들 내에서도 문제의 조건으로 탈락하는 사람이 생길 수 있다. 리스트를 2번 순회하였더니 시간초과가 나서 큐를 이용해 최소 힙을 구현하여 수행 시간을 줄였지만 오답처리 되었다. ...

2023년 9월 16일 알고리즘 문제풀이 문제 1 백준 1030 문제 링크 1차 시도 나의 생각 분할정복으로 풀면 되겠다고 생각했다. 정사각형 한 변의 길이는 1초마다 n이 곱해져 결국 s초 후 n의 s제곱 형태가 된다. s는 최대 10, n은 최대 8이므로 한 변의 길이는 최대 2의 30제곱이나 된다. 전체 정사각형 배치를 그린 후 원하는 부분만 출력하기엔 너무 크다는 뜻이다. 문제에서 출력하라고 요구하는 부분만 출력해야 한다. 이 부분이 너무 어려워서 다른 사람들의 풀이를 보고 공부한 코드이다. l은 위에서 말했던 n의 s제곱이자 s초 후 정사각형의 한 변의 길이이다. main 함수는 평면의 한 변의 길이와 검은색인지 확인할 곳의 행렬을 x,y로 받는다. 중앙의 k x k 크기의 사각형에 포함된다면 검은색이므로 1을 반환한다. ...