반응형 Problem Solving/BOJ228 백준 1516번 게임 개발 - C++(cpp) 풀이 1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물을 짓는 데 걸리는 시간을 구한다. 1. 각 건물을 정점으로, 건설 순서를 방향 간선으로 나타낸다. 이렇게 선행 관계가 정해져있는 작업들을 순서대로 수행하는 상황은 그래프 위상 정렬 알고리즘으로 해결할 수 있다. 먼저 주어진 상황을 그래프로 나타낸다. 2. 그래프에 대해 위상 정렬을 한다. 위상 정렬을 해준다. 아래 코드에서는 큐를 사용하였고, 선행 작업들이 모두 완료된 작업들만 큐에 들어가게 된다. 3. 위상 정렬 과정에서 totalCost[i] = max(totalCost[prev]) + i번 건물.. 2022. 1. 28. 백준 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. 이전 1 ··· 33 34 35 36 37 38 39 ··· 46 다음 반응형
