본문 바로가기

dfs32

[Swift][BruteForce] 백준 14391번 (종이 조각) 요구 능력 BruteForce + recursiveFunction(DFS) 문제설명 가로와 세로를 섞어서 찢는데 나올 수 있는 가장 큰 수를 구하는 문제이다. 시간복잡도 종이조각을 가로로 자르거나 세로로 자르는 2가지의 경우가 모든칸에 적용될 수 있으므로 O(2^n)의 시간복잡도를 갖는다. n과 m이 최대4까지 나오니까 2^16이 최악의경우이다. 그리고 가로 혹은 세로로 찢어지는 경우마다 우리는 완전탐색을 해서 한번씩 들여다봐야하기 때문에 O(n *m)의 시간복잡도가 걸린다. 종합적으로 O(2^n * m * n)의 시간복잡도가 걸리는것이다. DFS() 처음에는 이게 무슨뜻이지 싶었는데, 방문처리가 true로 처리됬을 경우에는 가로로 찢어진것을 의미하고, 방문처리가 false로 처리됬을 경우에는 세로로 찢.. 2022. 3. 22.
[Swift][프로그래머스][DFS] 네트워크 요구능력 : DFS 재귀 코드설명 : 네트워크가 따로따로(?)있는게 몇개인지 구하는 문제이다. 예를 들어서 1번과 2번이 연결되어 있고 3번은 따로있으면 네트워크는 2개이다. 만약 1번과 2번과 3번이 모두 연결되어있지 않으면 네트워크는 3개이다 1번과 2번과 3번이 모두 연결되어있으면 네트워크는 1개이다. 나는 우선 연결그래프를 만들어주었다. 이렇게 노드의 개수와 연결된 간선이 주어지는 경우에는 연결그래프를 만들어주고 문제를 푸는게 좋다. 만약 입출력 예의 1번같은 경우에는 graph에 다음과 같이 들어갈 것이다. graph = [[0,1], [0,1], [2]] 나는 노드를 0번부터 세어주었다. 그래서 0번노드는 0번과 1번이 연결되어있고, 1번노드도 0번과 1번이 연결되어있고, 2번노드는 2번 자신.. 2022. 3. 15.
[Swift][DFS] 백준 1248번 (맞춰봐) 요구능력 : DFS 재귀 코드설명 : 일단 문제를 이해해야하는데,, 예제입력 1에 적혀있는 -+0++++--+로 예를 들어 설명해보자. 규현이가 쓴 수가 A[]라는 배열에 4개가 저장되어 있다고 가정해보면 A[0]의 합, A[0] ~ A[1]의 합, A[0] ~ A[2]의 합, A[0] ~ A[3]의 합이 음수, 양수, 0으로 구분되어 저장되는 것이라고 보면된다. 예제 출력1처럼 -2 5 -3 1일 때 A[0]의 합, A[0] ~ A[1]의 합, A[0] ~ A[2]의 합, A[0] ~ A[3]의 합을 직접해보면 -+0+가 나오는걸 알 수 있다. 이후에도 A[1]의 합, A[1] ~ A[2]의 합, ... 이렇게 구해보면 문제에서 뭘 구해야하는지 이해가 갈것이다. 나는 처음에 result배열에 그냥 평범.. 2022. 3. 15.
[Swift][프로그래머스][DFS] 타겟 넘버 요구능력 : 깊이우선탐색 코드설명 : 일반적인 DFS문제로 노드를 그려가면서 풀면 이해가 쉽다. 후기 : 그냥 DFS로 풀면되는걸.. 계속 순열로 풀려고 하다가 시간이 조금 걸렸다.. 이걸 대체 왜 순열로 접근했을까.. func solution(_ numbers:[Int], _ target:Int) -> Int { var result = 0 func dfs(_ depth: Int, _ sum: Int){ if depth == numbers.count{ if target == sum { result += 1 } return } dfs(depth + 1, sum + numbers[depth]) dfs(depth + 1, sum - numbers[depth]) } dfs(0, 0) return result } 2022. 3. 14.

티스토리툴바