Do blog

문제 https://www.acmicpc.net/problem/9663 Note 백트래킹 모든 경우를 탐색하되 조건을 만족하는 경우를 제외하는 가지치기를 잘 수행해야 한다. 백트래킹이라는 개념을 오해하고 있었는데, 아래 잘 정리된 게시글을 보고 제대로 이해할 수 있었다. 나쁜 습관 문제를 빨리 풀려고 성급하게 접근하다 보니 잘못 푸는 경우가 잦다. 이 문제도 시간초과를 받았는데, 굉장히 비효율적인 방식으로 완전 탐색을 수행했었다. 시간 복잡도 계산 일반적인 구현은 O(N!)의 시간복잡도를 갖는 것 같다. (확인 및 검증 필요) Reference https://medium.com/@jeongdowon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-backtracking-%EC%9D%B4..

1. 문제 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. www.acmicpc.net 2. Note 구조체에 가입 순서를 포함하여 정렬해도 되지만, 안정 정렬(Stable sort)을 가능하게 하는 정렬 알고리즘을 사용하는 것이 좋다. 3. Reference https://en.cppreference.com/w/cpp/algorithm/stable_sort std::stable_sort - cppreference.com template< class RandomIt..

1. 문제 https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는 www.acmicpc.net 2. Note gi가 주어졌을 때 가능한 gi에 가깝도록 게이트를 배정해야하고, 이를 위해 가까운 게이트를 탐색해야 한다는 것..

1. 문제 https://www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 같은 자연수이다. www.acmicpc.net 2. Note 우선순위 큐에서 가장 작은 합성수를 뽑아서 주어진 소수들을 곱한 뒤 다시 큐에 넣는데, 왜 이 방식이 매 반복문마다 최소값을 보장할 수 있는지 이해하지 못했다. 다음에 다시 이해해보려고 한다.