백준177 [Swift][BFS] 백준 14226번 (이모티콘) 요구능력 : BFS에 대한 이해와 응용 코드설명 : 이 문제에서 가장 중요한건 조건을 보고 핵심을 캐치하는것이다. 내가 생각했을 때 핵심은 화면, 클립보드, 시간을 구성해서 큐와 visited배열을 짜는것이다.(조건은 문제를 잘 읽어보면 생각나기때문) 화면, 클립보드, 시간이 함께 움직이기(?) 때문에 하나의 튜플로 정의했다. pop.0은 화면 pop.1은 클립보드 pop.2는 시간을 의미한다. 일반적으로 BFS에서 같은곳을 두번이상 방문하면 최단시간, 최단경로가 나오지 않으므로 방문처리를 해주는데, 방문여부를 표시하는 visited는 visited[1][0]이면 화면에 1개있고 클립보드가 0개있을 때 라는 의미이다. 이렇게 해준이유는 화면개수와 클립보드개수에 따라 다음번에 while문을 돌때 시간에 영.. 2021. 11. 11. [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. 이전 1 ··· 18 19 20 21 22 23 24 ··· 45 다음
