세번째 작은 수 찾는 프로그램. 우선 처음 접근을 next_permutation을 통해 찾으려고 했는데, 해당 함수는 1,1,1 과 같은 중복된 숫자에 대해서 순열을 찾지 않는다는 것을 깨달았습니다. 이는 모든 요소가 동일하기 때문에 사전 순으로 더 이상의 다른 순열이 존재할 수 없기 때문입니다.  int i = 0; do { if (i == 2) { cout  그래서 dfs로 변경해서 풀었는데, 갯수가 10^8개가 되면서 dfs로 전부 찾으려고 하니까 시간 초과가 났다.생각해보니, 가장 작은 수 4개만 찾으면 세번째로 작은 수를 찾을 수 있을거라 판단하고 코드를 작성하여 해결했다. 정답 코드.#include #include #include #define fastio ios::sync_..

나무는 (x, y)라고 해놓고선 r,c로 들어왔다. 문제가 날 속임. (그래서 틀림...ㅠㅠ)결국 맞췄을땐 vector로하면 시간초과가 난다는 것을 알게 되었다. 처음에 문제 잘 읽고 시간 제한 보긴했지만 구현 문제라서 그냥 주어진 상황대로 풀었다. 둘을 비교했을때, 나무의 수가 커지면 커질수록 더 차이가 난다.# Let's calculate the complexity of both versions of the code to compare their potential performance.# Old Version (using vector):# In the old version, we have:# - Spring: Sorting the entire vector by age each spring, which..

다익스트라 정리 다익스트라 풀이처음에 다익스트라로 n까지 최단 거리 구함. (구하면서 prev에 간선 정보들을 저장)prev를 이용하여 graph에서 해당하는 간선들을 삭제.다시 다익스트라를 돌려서 n까지 가는 최단 거리를 구함.고려한 점도시는 양방향으로 이동할 수 있다. (최단거리라면 양방향 둘 다 막힌다)다른 도시로 이동할 때 코스트가 다른 도로가 존재할 수 있다 ( 1->2 (1), 1->2 (2)) 이때 cost 가 1인 도로만 막힘탈출하지 못하는 경우는 없다.정답 코드더보기#include using namespace std;#define INF 1e9void dijkstra(int n, vector>>& graph, vector& distance, vector& prev..

다이나믹프로그래밍과 다익스트라 두 방법 모두 사용할 수 있습니다. 시간 복잡도시간 복잡도는 O(D + N)입니다.D는 고속도로의 길이, N은 지름길의 수입니다.문제에서 N ≤ 12, D ≤ 10,000이므로, 이 접근 방식은 충분히 효율적입니다. C++ DP 풀이.#include using namespace std;#define INF 1e9int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, d; cin >> n >> d; vector> graph[10001]; for (int i = 0; i > from >> to >> cost; if (to dist(d + 1, INF); dist[0] = 0; for (int ..

문제 개요는 2048게임을 구현하는 것.입력첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.출력최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다. 접근 방법. 4방향으로 합치고, 미는 dfs의 방법을 통해. 5번 할 수 있는 모든 방법을 찾아낸 뒤. 최대값으로 출력. 더보기/* ************************************************************************** *//* ..