N과M4 [Swift][DFS][LV_1][프로그래머스] 소수 만들기 요구능력 : 백트래킹에 대한 이해 코드설명 : 풀이는 살펴보니 여러가지 각양각색이다. 나는 N개의 배열에서 3개를 뽑아내서 백트래킹으로 문제를 풀어냈다. 백준의 N과M을 이해하고온다면 문제를 쉽게 풀 수 있다. 1. 3개를 뽑아내기위한 부분 for i in start.. 2021. 11. 6. [Swift][BruteForce] 백준 6603번 (로또) 요구능력 : N과M에 대한 이해 코드설명 : 문제를 보면 N과M시리즈와 매우 유사하다. 1. N개의 수 중에서 6개를 뽑는다. 2. 비내림차순 1. 문제의 조건을 맞춰주는 부분 문제에서는 0이 입력되기전까지 계속해서 받으라고 했으므로 while문으로 처리를 해준다. 그리고 배열에서 맨 앞의수는 필요없으니 버려준다.(어차피 N개의 수에서 6개만 뽑아서 오름차순해줄것이기 때문이다.) while true{ input = readLine()!.split(separator: " ").map{Int(String($0))!} if input[0] == 0 { break }else { input.removeFirst() dfs(0, 0) print("") } } 2. 백트래킹을 이용해서 N개의 수중 6개를 뽑아준다. .. 2021. 11. 2. [Swift][DFS] 백준 1759번 (암호만들기) 요구능력 : DFS와 백트래킹에 대한 이해 코드설명 : N과M(8) 문제로 선행학습을 하고 풀면 정말 효율적일거같다. 안푸셨다면 풀고오시길... N과M(8)에서 바뀐부분 1. 숫자가 아닌 알파벳이라는 점 2. for문을 이용하여 자음이 2개이상, 모음이 1개이상인지 판별 후기 : 우연찮게 이 문제를 접하게됬는데 N과M(8)과 거의 유사한문제다.. 자음 2개이상과 모음1개이상이 들어갔는지만 판별하면 되는 문제였다.. 골드문제를 처음으로 15분도안걸려서 풀었다. 시간초과가 날거같았는데, 2초인거보고 안심... let LC = readLine()!.split(separator: " ").map{Int(String($0))!} let L = LC[0] let C = LC[1] let arr = readLine(.. 2021. 10. 1. [Swift][DFS][백트래킹] 백준 15649번 (N과 M (1)) 요구능력 : DFS의 응용 코드설명 : DFS를 활용하는 백트래킹 문제이다. 백트래킹이란? 탐색하는데 필요한 많은 자원을 줄이기 위해 유망성있는 노드들을 중심으로 탐색하는 방법이다. 조건을 줘서 필요없는(유망성없는) 노드에는 방문조차 하지않는다. 백트래킹이라는 방법을 사용하기위해 DFS를 이용한다고 생각하면 된다. 이 문제에서 핵심 두 가지다. 1. 수열을 만들되, 백트래킹을 이용하여 중복되는 수(유망성없는 수)를 방문하지 않는다는것이다. 2. DFS를 사용하기 때문에 Stack을 활용한다는 것이다. 문제예시) 4 4를 입력했다고 치자. 아래 코드를 실행하게 되면, result(0) depth = 0, visitied[1] = false -> visited[1] = true, stack = [1] res.. 2021. 9. 23. 이전 1 다음