반응형 전체 글282 백준 1005번 ACM Craft - 스위프트(Swift) 시간초과 해결 못함 단순한 위상 정렬 문제였는데 TLEㅠㅠ 입력이 느려서 그런 것 같다. 검색해보니 이 문제를 swift로 푼 사람들 중에 readLine() 대신 FileIO를 사용해서 AC를 받았다는 글이 몇 개 있었다. 결국 또 C++로 다시 제출했다. 아래는 각각 시간초과 받은 Swift코드와 같은 로직인데 AC 받은 C++ 코드. import Foundation var N = 0, K = 0 var indegree = [Int]() var buildCost = [Int]() var totalCost = [Int]() var edges = [[Int]]() struct Queue { var queue = [Int]() var front = 0 var isEmpty: Bool { return front >= queue.. 2022. 1. 27. 백준 2239번 스도쿠 - 스위프트(Swift) 풀이 1. 차례로 빈칸을 찾아 1-9중에 가능한 숫자를 전부 넣어본다. 2. 마지막 빈칸까지 다 채우면 전체 탐색을 종료한다. 1. 차례로 빈칸을 찾아 1-9중에 가능한 숫자를 전부 넣어본다. 결국 모든 빈칸을 다 채워야 하므로, 빈칸을 채울 순서를 정한 뒤 차례로 빈칸을 채워보면 되는 백트래킹 문제이다. 빈칸에 들어갈 수 있는 숫자 1-9 중에, 채울 수 있는 숫자들로만 채워본다. (만약 같은 행 또는 열 또는 블록에 같은 숫자가 있으면 채울 수 없다.) 만약 해가 여러 개라면 사전식으로 앞서는 것을 출력해야 하므로, 작은 수인 1부터 9까지 차례로 넣어준다. 해당 빈칸을 채웠으면, 다음 차례 칸을 채우는 함수를 또 재귀적으로 호출한다. 아래 코드에서는 각 칸에 row*9+col로 번호를 매겨 순서를 정했다.. 2022. 1. 27. 백준 11049번 행렬 곱셈 순서 - 스위프트(Swift) 풀이 1. 두 부분으로 잘라 앞쪽 행렬끼리 곱하고, 뒤쪽 행렬끼리 곱한 뒤, (앞쪽 행렬들을 모두 곱한 결과 행렬)과 (뒤쪽 행렬들을 모두 곱한 결과 행렬)을 곱하는 방식을 사용한다. 2. dp(lo, hi) = lo부터 hi번째 행렬을 전부 곱하는 데 필요한 연산 횟수의 최솟값이라고 하면 3. dp(lo, hi) = i=lo~hi-1일 때 min( dp(lo, i) + dp(i+1, hi) + matrix[lo].row * matrix[i].col * matrix[hi].col ) 1. 두 부분으로 잘라 앞쪽 행렬끼리 곱하고, 뒤쪽 행렬끼리 곱한 뒤, (앞쪽 행렬들을 모두 곱한 결과 행렬)과 (뒤쪽 행렬들을 모두 곱한 결과 행렬)을 곱하는 방식을 사용한다. 브루트포스로는 시간 내에 통과가 불가능하다. DP를.. 2022. 1. 27. 백준 2638번 치즈 - 스위프트(Swift) 풀이 + 그림 설명 1. 가장자리 아무 칸에서나 시작해 DFS/BFS로 인접한 모든 칸들을 외부 공기 처리한다. 2. 치즈들을 모두 순회하면서 녹을지 말지를 결정한다. 3. 치즈가 남지 않을 때까지 1-2를 반복한다. 1. 가장자리 아무칸에서나 시작해 DFS/BFS로 인접한 모든 칸들을 외부 공기 처리한다. 가장자리에는 치즈가 오지 않으므로 항상 외부 공기가 있는 칸이다. 치즈로 둘러싸여 있는 내부 공기 칸과 구분하기 위해 매시간마다 가장자리에서 시작하는 BFS/DFS를 돌면서 인접한 칸들을 모두 외부 공기 칸으로 처리해준다. 좌측과 같은 초기 상황이라고 하면, 먼저 우측 그림처럼 외부 공기 처리를 해준다. 내부 공기와는 다르게 처리되고 있는 것에 유의한다. 2. 치즈들을 모두 순회하면서 녹을지 말지를 결정한다. 매 시간마.. 2022. 1. 26. 백준 14938번 서강그라운드 - 스위프트(Swift) 풀이 1. 모든 정점에 대해 각 정점에서 모든 정점으로 가는 거리를 플로이드 와샬 알고리즘을 사용하여 구한다. 2. 모든 정점에 대해 해당 정점과의 거리가 m이하인 정점들을 탐색하여 해당 정점에 낙하했을 때 얻을 수 있는 아이템 수를 구한다. 3. 2번에서 구한 값 중 최댓값을 출력한다. 1. 모든 정점에 대해각 정점에서 모든 정점으로 가는 거리를 플로이드 와샬 알고리즘을 사용하여 구한다. 각 정점에 낙하하는 모든 경우를 고려한 뒤 최적해를 골라야 한다. 또한, 어떤 정점에 낙하했을 때 얻을 수 있는 아이템 수를 알려면, 해당 정점에서 나머지 정점으로의 거리를 전부 알아야 한다. 따라서 모든 정점에 대해 나머지 정점으로의 거리를 구하는 플로이드 와샬 알고리즘을 사용한다. N=100이므로 O(N^3)도 제한시간.. 2022. 1. 26. 이전 1 ··· 41 42 43 44 45 46 47 ··· 57 다음 반응형
