Algorithm123 [Swift][DP] 백준 2133번 (타일 채우기) 요구능력 : DP에대한 이해 코드설명 : 그림을 보면 n = 2일 때는 3가지 n = 3일 때는 0가지, n = 4일 때는 11가지가 나온다. n이 홀수일때는 0가지라는걸 직접 그리는걸 시도해보면 알것이다. n = 4일 때를 보면 빨간색으로 색칠한 부분 오른쪽을보자. n = 2일 때의 모양들을 가지고 있다. n = 2일 때의 모양이 3번 연속나오니까 dp[i] = dp[i - 2] * 3이라는 식은 쉽게 나온다. 하지만, 여기서 끝이아니고 맨 오른쪽에 기괴한 모양이 있다. 이 문제에서 핵심은 저 모양을 처리해주는 것이다. 기괴한 모양은 그려보면 알겠지만, n = 4일 때부터 2개씩 계속나온다. 그럼 +2를 해주면 되지않는가 싶지만 아쉽게도 저 모양마저 계속 옆에 모양이 달려서 나올 것이다. 그럼 n = .. 2021. 11. 11. [Swift][DP] 백준 11722번 (가장 긴 감소하는 부분 수열) 요구능력 : DP에대한 이해 코드설명 : 가장 긴 증가하는 부분수열 문제와 부등호만 틀리다. 가장 긴 감소하는 부분수열을 구하는 문제이다. 예제를 보자. 10 30 10 20 20 10 여기서 i인덱스(3)가 20을 가리킨다고 가정하고 설명하면 arr[0]부터 arr[2]까지의 수 중에서 arr[3]보다 큰 수가 있으면 dp[i]를 갱신해준다. 감소하는 부분수열이라서 앞에 나보다 큰 수가 있으면 dp[i]를 갱신해주는것이다. 그럼 dp[i]는 dp[0]부터 dp[2]까지 중에 조건을 만족하는 dp[]를 갖고 +1을 해줄것이다. dp[1]도만족하고 dp[2]도 만족하는 경우가 있으면 max()로 그 중 큰 값을 가져온다. 이유는 그 중 큰값은 이전에 더 많은 감소하는 부분수열을 갖고있을 것이기 때문이다. .. 2021. 11. 10. [Swift][DP] 백준 11055번 (가장 큰 증가 부분 수열) 요구능력 : DP에대한 이해 코드설명 : 이 문제는 가장 큰 증가 부분수열로 이전에 풀었던 가장 긴 증가 부분수열이랑 비슷하다. 우선 dp를 구하는 방법부터 알아보자 10 1 100 2 50 60 3 5 6 7 8 위와 같이 예제가 있을 때 dp[1] = 1 dp[2] = 101 dp[3] = 3 . . . 이렇게 될것이다. dp[x] = y라고 했을 때 x번 인덱스까지 가장 큰 증가하는 부분수열은 y라는 의미이다. 이제 점화식을 구하면 되는데 dp[1]도 함께 처리하기 위해 dp[i]에 arr의 값을 전부 넣어준다. 그리고 arr을 비교하면서 dp[i]의 값을 정해준다. 점화식 dp[i] = max(dp[j] + arr[i - 1], dp[i]) arr에서 i - 1을 해준건 arr의 인덱스는 0부터.. 2021. 11. 10. [Swift][BFS] 백준 7576번 (토마토) 요구능력 : BFS에 대한 이해 코드설명 : 이 문제의 핵심 1. 인접한 왼쪽, 오른쪽, 앞, 뒤 네방향에 있는 토마토에 영향을 준다. 2. 익은 토마토가 있는 지점부터 시작해야한다.(여러개가 있을경우 여러군데에서 시작한다. 예제3번 참조) 3. 토마토를 다익히지 못했을 경우를 생각해야한다.(예제2번같은경우) 4. 따로 Queue관련해서 지원되는게 없는 언어의 경우 시간초과에 유의한다.ㅠ 1. 1로 시작하는 시작지점들을 찾아서 Queue에 넣어둔다. for i in 1...m{ for j in 0.. 0 && nx = 0 && ny < n{ if arr[nx][ny] == 0{ arr[nx][ny] = 1 depth[nx][ny] = depth[pop.0][pop.1] + 1 queue.append((.. 2021. 11. 9. 이전 1 ··· 5 6 7 8 9 10 11 ··· 31 다음
