#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.
#1489 대결
이번 문제는 Gold I 문제네요. A팀과 B팀이 n명의 사람들이 각각 1:1 대결해서 승패를 가리는데, 이기면 2점, 비기면 1점, 지면 0점을 받게 됩니다. 승부를 벌이는 두 사람의 능력치로 승패가 좌우되는데, 높은 능력치가 이기고, 능력치가 같으면 비기게 됩니다. 승부를 벌이는 두 팀의 n명의 능력치를 알고 있을 때, A팀이 얻을 수 있는 최대 점수를 계산하는 것이 목표입니다. 제가 생각한 방법은, 첫번째로 두 팀을 모두 정렬을 합니다. 두번째로 동적 계획법을 이용해서 A 팀이 얻을 수 있는 최대 점수를 구한다입니다. A 팀의 능력치를 오름차순으로 정렬했을 때, \( a_1, a_2, ..., a_n \)이라고 하고 B 팀 역시 \( b_1, b_2, ..., b_n \) 이라고 할 때, 다음과 같..
2022. 8. 19.
