🧪선택정렬 알고리즘 연습 - ref.23881

*해당 알고리즘 연습은 백준 23881번 문제를 참고 했음을 인지해 달라.

• 선형탐색

기본 형태의 선택형 알고리즘은 어려움이 없었다. 하지만 막상 문제를 통해서 구현하려고 하다보니 어려움을 느꼈다. 생각보다 많은 시간을 할애 하였고 이에 좌절하지 않고 몇일을 틀린 문제를 무한 반복하며 내가 무엇을 놓치고 있는지 생각을 했었다. 3일 걸릴 수 있는 것을 개인 사정 일정과 맞춰가며 문제를 풀다 보니 1주일 정도의 시간이 필요했다. 문제를 파익하고 이해했다기 보단 선택정렬이 어떻게 이루어졌으며 어떤 구조를 통해서 문제가 돌아가는지에 초점을 맞춘 포스팅이다.
우선 선택 정렬 알고리즘의 이중 for문만을 기준으로 바라본 그림은 아래와 같다.

조금 복잡해 보이니 리스트 요소 하나만을 동작 시켰을 때의 모습은 오른쪽과 같다. 코드는 아래와 같을 것이다.

 

N = [3, 1, 2, 5, 4]

 

for last in range(len(N)-1, -1, -1):

  

    for j in range(last, -1, -1):

 

이제 여기에 max 변수를 넣어서 값이 어떻게 할당 되는지 그림으로 확인해 보면 아래와 같다.

할당된 모습을 그림으로 그려내려면 전반적이 그림의 수정이 필요했다. 하지만 색깔로 보게 된다면 빨간색과 파란색들과의 비교만 으로 가장 큰 값이 어떤 건지 알 수 있다. 4를 기준으로 N[j]가 포함 할 수 있는 값들 중 가장 큰 값은 5가 된 다는 것을 알 수 있다. 그럼 다시 오른쪽 그림 처럼 last값을 끊고 max값은 j가 되는 것이다. 코드는 아래와 같다.

N = [3, 1, 2, 5, 4]

 

for last in range(len(N)-1, -1, -1):

    max = last

    for j in range(last, -1, -1):

        if N[max] < N[j]: 

            max = j  

 

그렇게 두 번째 for문에서 첫 번째 for문으로 범위가 좁혀 지면서 값을 계속해서 반복하는 것이다. 그렇다면 해당 범위 영역에서 max값은 5,0,3,3이 나올 것이다. if문에 print(N[max])를 해보면 확인 할 수 있다. 0은 출력되지 않을 것이다.
이후 스위치가 되는 구문 그림들 추가
아래 코드는 정렬이 완성되는 두가지 방법이다.
* 첫 번째 방법 :  max값을 판별하고 last의 인덱스 자리 값과 max의 인덱스 자리 값을 서로 switch한다.

 

N = [3, 1, 2, 5, 4]

for last in range(len(N)-1, -1, -1):

    max = last

    for j in range(last, -1, -1):  # 가장 큰 수를 찾는 loop

        if N[max] < N[j]:  # 가장 큰 수 판별

            max = j

            # switch

            N[max], N[last] = N[last], N[max]  # 방법 1

            

print(N)

*두 번째 방법 : max값과 j의 값이 판별이 되는 순간 바로 max 인덱스 자리 값과 j 인덱스 자리 값을 switch한다.

 

N = [3, 1, 2, 5, 4]

for last in range(len(N)-1, -1, -1):

    max = last

    for j in range(last, -1, -1):  # 가장 큰 수를 찾는 loop

        if N[max] < N[j]:  # 가장 큰 수 판별

            # switch

            N[max], N[j] = N[j], N[max]  # 방법 2

print(N)

 
23881번의 문제는 아직 제출 하지 않았다. 이후에 다시 문제를 풀어보고 문제를 제출해 볼 예정이다.

[백준] 23881번 알고리즘 수업 - 선택 정렬 1 - 파이썬