꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/10973 prev_permutation을 사용하면 간단히 풀 수 있는 문제였지만 직접 구현해봤습니다. 알고리즘은 아래와 같습니다.1. v[idx - 1] > v[idx]를 만족하는 가장 큰 idx를 찾습니다.2. idx2 >= idx이면서 v[idx2] > N; v.resize(N); for (int i = 0; i > v[i]; int idx = N - 1; //v[idx - 1] > v[idx]를 만족하는 가장 큰 idx를 찾는다 while (idx > 0 && v[idx - 1]

문제 링크입니다: https://www.acmicpc.net/problem/10972 next_permutation을 사용하면 간단히 풀 수 있는 문제였지만 직접 구현해봤습니다. 알고리즘은 아래와 같습니다.1. v[idx - 1] = idx이면서 v[idx2] > v[idx2-1]을 만족하는 가장 큰 idx2를 찾습니다.3. v[idx - 1]과 v[idx2]를 뒤바꿔줍니다.4. idx부터 순열을 뒤집어줍니다. #include #include #include using namespace std; int N; vector v; int main(void) { cin >> N; v.resize(N); for (int i = 0; i < N;..

문제 링크입니다: https://www.acmicpc.net/problem/5901 다익스트라 알고리즘을 이용해 푸는 문제였습니다. 알고리즘은 아래와 같습니다.1. 장터가 있는 마을을 입력받고, 해당 마을에 장터가 있다고 표시합니다.2. 양방향 그래프를 입력받고 각각의 마을에 대해 다익스트라 알고리즘을 통해 최단경로를 계산합니다.3. 어디에 거주를 할지 모르기 때문에 모든 경우의 수를 파악합니다.i) next_permutation을 이용하여 K! 순열을 확인합니다.ii) 처음과 끝은 해당 거주지로부터 출발하므로 양 끝 경로도 더해서 계산해야합니다.iii) ii) 중 최소의 값이 정답입니다. #include #include #include #include #include #include using name..

문제 링크입니다: https://www.acmicpc.net/problem/2529 순열을 이용하는 그리디(greedy) 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 그리디하게 접근했을 때 최대 숫자는 9 ~ (9 - K)의 숫자들로 이루어질 것이고 최소 숫자는 0 ~ K까지의 숫자들로 이루어질 것입니다.2. 초기에는 최대 숫자를 내림차순으로 벡터에 저장하고 최소 숫자를 오름차순으로 벡터에 저장한다.3. 2 번에서 구한 벡터들에 대해 반복문을 돌리는데 저장된 숫자들의 위치와 부등호 간에 모순이 없을 때까지 반복한다.i) 최대 숫자에 대해 모순이 발생하면 prev_permutation 함수를 이용하여 해당 숫자보다 작으면서 최대인 숫자로 바꿔준다.ii) 최소 숫자에 대해 모순이 발생하면 next..