프로그래머스33 [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] 타겟 넘버 요구능력 : 깊이우선탐색 코드설명 : 일반적인 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. [Swift][백트래킹][LV_3] 양과 늑대 요구능력 : 2진트리, 백트래킹 코드설명 : 처음에 배열로 edges를 연결리스트식으로 만들어서 방문했던곳을 다시 들리는(위로다시올라오는) 대참사가 발생했다. dictionary로 아래와 같이 넣으면 한방향(본인 위치의 아래방향)으로 방문하기 편하므로 dictionary를 사용했다. 백트래킹이라고 생각한이유는 모든경우를 다 세어봐야 하기 때문이다. dfs(현재노드, 다음에 방문할 수 있는 노드, 양의 카운트, 늑대의 카운트)로 구성했다. 이렇게 구성한 이유는 양과 늑대의 카운트같은 경우 dfs()함수가 리턴되면 따로 -처리를 해주지 않아도 되기 때문이고(전역으로 선언 시 따로 -처리를 해줘야함), 현재노드 같은 경우에는 시작노드로 0을 전달해줘야 하는것도있고 굳이 0을 전달 안해주고 0으로 시작하더라도 .. 2022. 2. 26. [Swift][소수][LV_2] K진수에서 소수개수 구하기 요구능력 : 소수판별 코드설명 : 처음에 에라토스테네스의 체를 100만으로 설정하고 풀었는데, 두 개의 테스트케이스에서 coreDumped가 나왔다. 인덱스 문제인것같아서 n = 1000000으로 설정하고 k = 6으로 설정해봤는데, 에라토스테네스의 체에 들어간 수가 100만 보다 큰 수가 나와버려서 coreDumped된것이었다. 그래서 4천만으로 설정하고 해봤는데 당연히 시간초과 ^^ 에라토스테네스가 더 빠른건줄알고 100만으로 두고 그보다 큰수가 나오면 아래에 isPrime함수를 사용했는데, 이렇게 사용한 시간보다 isPrime만 사용한 시간이 더 짧았다. 사실 이 문제에서 소수를 판별해봤자 몇개나 판별하겠나.. 이 문제를 통해서 에라토스테네스의 체를 소수구한다고 아무때나 사용하는게 아니라는것을 알았.. 2022. 2. 25. 이전 1 ··· 3 4 5 6 7 8 9 다음