본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

Algorithm/Dynamic28

[동적계획법, 난이도 중하] 백준 2579번 계단 오르기 이 문제의 주어진 조건을 요약하자면, 계단을 3칸 연속으로 밟을 수 없고 마지막 칸은 무조건 밟아야 한다는 것이다. 배열 save를 n번째 계단까지 올랐을 때 얻을 수 있는 최대 점수, 배열 floors을 초기 입력된 계단 점수 배열이라 하면 이 문제의 점화식은 이렇게 된다. save[i] = maxs((save[i - 3] + floors[i - 1] + floors[i]), (save[i - 2] + floors[i])); 이다. 왜 이런 식이 나오는지는 아래 그림과 같이 설명하겠다. 위 그림에서 연한 노란색은 이미 DP로 처리한 부분이고 진한 노란색은 밟을 수 있는 계단들이다. 즉, 계단을 연속 3칸으로 밟는 것을 피하기 위해선 위와 같은 그림의 (O) 케이스가 되어야 하는데 3번째 케이스는 왜 계.. 2020. 8. 18.
[동적계획법, 난이도 중] 백준 1149번 RGB거리 집에 색을 칠하는 조건 3가지가 명시되어있다. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 간단하게 요약하자면 인접한 집끼리는 다른 색이어야 한다는 것이다. 즉 n번째 집까지 칠했을 때 n번째 집이 R이라면 비용의 최솟값은 n-1번째 집이 G색일경우의 총 비용의 최솟값과 n-1번째 집이 B색일경우의 총 비용의 최솟값중 더 작은 값. 그리고 n번째 집까지 칠했을 때 n번째 집이 G이라면 비용의 최솟값은 n-1번째 집이 R색일경우의 총 비용의 최솟값과 n-1번째 집이 B색일경우의 총 비용의 최솟값중 더 작은 값. 그리고 n번째 집까지 칠했을 때 n번째 집이 .. 2020. 8. 18.
[동적계획법, 난이도 하] 백준 1932번 정수 삼각형 동적계획법을 처음 배우는 분들이 동적계획법에 대해 감을 익히기 적합한 난이도의 문제이다.이 문제보다 쉬운 DP문제는 포스팅하지 않을 것이다. 입력은 인덱스 0부터가 아닌 1부터 시작한다.DP는 대체로 이런 식으로 입력해야 편한 것 같다. 아래 표는 예제 입력1을 기준으로 작성했다. INPUT[1][1]값은 DP[1][1]에 그대로 넣어주고 (1년전에 본인이 짠 아래 소스코드에서는 DP배열이름을 root로 했다)인덱스 2부터 DP를 수행하여 DP[i-1][j-1]와 DP[i-1][j]중 최댓값과 INPUT[i][j]를 더해서 DP배열을 채워나가면 된다. 모든 과정을 마친 최종 DP 표이다. 맨 아래 5행의 요소들중 최댓값 30이 이 케이스의 답이 된다. #include #include using names.. 2020. 8. 18.
[동적계획법, 난이도 중상] 백준 10942번 팰린드롬? 시간 제한은 0.5초이고 데이터범위는 100만인 시간 제한이 매우 빡센 문제이다. 이 때문에 문제의 난이도 평가를 중상으로 할지 상으로 할지 고민했다. 본인은 동적계획법으로 이렇게 접근했다. 예) 문제 입력에서 수열의 크기 N=12 그리고 칠판에 적은 수를 1 2 2 1 2 1 2 2 1 2 2 2로 가정했을 때의 dp표이다. 홍준이가 한 질문 최대 100만개는 이 표를 참고하여 대답해줄 것이다. 행은 팰린드롬의 길이, 열은 홍준이가 칠판에 적은 숫자를 나열한 것이다. 이 표는 팰린드롬의 중심을 기준으로 했을 때 길이 별 팰린드롬 여부를 나타낸 것이다. 예를 들어 7행 5열에서 "o"로 표시되어 있는데 흥준이가 칠판에 적은 숫자들중 5번째인 "2"를 중심으로 했을 때 연속 수의 길이가 7인 숫자열은 팰린.. 2020. 8. 17.
[동적계획법, 난이도 중상] 백준 1520번 내리막 길 이 문제는 동적계획법과 DFS를 동시에 적용해야 하는 문제이다. 백준 1890번 점프와 접근법은 비슷하다. https://kimcoder.tistory.com/47 [동적계획법, 난이도 상] 백준 1890번 점프 동적계획법과 DFS를 동시에 적용해야 하는 높은 난이도의 문제이다. 본인은 이제부터 DFS를 마주쳤다 싶으면 바로 그래프로 도식화해서 풀 것이라고 다짐했다. 이 문제는 두 스텝으로 나누어서 �� kimcoder.tistory.com 경로벡터를 이용하였으며 도착점부터 시작점까지 역으로 DFS를 수행하였다. 자세한 설명은 위 링크에 있는 백준 1890번 점프 풀이를 읽고오면 된다. 아래 그림도 백준 1890번 점프에서 도식화 했던 원리랑 똑같다. 문제에 따른 push_back 기준만 다를 뿐이다. .. 2020. 8. 17.
[동적계획법, 난이도 상] 백준 1890번 점프 동적계획법과 DFS를 동시에 적용해야 하는 높은 난이도의 문제이다. 본인은 이제부터 DFS를 마주쳤다 싶으면 바로 그래프로 도식화해서 풀 것이라고 다짐했다. 이 문제는 두 스텝으로 나누어서 해결했다. 1. 점프할 수 있는 좌표를 모두 경로벡터에 넣는다. 여기에서는 간선이라고 봐도 무방하다. 점프를 했을 때 맵 밖으로 벗어나는 경우도 신경 써줘야한다. 맵 밖으로 떨어진 좌표는 경로벡터에 넣지 않으면 된다. 오른쪽, 아래쪽만 점프 가능하다는 사실을 잊지말자. DFS를 도착점부터 역으로 수행할 것이기 때문에 간선 연결 방향은 반대로 했다. >> a[i+jump*dx[k]][j+jump*dy[k]].push_back(make_pair(i, j)); 이 과정이 끝나면 경로는 이렇게 된다. 맨 오른쪽 맨 아래 '0.. 2020. 8. 17.
[동적계획법, 난이도 중하] 백준 11726번 2xn 타일링 이 문제에 동적계획법을 적용시키면 2x1, 2x2, 2x3, ... 2x(n-1),2xn 이런식으로 차례대로 이전 값을 이용하여 계산해 나가면 된다. 이전 타일값에 1x2, 2x1 타일을 붙일 수 있는 경우의 수를 따져보자. 위의 전체 타일의 넓이는 2xn이다. 그리고 갈색 타일의 넓이는 1x2, 2x1이다. 이렇게 2x(n-1) 타일에 2x1 타일을 1개 추가하는 방법 -> 1가지 2x(n-2) 타일에 1x2 타일을 2개 추가하는 방법 -> 1가지 2x(n-2) 타일에 2x1 타일을 2개 추가하는 방법은 포함하지 않는다. 왜냐하면 이는 2x(n-1) 타일에 2x1 타일을 1개 추가하는 방법과 같은 경우이기 때문이다. 경우가 중복된다는 의미다. 즉 save[n]=save[n-1]+save[n-2] 라는 .. 2020. 8. 16.
[동적계획법, 난이도 중하] 백준 1003번 피보나치 함수 피보나치 함수 fibonacci(n) 의 리턴값은 fibonacci(n-1)+fibonacci(n-2) 이다. fibonacci(0)은 0을 출력하므로 0이 1회 출현한다고 보고 fibonacci(1)은 1을 출력하므로 1이 1회 출현한다고 본다. 그렇다면 fibonacci(2)는 fibonacci(1)과 fibonacci(0)을 리턴하기 때문에 0,1이 1회씩 출현한다고 할 수 있다. fibonacci(3)까지 해보자. fibonacci(3)은 fibonacci(2)와 fibonacci(1)을 리턴하기 때문에 0은 1회, 1은 2회 출현한다고 할 수 있다. 자세히 나타내면 이렇다. fibonacci(2) -> 0 1회, 1 1회 fibonacci(1) -> 0 0회, 1 1회 fibonacch(3) 총.. 2020. 8. 15.
[동적계획법, 난이도 중하] 백준 9095번 1,2,3 더하기 1,2,3 이 3개의 정수의 덧셈으로 n을 표현해야 하기 때문에 1,2,3 을 표현하는 방법은 미리 구해놓자. 1 -> (1) 1가지 2 -> (1+1),(2) 2가지 3 -> (1+1+1), (2+1), (1+2) , (3) 4가지 n=4일때부터 순차적으로 DP를 진행해야 하는데 동적계획법은 이전에 계산 했던 값들을 가지고 현재 정보를 계산하는 알고리즘이다. 이전 값은 이렇게 응용하면 된다. 3을 1,2,3의 합으로 표현하는 방법은 -> (1+1+1), (2+1), (1+2) , (3) 총 4가지 인데 이 4가지 그룹에서 각각 1을 더해주면 4가 나오지 않을까? 그리고 2를 1,2,3의 합으로 표현하는 방법은 -> (1+1),(2) 총 2가지 인데 이 2가지 그룹에서 각각 2을 더해주면 4가 나오지 않.. 2020. 8. 15.

티스토리툴바