본문 바로가기

Algorithm123

[Swift][DFS] 백준 15656번 (N과M(7)) 요구능력 : DFS와 백트래킹에 대한 이해 코드설명 : N과M(3) 에서 바뀐점은 수열을 지정해 줬다는 점이다. 시간초과로 애먹었는데, 이번 문제를 통해서 map()함수가 시간을 은근히 잡아먹는다는 걸 깨달았다. 시간초과가 났던 코드를 첨부해본다. let nm = readLine()!.split(separator: " ").map{Int(String($0))!} let n = nm[0] let m = nm[1] var arr = readLine()!.split(separator: " ").map{Int(String($0))!} arr.sort() var depth = 0 var resultStr = "" var result: [String] = [] func dfs(_ depth: Int){ if dep.. 2021. 9. 30.
[Swift][DFS][백트래킹] 백준 15654번 (N과 M (5)) 요구능력 : DFS와 백트래킹에 대한 이해 코드설명 : N과M(1) 에서 1부터 n까지 썻던 배열을 이 문제에서는 입력받아서 쓰는 차이가 있다. 바뀐건 아래 코드에 주석처리한 부분과 입력받는부분이 하나 더 추가된점 외에는 없다. 후기 : N과M문제는 N과M(1)만 잘 이해하고 있으면 연쇄적으로 잘풀려서 기분은 좋은거같다. let input = readLine()!.split(separator: " ").map{Int(String($0))!} let n = input[0] let m = input[1] var arr = readLine()!.split(separator: " ").map{Int(String($0))!} var visited: [Bool] = Array(repeating: false, cou.. 2021. 9. 29.
[Swift][DFS] 백준 15651번 (N과 M (3)) 요구능력 : DFS와 백트래킹에 대한 이해 코드설명 : N과 M(1) 에서 "같은 수를 여러번 골라도 된다." 라는 조건이 더해졌다. 기존의 N과M에서 방문여부를 따지지 않으면 된다. n = 4, m = 4 인 경우를 생각해보자. 1 1 1 1 1 1 1 2 1 1 1 3 . . 간단하게 스택을 생각하면 된다. [1, 1, 1, 1]일 때, 모든 dfs의 i = 1일 때 이다. 이걸 str에 추가하고 나서 return하면 result = [1, 1, 1]이 되고, i = 2가 실행된다. 그럼 result = [1, 1, 1, 2]가 되고, str에 추가된다. 이런식으로 맨 나중에 들어온걸 빼고 그 다음수를 넣는 식으로 스택이 진행된다. 후기 : N과M(1) 문제에 간단한 조건1개만 추가한 문제 N과 M의.. 2021. 9. 27.
[Swift][DFS] 백준 11724번 (연결 요소의 개수) 요구능력 : DFS와 인접리스트에 대한 이해 코드설명 : 평범한 DFS문제처럼 인접리스트를 구해준다. 문제에서 따로 함수를 빠져나갈 조건이 나오지 않았으므로 사실 depth도 필요는 없다. 그냥적은거다. 조건이 없으니 방문처리만하고 나가는 처리는 할필요가 없다. 여기서 핵심은 인접리스트를 다 돌면서 이미 방문한 노드들은 돌지않고 돌게되는 인접리스트는 카운트를 해주는 것이다. 이미 방문한 노드들은 한개의 묶음의 노드이기 때문이다. (하나의 연결요소이기 때문이다.) DFS는 같은 묶음에 있는 노드는 다 돌게 되어있다. 그러니 방문하지 않은 노드는 다른 연결요소라는 뜻이다. 후기 : DFS문제는 아직 어렵다 .. 적응이 좀 더 필요하다.. let arr = readLine()!.split(separator: .. 2021. 9. 26.

티스토리툴바