백준177 [Swift][DP] 백준 14051번 (퇴사) 요구능력 : DP에 대한 이해 코드설명 : 이 문제는 삼성SW역량테스트? 거기서 나온문제라고 한다. 1. 입력받기 let n = Int(String(readLine()!))! var t: [Int] = Array(repeating: 0, count: n + 1) var p: [Int] = Array(repeating: 0, count: n + 1) var dp = Array(repeating: 0, count: 1001) for i in 1...n { let TP = readLine()!.split(separator: " ").map{Int(String($0))!} t[i] = TP[0] p[i] = TP[1] dp[i] = p[i] //넣어놔야 아래코드에서 비교가능 } 2. DP코드 짜기 for i i.. 2021. 10. 8. [Swift][BFS] 백준 2178번 (미로탐색) 요구능력 : BFS에 대한 이해 코드설명 : 최소의 이동을 요구하는 문제는 BFS로 접근하는게 맞는것같다. DFS로도 풀 수는 있지만 DFS는 모든 경우의수를 다 돌아보기 때문에 자칫하면 시간초과가 날 수 있다. 이 문제는 문제에서 최소의 이동을 요구했기 때문에 BFS로 풀어볼 것이다. 1. n,m 과 좌표의 크기 받기 let nm = readLine()!.split(separator: " ").map{Int(String($0))!} let (n, m) = (nm[0], nm[1]) var arr = [[Int]]() for _ in 0..= m {continue}// nx와 ny가 배열밖으로 넘어가는것을 방지 if arr[nx][ny] == 0 {continue} //1일때만 이동가능하기 때문에 0일떄.. 2021. 10. 8. [Swift][DP] 백준 1699번 (제곱수의 합) 요구능력 : DP에 대한 이해 코드설명 : 우리는 여기서 최소개수를 구해야한다. 모든 경우의수를 비교해서 최소개수를 구하면 된다. 11은 최소 3개항의 제곱수로 표현 가능하다고 한다. 1부터 8까지만 찾아보자. 1 1의제곱 2 1의제곱 + 1의제곱 3 1의제곱 + 1의제곱 + 1의제곱 4 1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 2) 2의제곱 5 1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 2) 1의제곱 + 2의제곱 6 1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 2) 1의제곱 + 1의제곱 + 2의제곱 7 1) 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 + 1의제곱 2) 1의제곱 + 1의제곱 + 1의제곱 + 2의제.. 2021. 10. 7. [Swift][DP] 백준 14002 (가장 긴 증가하는 부분 수열4) 요구능력 : DP에 대한 이해 코드설명 : 첫번째로 가장 긴 증가하는 부분수열의 크기를 구해야하는데, 먼저 풀고오는 것을 추천한다. 이 문제에서 추가된 부분은 수열을 출력해주는것이다. dp에 우리가 저장한 수열 크기의 순서는 arr에 저장된 수열의 순서와 동일하다. 이게 무슨소린고 하면 아래 그림과 같다. 이거 처음에 나도 뭔소린가 했는데 밑에 var order = dp.max()! 부분부터 손디버깅 해보면서 써봐야 안다. 직접 생각하면서 써봐라. 참고로 아래 코드에서는 인덱스를 의도적으로 맞추지는 않았는데, dp값을 처음에 1로 초기화해놔서 정답이된다. (참고 : 어차피 배열의 뒤쪽에 있는 수가 큰 수 이므로 배열의 뒤쪽부터 찾아주는것이다.) 이제 이 인덱스가 같은점을 이용해서 문제를 푸는데, dp값이.. 2021. 10. 6. 이전 1 ··· 22 23 24 25 26 27 28 ··· 45 다음
