백트래킹15 [Swift][BruteForce] 백준 16198번 (에너지 모으기) 요구능력 : 백트래킹 코드설명 : 문제에서의 핵심 1. 구슬 하나를 고른다.(단, 첫번째구슬과 마지막구슬을 고르면 안됨) 2. x번째 에너지구슬 제거(고른 구슬을 제거해야한다.) 3. Wx-1 * Wx+1 의 에너지모음( Wx-1 * Wx+1의 모든경우를 합해야한다.) 4. N을 1감소시킴. 구슬 1~N까지 다시 번호매김. 예제 4 1 2 3 4 가있다. 2를 고르면 Wx-1 * Wx+1이 1 *3이 된다. 그리고 첫번째와 마지막은 못고르니까 3을 고른다. 3을 고르면 Wx-1 * Wx+1이 1 * 4가 된다. 그럼 에너지는 총 8이 모인다. 맨 처음에 3을 고른다. 그럼 Wx-1 * Wx+1이 2*4가 된다. 그 다음 2를 고르면 Wx-1 * Wx+1이 1 * 4가 되서 12가 나온다. 이렇게 어느 구.. 2022. 1. 14. [Swift][BruteForce] 백준 16197번 (두 동전) 요구능력 : 백트래킹 코드설명 : 문제를 보면 동전이 한 칸씩 왔다갔다 해야된다. 그래서 백트래킹을 생각했고 백트래킹을 하기위해서는 동전의 위치좌표가 필요했다. 이 문제에서의 핵심 1. 두 동전의 위치 2. 위, 아래, 좌, 우 백트래킹 3. 동전은 하나만 떨어뜨려야된다. 4. 동전 떨어뜨릴 수 없거나 버튼을 10번보다 많이눌러야되면 -1출력.(개인적으로 이게제일 어려웠다.) 1. 두 동전의 위치 입력으로 o가 들어올때마다 coinLocation변수에 2차원 배열로 저장했다. 2. 위, 아래, 좌, 우 백트래킹 처음에는 하나씩하려다가 어차피 두 동전이 동시에 이동하니까 굳이 하나씩할 필요도없고 해봤자 안될거같아서 동시에 이동했다. 나는 떨어뜨리는걸 알기위해서 동전이 떨어지는 모서리지점에 x로 도배를 해놨.. 2022. 1. 13. [Swift][Bruteforce] 백준 14225 (부분수열의 합) 요구능력 : 백트래킹 코드설명 : 이 문제는 이 전에 풀었던 부분수열의합(1182번)과 비슷한 느낌의 문제이다. 수열의 경우의수를 백트래킹으로 구하는 부분까지는 같다. 이 문제에서의 핵심 1. 백트래킹 2. 시간초과 안나고 없는수를 어떻게 찾을것이냐.. 처음에는 배열함수써서 인덱스찾고 찾은 인덱스로 지우고.. 뭐 별짓을 다하다가 시간초과가 계속났었다. 시간복잡도에 대해 공부좀해야겠다... 내가 해결한방법은 백트래킹으로 부분수열의 합을 구한다음에 나온 합에대한 부분을 true처리해서 for문을 나올 수 있는 최대합의 경우의수까지 돌리면서 false가 맨 처음 나오면 그게 가장 작은수!라고 풀이를 한것이다. 후기 : 어렵지는 않은 문제인데 결과값범위를 잘못잡아서 헤맸다.. let n = Int(String(.. 2022. 1. 12. [Swift][BruteForce] 백준 15658번 (연산자 끼워넣기 (2)) 요구능력 : 재귀함수 코드설명 : 내가 처음에 시간초과가 났던 코드는 문자열에 모든 연산자를 집어넣고 그 연산자를 백트래킹하면서 모든 경우의수를 다 세보는 코드다. 처음에는 연산자끼워넣기랑 똑같이 풀었다. 그러다 블로그를 서칭하던중에 내가 쓴 코드가 범위를 한참초과해서 시간초과가 난다는것을 알게되었다. 수의 개수는 최대 11개까지 들어온다. 그럼 연산자의 개수는 한번의 연산에 최대 10개를 쓸 수 있다. 그리고 연산자는 최대 4N개가 주어지니까 44개에서 10개를 뽑으면 44C10이 되고, 이걸 정렬하는 데는 연산자의 개수만큼 걸리니 44C10 * 10이 나온다. 그럼 시간초과가 나게된다. (다른분들은 다 11이라고 적으셧던데 저는 10이라고 생각해서 10으로 적었습니다. 틀렸다면 이유좀 댓글로 부탁드립.. 2021. 12. 27. 이전 1 2 3 4 다음
