본문 바로가기

Baekjoon78

[Swift][BruteForce] 백준 1182번 (부분수열의 합) 요구능력 : 백트래킹 코드설명 : 이 문제에서 생각해봐야할건 "어떻게해야 모든 부분수열을 구할 수 있을까?" 이다. -7, -3, -2, 5, 8 이 있을 때 {-7} {-7, -3} {-7, -3, -2} {-7, -3, -2, 5} {-7, -3, -2, 5, 8} {-7, -2} ... 그리고 -3부터 시작해서 위처럼 쭉 나열하고 -2부터, 5부터, 8부터... 이렇게 구하면 모든 부분수열을 구할 수 있다. 부분수열을 구하는건 그럼 백트래킹으로 해야겠다. 백트래킹으로 모든 경우의수를 다 검사해보는것이다. 백트래킹을 하면서 우리가 구해야하는건 부분수열의 합이다. 그래서 sum에 입력받은 연속된수열의 합을 백트래킹하면서 구했고, 그 합이 구하고자하는 값인 s와 같아졌을 때 그리고 문제에서 크기가 양수인.. 2022. 1. 11.
[Swift][BFS] 백준 13549번 (숨바꼭질3) 요구능력 : BFS에 대한 이해 코드설명 : 이전단계 문제인 숨바꼭질을 풀고오면 수월하게 풀리는문제이다. 먼저 풀고오는걸 권장하는게아닌 먼저풀고오는게 맞는거같다. 큐에 삽입한다는 말은 움직인다는 말인데, 움직이면 시간계산을 해줘야하므로 움직이는것과 시간계산을 함께 넣어서 큐를 튜플배열로 사용하였다. 순간이동이라는 조건이 추가되서 1초가아닌 0초를 더해야하는것을 제외하고는 숨바꼭질과 문제가 똑같다. queue에서 튜플의 첫번째 요소는 현재 위치, 두번째 요소는 걸리는 시간이다. 후기 : BFS관련 복잡한 문제들을 몇번봐서 이렇게 간단한건 어느정도 풀만한 수준이 된거같다. let nk = readLine()!.split(separator: " ").map{Int(String($0))!} let n = nk[.. 2021. 11. 12.
[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.

티스토리툴바