본문 바로가기

Algorithm123

[Swift][DP] 백준 1149번 (RGB거리) 요구능력 : DP에 대한 이해 코드설명 : 26 40 83 39 60 57 13 89 99 문제를 보면 앞뒤에 나온 컬러는 사용할 수가 없다. 우선 조건없는 점화식을 만들어보자. 조건이 없다면 최소값을 누적하는 dp이다. 그렇다면 dp[i] = dp[i - 1] + arr[i][최소가되는부분] 이 만들어진다. dp[i - 1]에는 이미 최소값이 만들어진것이라 가정한것이다. 조건을 넣은 점화식을 만들어보자. 우선 조건은 3가지가 있다. R일때, G일때, B일때. dp[i]가 R이면 이전에는 G와 B가 나와야한다. 아래 코드에서는 R이 0, G가 1, B가 2 이다. dp[i]를 R로 칠한경우의 DP가 있을것이고, G로 칠한경우의 DP가 있을것이고, B로 칠한경우의 DP가 있을것이다. 그러므로 arr배열에 .. 2021. 11. 4.
[Swift][BruteForce] 백준 14889번(스타트와 링크) 요구능력 : 백트래킹에 대한 이해 코드설명 : 이 문제는 팀을 n명중에서 n/2명을 뽑아야된다는게 핵심이다. 그래서 나는 n과 m을 떠올려서 백트래킹 방법으로 팀부터 뽑았다. 다음으로, 내가 스타트팀원들을 뽑았으니까 링크팀원들은 자동적으로 스타트팀원들을 뺀 사람들이 되겠다. 스타트팀원들을 n/2명을 뽑으면 맨 아래 for문에서 방문처리가 되게된다. 그럼 방문처리가 안된 사람들이 링크팀원들인 것이다. n/2명을 뽑았을 때 team1과 team2를 0으로 초기화해준다.(이전에 뽑았던 값을 재사용하게 되는 경우가 없게하기 위함) 그리고 for문으로 arr배열의 전체 인덱스를 돌아주면서 방문하지 않은것은 링크팀(team2)원들이기 때문에 방문하지 않은경우에 team2에 더해주고 방문했다면, 맨 아래에서 뽑은 스.. 2021. 11. 4.
[Swift][BruteForce] 백준 6603번 (로또) 요구능력 : N과M에 대한 이해 코드설명 : 문제를 보면 N과M시리즈와 매우 유사하다. 1. N개의 수 중에서 6개를 뽑는다. 2. 비내림차순 1. 문제의 조건을 맞춰주는 부분 문제에서는 0이 입력되기전까지 계속해서 받으라고 했으므로 while문으로 처리를 해준다. 그리고 배열에서 맨 앞의수는 필요없으니 버려준다.(어차피 N개의 수에서 6개만 뽑아서 오름차순해줄것이기 때문이다.) while true{ input = readLine()!.split(separator: " ").map{Int(String($0))!} if input[0] == 0 { break }else { input.removeFirst() dfs(0, 0) print("") } } 2. 백트래킹을 이용해서 N개의 수중 6개를 뽑아준다. .. 2021. 11. 2.
[Swift][DP] 백준 15988번 (1, 2, 3더하기 3) 요구능력 : DP에 대한 이해 코드설명 : 문제를 설명해주면 1과 2와 3중 한개 이상을 더해서 주어진 수를 만드는 문제이다. 처음 접해보시는 분들은 어렵게 느껴질 수도 있는데, 이 문제만 정확히 이해하면 다른 더하기 DP문제들은 꽤 쉽게 풀릴것이다. 그림을 보면 파란색글씨로 + 1, + 2, +3 을 해놓은것을 볼 수 있다. 1, 2, 3더하기니까 이렇게 1, 2, 3을 기준으로 앞에 들어와야 할 수를 구해준다. 이게 가능한건 DP이기 때문에 가능하다. +1, +2, +3앞에 오는 수가 무엇이든간에 이미 1과 2와 3의 조합으로만 더해놨기 때문이다. 위의 그림에 5를 보면 이전에 4를 1과 2와 3의 조합으로 해놨기 때문에, 4에 조합된 개수를 그대로 가져오는걸 볼 수 있다. 이해가 안간다면 여러번보고.. 2021. 11. 2.

티스토리툴바