백준 문제풀이(파이썬)

계단을 오르면서 밟는 발판의 최댓값을 구하는 문제다. 이전에 풀었던 삼각형 문제나 집 색깔 문제처럼 뒤에서 차례대로 더하면서 갱신해주는 방식을 생각했지만, 경우가 깔끔하게 나뉘는 것도 아니었고 규칙이 있는 것도 아니었다. 꼭 나눠줘야 하는 경우는 i번째 발판(s[i-1])을 밟기 전에 바로 전 발판(s[i-2])을 밟았는지 전전 발판(s[i-3])을 밟았는지 경우를 나누어 주고, 바로 전 발판(s[i-2])을 밟았다면 그 바로 전 발판(s[i-3])은 밟지 못하기 때문에, 전전 발판(s[i-4])까지 밟기까지의 경우의 최댓값(dp[i-3])에 s[i-1] 값과 s[i]값을 더해준 경우와 전전 발판(s[i-3])을 밟은 경우의 최대값을 비교해서 큰 값을 dp에 append 해주면 i번째 발판까지의 최대값이..

최대의 합을 찾아가는 문제다. 백트래킹으로 구현할 수 있지만, 이 문제 또한 DP문제이기 때문에 시간 초과를 생각하고 문제를 풀어야 한다. 위에서 아래로 내려가면서 합을 더해주면서 진행하면 밑의 값이 무엇이 올 지 모르기 때문에, 모든 경우를 다 생각해야 한다. 반면에, 아래에서 위로 올라가면서 합을 갱신하면 모든 경우를 돌지 않아도 된다. 이런 방식은 이전에 풀었던 RGB거리 문제(https://aodtns.tistory.com/20)와 유사하다. 백준 1149번 - RGB거리 RGB를 같은 색이 반복되지 않게 나열하는 문제다. i번째 집의 색을 각각 빨강(0), 초록(1), 파랑(2)으로 칠하는 비용을 갱신해주면서 반복해주면 된다. i번째 집의 색을 빨강으로 칠한다면, i-1번째 aodtns.tist..

RGB를 같은 색이 반복되지 않게 나열하는 문제다. i번째 집의 색을 각각 빨강(0), 초록(1), 파랑(2)으로 칠하는 비용을 갱신해주면서 반복해주면 된다. i번째 집의 색을 빨강으로 칠한다면, i-1번째 집의 색을 초록, 파랑으로 칠하는 비용 중에서 더 작은 값을 칠해주면 되기 때문에 파이썬의 기본 함수 min을 사용하여 구해준 뒤, i번째 집을 빨강으로 칠하는 비용을 더해줘서 갱신을 해준다. 그 뒤 i+1번째도 같은 원리로 갱신이 되고 결국 N번째에는 각 최소 비용이 들어갈 것이기 때문에 그 3개 중에 최솟값을 찾아주면 된다. ##변수 선언 부분## cost = [] ##메인 함수 부분## if __name__ == "__main__": N = int(input()) cost = [[int(x) f..

노트에 그려가면서 풀면 왜 문제에서 첫 10개의 숫자를 줬는지 대충 감이 온다. 삼각형을 그려보면 N번째 삼각형의 한 변의 길이는 바로 이전 삼각형의 변의 길이에 5번째 전(한 바퀴 돌고 난 뒤) 삼각형의 변의 길이를 더한 값과 같다는 것을 알 수 있다. 그러므로 점화식은 P(N) = P(N-5) + P(N-1)이다. 이를 이용해서 재귀 함수를 사용하지 않고 반복문을 사용해서 배열을 append 해주면 된다. ##변수 선언 부분## p = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9] ##메인 함수 부분## if __name__ == "__main__": T = int(input()) for i in range(T): N = int(input()) for j in range(11,N+1):..

주어진 재귀 함수를 동적 계획법으로 푸는 문제다. 처음에 봤을 때는 이전에 풀었던 피보나치 문제처럼 규칙이 있으면, append 해주면서 풀면 되겠구나 싶었지만, 딱히 규칙같은건 없었다. 재귀 함수를 보면, a,b,c의 입력이 -50~50이고, 21~50은 20,20,20으로 대체되고, -50~0은 1이 리턴되기 때문에 생각해야할 것은 1~20일 때다. 구한 값을 a= 1, b=1, c=1부터 a=20, b=20, c=20까지 총 20*20*20의 8000개의 배열이 필요할 것이다. 넉넉하게 10000개의 배열을 0으로 초기화하여 선언한다. 그 뒤 index를 계산해보면, 인덱스는 (a - 1) * 400 + (b - 1) * 20 + (c - 1)이 나온다. 만약 w[index]에 값이 없으면 캐싱해주..

피보나치 함수를 구현하는 문제이다. 하지만 일반적인 재귀함수를 이용하는 방법으로 풀면 시간 초과가 뜰 것이다. 이를 해결하기 위해서 동적 계획법에 대해 알아보자. 동적 계획법 (Dynamic Programming)이란, 하나의 복잡한 문제를 동일한 구조의 간단한 문제들의 합으로 푸는 방법이다. 하나의 문제를, 그것과 동일한 형태의 작은 문제들로 나눈 뒤, 작은 문제들을 풀어내어 최종적인 문제에 접근하는 것이 목적이다. 메모이제이션 (memoization)이란, 문제를 푸는 도중에, 여러개의 작은 문제들이 도출되는데, 이 문제들이 겹쳐지면 중복계산이 발생하여 시간이 오래 걸린다. 따라서, 한번 푼 문제는 중복하여 풀지 않도록 Cache를 저장해주는 작업을 해준다. 이를 메모이제이션이라고 한다. 동적 계획법..

팀을 나눠서 각 선수들의 케미(상호간의 능력치)를 구하는 문제다. 문제를 읽어보니 일단 N명의 선수를 받은 뒤 반으로 나누어서 팀을 구하고 각 팀 인원들의 케미를 구하면 되겠구나 싶었다. 팀을 나눌 때는 팀 하나가 정해지면 다른 팀은 바로 결정이 되기 때문에 두 팀을 따로 구할 필요가 없다. 팀을 나누려면 N과 M(1)문제에서 사용한 방법을 응용하면 된다. 백준 15649번 - N과 M(1) 완전 탐색중의 한 방법인 백트래킹 알고리즘에 대한 문제이다. 백트래킹의 특징은 탐색과정 중에 정답이 될 수 없는 조건에 해당되면 가지치기(Pruning)하여 효율을 높일 수 있다는 점이다. DFS와 aodtns.tistory.com 만약 N = 4라고 생각해 보면, A팀은 (0,1), (0,2), (0,3) 의 세 ..

처음에 문제를 보고 숫자도 문자열로 받은 뒤 입력 개수만큼 문자'+','-','x','//'를 받아서 하나씩 빼주면서 정수로 변환해서 계산을 해야겠다고 생각했다. 조금 복잡한 것 같지만 생각보다 그렇게 복잡하지는 않았다. 하지만 문제는 중복되는 순열도 모두 계산을 해야 하는 것이었다. 6개의 숫자를 받는다고 할 때 연산자가 만약 + + + - - 라고 할 때 내 계산을 그저 5! 의 경우를 모두 계산했다. 중복 문제를 해결하지 못했다. 그래도 예제의 출력 값은 제대로 나와서 백준에 제출했을 때 적어도 시간 초과라도 뜨겠구나 싶었지만, 틀렸다고 나왔다. 어느 부분에서 출력의 오류가 있었는지는 잘 모르겠다. ##함수 선언 부분 def calculator(Numbers): global min, max if l..