재귀함수2 [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][BruteForce] 백준 15658번 (연산자 끼워넣기 (2)) 요구능력 : 재귀함수 코드설명 : 내가 처음에 시간초과가 났던 코드는 문자열에 모든 연산자를 집어넣고 그 연산자를 백트래킹하면서 모든 경우의수를 다 세보는 코드다. 처음에는 연산자끼워넣기랑 똑같이 풀었다. 그러다 블로그를 서칭하던중에 내가 쓴 코드가 범위를 한참초과해서 시간초과가 난다는것을 알게되었다. 수의 개수는 최대 11개까지 들어온다. 그럼 연산자의 개수는 한번의 연산에 최대 10개를 쓸 수 있다. 그리고 연산자는 최대 4N개가 주어지니까 44개에서 10개를 뽑으면 44C10이 되고, 이걸 정렬하는 데는 연산자의 개수만큼 걸리니 44C10 * 10이 나온다. 그럼 시간초과가 나게된다. (다른분들은 다 11이라고 적으셧던데 저는 10이라고 생각해서 10으로 적었습니다. 틀렸다면 이유좀 댓글로 부탁드립.. 2021. 12. 27. 이전 1 다음
