본문 바로가기

Algorithm236

[Swift][BFS] 백준 12869번 (뮤탈리스크) 요구능력 : BFS 코드설명 : 문제풀이는 유튜브 큰돌의터전님께서 정말 잘 설명해놓으셨다. 이보다 잘설명하기는 어려울것 같아서 혹시나 어떤방식으로 풀리는지 모르겠는 사람은 유튜브를 들어가보시길.. SCV가 3대 있다고 가정하고, 뮤탈리스크는 1번 SCV를 먼저 칠 수도있고, 2번 SCV를 먼저 칠 수도있고, 3번 SCV를 먼저 칠 수도있다. 그렇다면 뮤탈리스크가 공격하는 경우의 수는 총 6가지가 나오게된다. let damage = [[1, 3, 9], [1, 9, 3], [3, 1, 9], [3, 9, 1], [9, 1, 3], [9, 3, 1]] 나는 N이 1~3까지 밖에 없길래 그냥 큐를 튜플 3개로 선언하고 arr이 3보다 작은경우에는 나머지칸에 0을 넣어줬다. if arr.count == 1 { .. 2022. 1. 17.
[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.

티스토리툴바