백준177 [Swift][DP] 백준 1932번 (정수삼각형) 요구능력 : DP에 대한 이해 코드설명 : 문제를 읽고 우선적으로 생각해볼 수 있는건 dp[i]를 구하려면 이전에 어떤 값을 골랐는지가 중요하다는것이다. 삼각형에서 한줄을 i줄이라고 한다면 몇번째 수를 선택했는지가 중요한것이다. 이것을 보고 dp는 2차원 배열로 이루어지겠구나를 생각했다. 조건은 왼쪽대각선 혹은 오른쪽대각선으로만 선택할 수 있는것이다. 문제의 예제를 보고 8, 1, 0이 있는 줄을 dp[i]라고 생각해보면 이전 줄에 3, 8이 있다. 우선 8을 선택했을 때의 최대값을 구하기 위해서는 3에서 내려오는 방법밖에는 없다. 왼쪽 대각선으로 내려오는 것 밖에 없는것이다. 다음으로 1을 생각해보자. dp[i][1]을 구하는것인데 1은 왼쪽대각선과 오른쪽대각선 2가지가 모두에서 내려올 수 있다. 다.. 2021. 11. 9. [Swift][BruteForce] 백준 2529번 (부등호) 요구능력 : 백트래킹에 대한 이해 코드설명 : 맨 아래에 수정된 코드있습니다. 이 문제는 0~9까지의 수 중에서 부등호의 갯수 +1 개만큼의 수를 뽑아서 부등호 조건에 맞출 수 있는지를 묻는 문제이다. 문제에서 요구하는 부분 1. 부등호의 개수 + 1개 만큼의 수 2. 뽑은 수를 가지고 부등호 조건을 만족하는지 확인 3. 부등호 조건을 만족하는 수들의 최소값과 최대값 출력 1. 1번부터 해결하면 n과m문제를 떠올리면 된다. 이 문제에서는 0부터 9까지의 수 중에서 선택하라고 했고 선택된 숫자는 모두 달라야한다고 했으므로 방문처리까지 해주면서 방문하는 수를 k + 1 (부등호의 개수 + 1)개 뽑았을 때 부등호조건에 비교하기위해서 result라는 배열에 저장해줬다. for i in 0...9 { if !.. 2021. 11. 8. [Swift][DP] 백준 2156번 (포도주 시식) 요구능력 : DP에 대한 이해 코드설명 : 문제의 핵심은 3잔연속으로 선택하면 안된다는점과 가장 많은양의 포도주를 마셔야한다는점이다. 보통 이렇게 숫자가 나열되어있고 가장많은양의~, ~~연속 이런식으로 나오면 DP의 2가지 요소가 충족해서 DP로 풀면된다. 6 10 13 9 8 1이 있다. 어차피 첫번째 dp의 최대값은 주어진 배열의 맨앞의 수이다. 쌓일 수 있는 값이 없기때문이다. dp[1] = arr[1] 마찬가지로 dp[2]도 3잔연속되는 경우가 없기에 dp[2] = arr[2]이다. 그럼 이제, dp[3]을 구해보자. dp[3]은 세번째 잔이기 때문에 문제의 조건을 다뤄줘야한다. 이렇게 세가지 경우의 수중 최댓값을 찾으면 그게 점화식의 완성이다. 점화식은 아래 코드에 적혀있습니다. 후기 : 규칙.. 2021. 11. 8. [Swift][DFS] 백준 2667번 (단지번호붙이기) 요구능력 : 문제의 조건과 DFS에 대한 이해 코드설명 : 문제를 보면 단지를 전부 돌아봐야 할 것 같다. 전부 돌면서 1이 뭉쳐있는곳은 하나의 단지라고 본다. 1이 뭉쳐있는곳을 DFS로 돌려서 모두 탐색해봐야한다. 그렇다면 아직 방문하지 않은곳이면서 1인좌표를 찾아서 dfs를 돌면된다. for i in 0..= 0 && ny < n { if arr[nx][ny] == 1 && !visited[nx][ny] { dfs(nx, ny) } } } } 후기 : 비슷한류의 문제를 겪어본적이 있는거같은데...뭐더라 let n = Int(String(readLine()!))! var arr: [[Int]] = [[]] var visited = Array(repeating: Array(repeating: false.. 2021. 11. 5. 이전 1 ··· 19 20 21 22 23 24 25 ··· 45 다음
