#1517 버블 소트
버블 소트는 정렬에서 가장 재미있는 정렬 방식이자, 사실 실생활에서도 많이 이루어지는 정렬 방식이죠. 이웃하는 것끼리 크기를 비교해서 위치가 잘못되었으면 서로 교환을 하는 방식입니다. 대략 해당되는 알고리즘을 코드로 표현하면 다음과 같습니다. function Bubble(a, from, to): for i in (to, from+1, -1): for j in (from, i-1): if a[j] > a[j+1]: swap(a, j, j+1) 위의 알고리즘에서 swap하는 횟수가 몇번인가를 구하는 것이 이번 문제죠. 이 문제를 풀기 위해서 swap 횟수는 몇번 일어날 것인지 알아볼께요. 3, 5, 1, 2, 4 라는 수열이 있습니다. 3 5 1 2 4 이 수열이 버블 정렬에 의해서 swap이 발생하는 과정..
2022. 8. 23.
#1494 절대값 수열
절대값 수열 문제는 전체적으로 감소하는 수열의 특징을 이용하시면 됩니다. 일반적으로 비율로 줄어드는 수열의 경우에는 그 비율이 \(1/\varphi\)인 경우 가장 오래 갈 수 있습니다. 절대값 수열도 크게 다르지 않기 때문에, 가장 긴 수열을 얻기 위해서는 \(1/\varphi\) 비율에 가까워야 합니다. 정수에서는 1618:1000 정도의 비율입니다. 이 문제는 Platinum I 문제이지만, 수열 법칙을 조금 이해하시면 풀 수 있습니다. 60과 1로 시작하는 수열을 생각해보면, 60, 1, 59, 58, 1, 57, 56, 1, 55, 54, 1, ..., 2, 1, 1, 0, 1, 1, 0, .... 형태로 전체적으로 감소하는 수열이 됩니다. 이 중 두번째 값인 1이 여러번 반복하게 되는데, 이 ..
2022. 8. 22.
