Algorithm
-
[Programmers] 스티커 모으기(2)Algorithm/Programmers 2021. 10. 9. 13:21
출처: https://programmers.co.kr/learn/courses/30/lessons/12971 분류: dp 접근 배열의 길이도 100,000 으로 크고 이 스티커를 뗄지 안 뗄지, 앞에껄 땠는지 안 땠는지 등등의 경우를 고려해줘야 하니 DP로 문제로 접근을 했어요. 그냥 배열의 첫 번째를 기준으로 잡으면, 이 스티커를 땔 경우 DP vs 떼지 않을 경우 DP 두 번의 DP를 구해서 최대를 구하면 되는 문제였네요 처음에 저도 이렇게 접근은 했는데 첫 번째 인덱스부터 DP, 마지막 인덱스부터 거꾸로 DP 라는 엉뚱한 풀이로 해서.. 꽤나 삽질을 했습니다 😰 풀이 일단 각 케이스의 0, 1번 기저 사례를 구해주고 2번 인덱스부터 점화식으로 적용해주면 됩니다. (사실 n이 3일 때는 하나밖에 땔 ..
-
[BOJ] 2178 미로탐색Algorithm/BOJ 2021. 10. 9. 13:03
출처: https://www.acmicpc.net/problem/2178 분류: BFS 접근 시작점부터 목적지까지 최단 경로를 찾는 전형적인 BFS 문제였습니다. 풀이 방법은 다양하겠으나 저는 거리를 담아두는 distanceMap 이차원 배열을 하나 만들어서 풀었습니다. import Foundation let rc = readLine()!.split(separator: " ").map { Int($0)! } var map = [[Int]]() for _ in 0..= 0, nc >= 0, nr < rc[0], nc < rc[1], distanceMap[nr][nc] == 0, map[nr][nc] == 1 else { continue } distanceMap[nr][nc] = distanceMap[r][..