Swift
-
백준 17135 캐슬디펜스Algorithm/BOJ 2021. 3. 18. 14:14
출처: www.acmicpc.net/problem/17135 분류: 시뮬레이션 접근방식 구현도 구현인데 생각을 좀 잘못해서 몇 번의 시행착오를 겪었습니다. 문제를 잘 읽지 않으면 틀릴 수 있는 주의해야 할 점들이 몇 가지 있었던 문제 같습니다. 저는 문제를 보고 크게 3가지의 구현 단계로 나눠야겠다고 생각했습니다. 1. 궁수 3명 뽑기 2. 현 위치에서 제거 가능한 적 찾기 3. 궁수 전진 각 부분이 잘 구현되면 흐름에 따라 답을 찾는 건 어렵지 않게 할 수 있습니다. 저는 우선 주어진 맵 밑에 궁수가 배치될 행 (n행) 을 하나 추가했는데요, 여기에 궁수를 두고 나머지 적을 모두 밑으로 내리는 건 에너지 소모가 굉장히 큰 일이라서, 저는 여기서부터 출발해 궁수가 한 칸씩 위로 올라가면서 적을 죽이는 방..
-
백준 17142 연구소 3Algorithm/BOJ 2021. 3. 17. 16:09
출처: www.acmicpc.net/problem/17142 분류: 완전탐색, BFS, DFS 접근방식 조합과 BFS를 사용해 해결할 수는 문제였습니다. 바이러스가 활성화될 수 있는 지역과 최대 활성화시킬 수 있는 바이러스의 수가 주어졌을 때, 활성화 바이러스의 조합을 뽑아 BFS를 돌려 최단 거리를 계산합니다. 활성화 바이러스의 조합은 순서 상관없이 뽑는 경우의 수이기 때문에 순열이 아닌 조합으로 처리해줘야 합니다! var selected = [Point]() func selectVirus(curr: Int) { if selected.count == nm[1] { let time = infectTime(selected) if time != -1 { if minimumTime == -1 { minimum..
-
백준 10819 차이를 최대로Algorithm/BOJ 2021. 3. 16. 13:20
출처: www.acmicpc.net/problem/10819 분류: 완전탐색, 순열 접근방식 n이 최대 8밖에 되지 않아 가능한 배열 조합을 모두 구해서 주어진 식대로 계수의 최댓값을 계산했습니다. 주어진 예제에서는 [8, 15, 1, 20, 4, 10] 경우에 가장 큰 최댓값이 나오는데 어떤 경우에 최대가 나오는 특별한 규칙이 있는건지는 잘 모르겠습니다.. ㅠㅠ 순열을 오랜만에 해서 처음에는 배열을 만들어가고 해당 수를 넣었는지 체크하는 bool 배열을 만들고... 굉장히 비효율적으로 풀었었네요 ㅠㅠ 덕분에 오랜만에 순열을 다시 복습해볼 수 있어서 좋았네요 :) 전통적인 순열은 스왑을 통해 백트래킹 방식으로 구할 수 있습니다. 앞에서부터 해당 자리에 들어갈 수를 채워넣어가는 방식으로 바꿀 자리의 인덱스..
-
백준 16236 아기상어Algorithm/BOJ 2021. 3. 10. 18:08
출처: www.acmicpc.net/problem/16236 분류: BFS 접근방식 상어가 먹이를 찾을 수 없을 때가지 최단거리의 먹이를 찾아 bfs를 돌려주면 되는 문제였습니다. 기술적으로 크게 어려운 것은 없었으나... 익숙하지 않다면 구현에서 좀 애를 먹을 수 있을 것 같네요..! (후 힘들었습니다..) 같은 거리의 먹이들이 여러 개라면 요구사항대로 정렬을 해줘야 합니다! row 우선, 그다음 col로 ..! feeds.sorted(by: { $0.r == $1.r ? $0.c < $1.c : $0.r < $1.r}) 큐에서 DoubleStackQueue를 사용했는데 그냥 배열로 해서 removeFirst해도 통과가 가능한 것 같습니다. 해결방법 struct DoubleStackQueue { pri..
-
백준 12100 2408(easy)Algorithm/BOJ 2021. 3. 8. 15:03
출처: www.acmicpc.net/problem/12100 분류: 시뮬레이션 접근방식 바킹독님의 유튜브 강의를 참고했습니다. 최고 🥰 2048.. 하는 건 좋아했는데 막상 만들라고 하니 꽤 어려웠습니다. 하지만 항상 지나고 생각해보면 그리 어렵지 않습니다 💪 한 행만 잘 합칠 수 있다면 이걸 반복하고, 회전시켜서 간단하게 해결했습니다. 한 행 기울이기 먼저 한 행을 왼쪽으로 기울여서 합치는 걸 생각해보겠습니다. 저는 합쳐진 새로운 행을 만들어 나간다고 생각을 했는데요, 왼쪽으로 기울일거니까 합칠 배열의 인덱스를 0으로 두고 기존의 행을 돌면서 새로운 배열을 만들어 나갔습니다. 새로 만들어질 배열을 mixed, mixed의 현재 인덱스를 movingPoint 라고 해볼게요. mixed 를 기존 행의 크기..
-
백준 18808 스티커 붙이기Algorithm/BOJ 2021. 3. 7. 18:48
출처: www.acmicpc.net/problem/18808 분류: 시뮬레이션 접근방식 주어진 요구사항대로 잘 구현하면 되는 문제였습니다! 각 부분을 함수로 잘 쪼개면 어렵지 않게 해결할 수 있을 것 같네요 :) 저는 isPaste, paste, rotate 등을 함수로 분리해서 해결했습니다. rotate 하는 부분이 좀 헷갈렸는데, 기억해두면 나중에도 유용하게 사용할 수 있을 것 같아요! 90도 회전 func rotate(_ sticker: [[Int]]) -> [[Int]] { let rowSize = sticker.count let colSize = sticker[0].count var rotated = [[Int]](repeating: [Int](repeating: 0, count: rowSize..
-
백준 2143 두 배열의 합Algorithm/BOJ 2021. 3. 5. 13:44
출처: www.acmicpc.net/problem/2143 분류: 이분 탐색, 투 포인터 접근방식 합이 0인 네 정수 문제와 비슷했던 문제였습니다. 주어진 각 배열에서 나올 수 있는 부분합을 모두 구해준 뒤 정렬해서 투 포인터로 해결했습니다. 마찬가지로 T인 케이스를 찾았을 때 중복인 수의 개수를 세서 쌍을 찾아줘야 합니다 :) 해결방법 let t = Int(readLine()!)! let n = Int(readLine()!)! let a = readLine()!.split(separator: " ").map { Int(String($0))! } let m = Int(readLine()!)! let b = readLine()!.split(separator: " ").map { Int(String($0))..
-
백준 1939 중량제한Algorithm/BOJ 2021. 3. 4. 17:06
출처: www.acmicpc.net/problem/1939 분류: 이분 탐색 접근방식 하 이번 문제도 너무 어려웠습니다... 설명이 애매해서 이해도 어려웠고 메모리제한............ ㅂㄷㅂㄷ 먼저 문제의 마지막에 " 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오. " 라고 되어있어서 마지막에 주어진 두 섬으로 한 번에 가는 경우를 체크하는건가? 그럼 중간에 경로들은 왜 주어진거지? 문제가 좀 이상한데? 라고 생각했었습니다. 결국 여기서 말하는 한 번의 이동이란 처음 섬에서 특정 중량으로 출발시킨 짐이 목표 섬까지 도착하는 경로를 의미합니다. 중량을 기준으로 이분 탐색을 해서 각 중량으로 이동이 가능한지 체크해서 해결했습니다. var mostWeight = 0..