algorithm
-
백준 1916 최소비용 구하기Algorithm/BOJ 2021. 4. 6. 22:11
출처: www.acmicpc.net/problem/1916 분류: 다익스트라 접근방식 전형적인 최단경로 문제였습니다. 다익스트라 알고리즘으로 해결할 수 있었습니다. 다익스트라 알고리즘을 알면 별도의 설명은 필요 없을듯 하네요. 다익스트라 포스팅을 한 번 해야겠습니다.. 해결방법 let n = Int(readLine()!)! var cities = [[(end: Int, value: Int)]](repeating: [], count: n+1) for _ in 0..
-
백준 17298 오큰수Algorithm/BOJ 2021. 4. 6. 18:20
출처: www.acmicpc.net/problem/17298 분류: 스택 접근방식 스택을 이용해서 풀 수 있었는데, 처음에 접근을 떠올리지 못해서 다른 분들의 풀이를 참고해서 겨우 풀었습니다. 아직 오큰수를 찾지 못한 수들을 스택에 담아줍니다. 현재 a[i]가 스택의 top 보다 크다면 top의 오큰수는 a[i]가 됩니다. 스택의 있는 수들은 아직 오큰수를 찾지 못한 수들이기 때문에 오른쪽에 있으면서 가장 큰 수가 바로 a[i] 입니다. 따라서 스택에는 오큰수를 찾지 못한 인덱스를 넣어주면서 a[i] 보다 크다면 빼서 해당 인덱스의 오큰수를 a[i]로 기록해주고, 다음으로 a[i]의 오큰수를 또 찾아야 하기 때문에 stack에 a[i]의 인덱스 i 를 넣어주고 넘어가줍니다. for i in 0..
-
백준 1450 냅색문제Algorithm/BOJ 2021. 4. 6. 14:48
출처: www.acmicpc.net/problem/1450 분류: 이분탐색 접근방식 n이 30으로 크기 때문에 그대로 부분합을 구하면 2^30 시간제한을 통과하기 어렵습니다. 따라서 반반 나눈 뒤 이분탐색으로 접근하는 방법으로 접근합니다. 부분합은 재귀적으로 구해줬습니다. func partition(_ idx: Int, _ to: Int, _ array: inout [Int], _ sum: Int) { guard sum Int { var low = 0 var high = sumB.count while low < high { let mid = (low + high)/2 if target < sumB[mid] { high = mid } else { low = mid+1 } } return low } 참고로 ..
-
백준 17825 주사위 윷놀이Algorithm/BOJ 2021. 4. 4. 18:53
출처: www.acmicpc.net/problem/17825 분류: 완전탐색 접근방식 꽤나 시간이 오래 걸렸던 문제네요.. 저는 5개의 루트로 나눠서 생각을 해봤는데요, 이동하고 나서 해당 칸이 다른 루트로 가야 한다면 루트를 바꿔주는 방식으로 풀었습니다. 이런 식으로 루트를 생각하면 다음과 같이 초기화 해줄 수 있습니다. var root = [[Int]](repeating: [Int](), count: 5) root[0] = (0...19).map { $0 * 2 } root[1] = [0, 13, 16, 19] root[2] = [0, 22, 24] root[3] = [0, 28, 27, 26] root[4] = [25, 30, 35, 40, 0] 1, 2, 3 같은 경우 특정 칸에서 멈출 때만 이동..
-
백준 17779 게리맨더링 2Algorithm/BOJ 2021. 4. 4. 15:59
출처: www.acmicpc.net/problem/17779 분류: 완전탐색 접근방식 주어진 요구사항 대로 구역을 나눠서 찾으면 되는 완전탐색 문제였습니다. 5번 구역의 범위를 계산하는 부분에서 애를 많이 먹었습니다... 😭 각 구역을 구분하는 부분만 다시 보면 될 것 같은데 간단하게 살펴보겠습니다. 우선 5구역을 시작하는 점을 (pr, pc) 라고 하면, 1구역의 r, c를 검사할 때, c p.c), pr - (c - pc) 보다 크거나 같은지로 계산해줄 수 있습니다. if c p.c && r >= p.r - (c-p.c)) { population[0] += map[r][c] } 같은 방식으로 2구역을 생각해보면, 큰 범위는 c > pc + d1 && r p.c+d1, r = p.c && r = p.c..
-
백준 2632 피자판매Algorithm/BOJ 2021. 4. 2. 13:14
출처: www.acmicpc.net/problem/2632 분류: 이분탐색 접근방식 이분탐색을 통해 해결해볼 수 있었습니다. 전체적인 풀이 과정은 다음과 같습니다. 1. 각 피자에서 가능한 피자 조각을 모두 구한다. (n == 1000 이므로 n^2 이면 충분합니다.) 2. 한쪽 피자에서 선택했을 경우 또는 하지 않을 경우 다른 쪽 피자의 값이 무엇이 되어야 할지 기대할 수 있기 때문에 이를 이분탐색으로 파악합니다. 가능한 피자 조각을 구할 때 주의해야 할 점은 피자 조각이 원형이라는 점입니다. 주어진 예제처럼 2 2 1 7 2 에서 피자 조각 경우를 구할 때, 원형으로 생각을 해줘야 합니다. 2 2 1 7 2 - 여기서 1부터 시작한다면 가능한 조합은 [1], [1, 7], [1, 7, 2], [1, ..
-
백준 1981 배열에서 이동Algorithm/BOJ 2021. 4. 1. 21:05
출처: www.acmicpc.net/problem/1981 분류: 이분탐색 접근방식 이 문제는 n이 최대 100으로 100 x 100 배열이기 때문에 단순 무식하게 BFS 접근하면 시간초과를 맞게 됩니다. 어떻게 하면 방문을 범위를 제한할 수 있을까요? 이 문제에서도 이분탐색의 아이디어를 적용해볼 수 있습니다. 우선 차이가 가장 작아지는 경우는 언제일까요? 경로의 최대최소가 같은 경우면 차이가 최소가 될 수 있겠죠? 때문에 최소는 언제나 가능성이 있으니 0으로 둡니다. 그럼 차이가 최대가 될 때는 언제일까요? 배열에 나오는 최대값과 최소값이 모두 들어있을 때, 즉 최대 - 최소가 차이의 최대가 되겠네요. 저희는 최소를 구해야 하기 때문에 만약 0 ~ 8 까지 가능성이 있을 때, 차이를 4로해서 가는 경우..
-
백준 3020 개똥벌레Algorithm/BOJ 2021. 3. 31. 11:36
출처: www.acmicpc.net/problem/3020 분류: 이분탐색 접근방식 이 문제는 가로 20 세로 50만이므로 모두 탐색한다거나 h만큼 일일이 배열에 담아준다거나 하는 방식으로는 시간초과를 면하기 어렵습니다. 저희가 원하는 건 특정 높이에서 만나는 장애물의 개수 입니다. 순서는 상관이 없죠! 따라서 이분탐색을 떠올려볼 수 있습니다. 대신 종유석과 석순이 서로 반대방향으로 나있기 때문에 이분탐색 upper/lower 바운드를 잘 섞어서 사용해줘야 하겠습니다. 이분탐색 upper/lower bounds가 익숙하지 않으시다면 여기를 읽어주세요 :] 조금 더 구체적으로 알아볼게요. 석순과 종류석의 높이를 따로 배열에 담고 정렬해줍니다. 저는 석순이 난 방향부터 높이를 1로 생각해서 계산해보려고 합니..