재원블로그 재원블로그

이 문제는 그리디를 이용해서 푸는 문제이다. 일단 완전 탐색을 이용하는 것은 입력이 10만이므로 불가능하다. 따라서 그리디를 사용해야 하는데, 여기서 중요한 것은 끝나는 시간에 대해 오름차순으로 정렬하고, 끝나는 시간이 같을 때 시작 시간에 대해 오름차순 정렬해야 한다는 것이다. 결국 얼마나 많이 회의실을 배정할 수 있냐이므로, 끝나는 시간이 일찍 끝날 수록 많은 배정이 가능하기 때문이다. #include #include #include #include using namespace std; bool compare(pair &a, pair &b) { if (a.second == b.second) { return a.first < b.first; } return a.second < b.second; } in..

이 문제는 다익스트라 알고리즘을 사용하는 문제이다. 한 지점에서 한 지점의 최단 거리를 구하기 때문에 다익스트라를 사용하면 쉽게 풀 수 있다. 주의할 점은 C++에서 우선순위 큐의 디폴트로 최대 힙이므로 cost를 -를 붙여서 넣어줘야 하고, pair 를 우선순위 큐 내부에 사용할 경우 first부터 우선순위가 부여되므로 cost, next 순으로 넣어줘야 한다. #include #include #include #include using namespace std; #define INF 100000000 vector edges[50001]; int dist[50001]; int dijkstra(int start, int end) { priority_queue pq; dist[start] = 0; pq.pu..

이 문제는 dp를 이용한 문제이다. 처음에는 이 문제를 1원부터 10000원까지 루프를 돌리면서 동전을 루프를 돌려 계산하였는데, 이렇게 하면 순서가 뒤바뀐 경우의 수가 모두 포함되게 된다. 순서가 뒤바뀐 경우를 없애려면 코인에 대해서 루프를 돌리고, 그 안에서 금액에 대한 dp 테이블을 갱신해야 한다. 주의해야 할 점은 0원을 만드는 경우의 수가 1이라는 것이다. 애초에 이 값을 0으로 해놓으면 값이 제대로 나오지 않는다. #include #include #include using namespace std; #define MAX 10000 int dp[MAX + 1]; int main() { int n, k; vector coin; cin >> n >> k; for (int i = 0; i < n; i..

이 문제는 dp를 이용해서 푸는 문제이다. dp 배열을 해당 금액을 만들 수 있는 최소의 코인 개수로 설정하면 쉽게 풀 수 있는 문제이다. 시간 제한이 1초이므로, 1억번의 연산만으로 끝내야 한다. for 문마다 최대 100번의 루프가 돌아야 하므로, 탐색할 수 있는 금액의 최대 한도는 1,000,000원이다. 따라서 MAX를 백만으로 설정해서 문제를 풀었다. #include #include using namespace std; #define MAX 1000000 int dp[MAX + 1]; void init() { for (int i = 0; i > n >> k; i..

이 문제는 시뮬레이션과 BFS를 이용한 문제이다. 이 문제는 그렇게 어렵지 않은 문제였으나 두가지 주의해야할 점이 있었다. 첫번째는 solve() 안에서 녹을 얼음을 고르는 로직에서 한번에 A 배열에 결과를 반영하면 다음 반복문에서 그 영향을 받아 연쇄적으로 값이 줄어든다. 그러므로 녹을 얼음을 체크만 해놓고 모든 체크가 끝나면 한꺼번에 1을 감소시켜야 한다. 두번째는 저렇게 로직을 짜도 시간 초과가 떴는데, 이는 로직의 문제가 아니라 cmath 내장 함수 pow를 쓰면 시간 초과가 난다. 직접 만들어서 쓰면 시간 초과가 안 뜬다. 애초에 배열의 크기도 매우 작고, 시간 복잡도를 계산해봐도 절대 1초를 넘기지 않는다. 수학 내장 함수는 조심해서 써야할 것 같다. #include #include #incl..

이 문제는 시뮬레이션 문제이고, 최댓값을 구하는 문제이다. 최댓값을 구할 때 브루트 포스로 가능한가 싶었지만, 말이 4개이고 10번의 주사위 결과만 있으므로 아무리 크게 잡아도 4^10 = 1,048,576 이므로 가능하다. 나는 게임판을 보고 그래프와 비슷한 형태라고 떠올렸고, node 구조체를 만들어 게임판의 한 칸을 정의했다. solution 함수 부분은 브루트 포스, 백트래킹으로 모든 경우의 수를 구하는 것인데, 이 때 주의할 점은 말이 현재 칸에서 다음 칸으로 이동하면 현재 칸의 visited는 false로 해주고, 다음 칸의 visited 는 true로 해줘야한다는 것이다. 처음에는 next에 대한 visited만을 신경썼는데, 그런식으로는 정답이 안 나온다. 또한 주의할 점은 재귀 호출이 끝..

이 문제는 bfs로 푸는 문제이다. 처음에 이 문제를 풀때 순간 플로이드 워셜이 떠올라서 그렇게 풀어봤는데 애초에 값이 제대로 안 나왔다. 그래서 bfs로 다시 방향을 고치고 풀었는데, 이번에는 시간 초과가 났다. 처음에 bfs를 짤때는 start와 end를 두어 모든 짝에 대한 USADO를 저장했는데, 이런 식으로는 5000 * 5000 * 5000의 연산이 필요하게 되어 시간 초과가 난다. 다시 생각해보니 그럴 필요가 전혀 없었고, 시작점에서 출발하여 정점들을 방문하면서 USADO를 측정하고, 그 값이 k보다 크거나 같으면 카운트하면 되는 문제였다. 문제를 풀 때 알고리즘을 안 보고 푸는 연습을 꼭 해야할 것 같다. 실제 코딩 테스트 시에는 이 문제가 어떤 알고리즘의 문제인지 알려주지 않기 때문이다...

이 문제는 구현, 시뮬레이션 문제이다. 구현이 매우 복잡하지만 순서에 따라 함수를 나누고, 세부 내용을 구현하는 방식으로 코딩하면 어렵지 않게 풀 수 있다. 한가지 유의할 점은 파란 칸이나 보드를 벗어날 때 stack 에서 뺐던 말들을 다시 제자리에 집어넣는 로직이 들어가야 한다는 것이다. 구현하면서 한가지 아쉬웠던 것은 moveHorse 함수 안에서 switch 문을 통해 말을 이동시키는 부분의 코드가 너무 길어 수정할 때 어려움을 겪었다는 것이다. 이렇게 길어지거나 복잡한 코드는 함수를 더 나눠서 해야 한다는 생각이 들었다. #include #include #include #include #include using namespace std; #define WHITE 0 #define RED 1 #de..