반응형 Problem Solving242 백준 2252번 줄 세우기 - C++(cpp) 풀이 1. 각 학생을 그래프의 정점으로 생각한다. 2. A가 B의 앞에 서야 한다면, A에서 B로 가는 방향 간선을 추가한다. 3. 위상 정렬한 결과를 출력한다. 1. 각 학생을 그래프의 정점으로 생각한다. 각 학생을 그래프의 노드로 생각할 것이다. X번 학생은 X번 노드로. 2. A가 B의 앞에 서야 한다면, A에서 B로 가는 방향 간선을 추가한다. A가 B의 앞에 서야 한다면, A가 있은 뒤에 B가 와야 한다. 이것을 그래프에 표현하기 위해 A → B인 방향 간선을 추가한다. 3. 위상 정렬한 결과를 출력한다. 이제 완성된 그래프를 위상 정렬한 결과를 출력하면 된다. 주어진 상황이 위상 정렬 상황이기 때문. #include #include #include #include using namespace std.. 2022. 1. 28. 백준 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. 이전 1 ··· 36 37 38 39 40 41 42 ··· 49 다음 반응형
