Social Developer

어제보다 한 걸음 더

Algorithms

이 문제도 10972번 문제와 마찬가지로 10819번 문제를 풀던 도중 라이브러리 사용을 하지 않고 모든 순열 탐색을 구현하기 위해 방법을 찾던 도중 접해 풀게 되었다. 10972번과 굉장히 유사한데, 이 문제의 특징은 모든 순열을 출력하는 것이다. 결과적으로, 10972번에서 사용한 다음 순열 찾기 알고리즘을 적용하기 전에, 입력으로 받은 N을 오름차순으로 1...N 배열을 먼저 생성한다. 이후, 알고리즘을 구현한 함수에 이 배열을 넣어 재귀적으로 모든 구간에서 내림차순일 때까지 반복 호출하면 된다. 함수가 다음 순열을 구하는 기능이기 때문에, 사전순으로 첫 순열도 먼저 출력해주고 N이 1이 아니라면 다음 순열을 구해 출력하는 구조로 구현했다. import sys def next_permutation(..

2021. 1. 8.

Algorithms

이 문제는 10819번 문제를 풀던 도중, 모든 순열을 반환하는 라이브러리 사용 외 직접 순열을 구하는 방법을 찾다가 접하게 되었다. 본 문제의 핵심은 '사전 순으로' 다음 순열을 찾아 내는 것인데, 이를 구현하는 방법으로 나리야나 판디타라는 수학자가 고안한 알고리즘이 이미 있다고 한다. 알고리즘을 처음 봤을 때는 어떤 의미인지 감이 잘 오지 않았는데, 직접 값을 넣어보면서 차츰 익숙해졌다. 알고리즘의 동작은 다음과 같다. 1) 배열 내에서 a[k]

2021. 1. 8.

Algorithms

그래프 - 1260, 11724, 1707, 10451, 2331, 9466, 2667, 4963, 7576, 2178, 2146, 1991, 11725, 1167, 1967 출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm] 알고리즘 문제풀이(PS) 시작하기 이런건 고수들이나 써야 하지 않나 싶지만, 그래도 1년정도 공부하면서 이 분야를 어떻게 시작해야 할지 써보려 한다. 라고 운을 뗀다음 열심히 내 얘기만 했던 후속편이다. 내 인생사가 궁금하 plzrun.tistory.com 1167번과 이 다음 1967번은 구조가 유사하다. 입력값을 부분을 제외하면 동일한 구조로 정답을 받을 수 있다. 1167번을 다른 분의 풀이를 ..

2021. 1. 1.