[항해99] 정렬 알고리즘

정렬?

정렬은 데이터를 순서대로 나열하는 방법! 

이하로는 어떻게 데이터를 나열할 지에 대한 방법을 연습하고자 한다. 

 

Bubble Sort 버블 정렬

https://youtu.be/Iv3vgjM8Pv4?si=AAnMnxyka7DF5WtG&t=54

버블 소트를 가장 잘 나타내는 춤이라고 생각합니다.

a[0]에서부터 a[9]까지 붙은 원소끼리 서로 자리를 바꾸어나가고,

그다음은 a[0]부터 a[8]까지, 계속해서 반복하고 a[0], a[1]의 자리를 서로 맞추어주면 정렬이 되게 됩니다. 

def bubblesort(lst):
    iters = len(lst) - 1
    for iter in range(iters):
        wall = iters - iter
        for cur in range(wall):
            if lst[cur] > lst[cur + 1]:
                lst[cur], lst[cur+1] = lst[cur+1], lst[cur],

    return lst

 

끝의 원소부터 한칸씩 정렬이 된다고생각하면 됨! 

Selection Sort 선택 정렬

선택해서 정렬한다! 라고 생각하시면 됩니다. 

 

들쭉날쭉하게 사람이 일렬로 서있다면, 그 중 제일 작은 사람이 맨 앞으로 와! 

그 다음으로 작은 사람 두번째로 배치... 이렇게 반복하면 순서대로 정렬이 되겠죠.

def selectionsort(lst):
    iters = len(lst) - 1
    for iter in range(iters):
        minimum = iter
        for cur in range(iter + 1, len(lst)):
            if lst[cur] < lst[minimum]:
                minimum = cur

        if minimum != iter:
            lst[minimum], lst[iter] = lst[iter], lst[minimum]

    return lst

Insertion Sort 삽입정렬

삽입정렬은 정렬 되어있는 배열에 정렬 안 된 원소를 하나하나 넣는다고 생각하면 된다.

 

키순서대로 서있는데, 새로운 사람 한 명이 와서 자기 자리를 찾아 간다고 생각하면 편함! 

def insertionsort(lst):
    for cur in range(1, len(lst)):
        for d in range(1, cur + 1):
            cmp = cur - d
            if lst[cmp] > lst[cmp + 1]:
                lst[cmp], lst[cmp + 1] = lst[cmp + 1], lst[cmp],

            else:
                break

    return lst

Insertion Sort List 배열 삽입 정렬

https://leetcode.com/problems/insertion-sort-list/submissions/

LeetCode - The World's Leading Online Programming Learning Platform

배열이라고 했지만, 사실 LinkedList다. 

두개의 포인터를 이용해서, 하나는 마지막으로 정렬이 끝난 원소를, 하나는 지금 보고있는 원소를 본다.

정렬이 끝난 원소 다음 원소에 대해서 정렬된 원소를 돌면서 삽입 정렬을 하면 된다.

여기서 dummy_head는 임시로 정렬 끝난 원소를 담기 위한 노드인데, 이 노드의 next는 정렬 된 ListNode의 Head이다.

# Definition for singly-linked list.
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        dummy_head = ListNode(val=-1, next=head)
        last_sorted = head  # 마지막으로 정렬된 원소
        cur = head.next # cur은 이제 정렬해야하는 원소
        while cur:
            if cur.val >= last_sorted.val:
                last_sorted = last_sorted.next
        
            else:
                prev = dummy_head
                while (prev.next.val <= cur.val):
                    prev = prev.next
                
                last_sorted.next = cur.next
                cur.next = prev.next
                prev.next = cur
            
            cur = last_sorted.next
            
        return dummy_head.next

Largest Number 최댓값

https://leetcode.com/problems/largest-number/

Largest Number - LeetCode

String으로 가장 큰 원소를 리턴해라 라는 것이 문제의 목적인데,

어떻게 풀어야 할 지 전혀 감이 안 왔다. 

Int순으로 정렬을 해도, str순으로 정렬해도 한자리 수와 두자리 수를 한번에 sorting하는 것은 너무 어려웠다.

 

해답을 보니까 명쾌하더라. BubbleSort에서처럼 처음 원소와 다음 원소가 서로 바꾸었을 때 더 커지는 문자열 숫자라면, 위치를 바꾸는 연산을 버블소트처럼 처음부터 끝까지 반복문으로 돌리면 된다. ( 예를들어 10 2 -> 2 10 이니까 2 10이 더크면 서로 위치를 바꿈)

문제에서 생각할 것이 너무 많다면, 제일 작게 쪼개서 Divide and Conquer하자..

from typing import List


class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        lst = []

        for ele in nums:
            lst += [str(ele)]

        n = len(lst)

        for i in range(n):
            for j in range(i + 1, n):

                if str(lst[i]) + str(lst[j]) > str(lst[j]) + str(lst[i]):
                    continue
                else:
                    lst[i], lst[j] = lst[j], lst[i]

        ans = ''.join(lst)

        if int(ans) == 0:
            return "0"

        return ans

전화번호 목록

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

애를 엄청 많이 먹었다.

처음 접근은 모든 원소에 대해서 한 두원소씩 계속해서 짝지어서 큰 원소가 작은 원소를 포함하는 지를 체크해봤는데, 모든 원소 중에서 두 원소를 뽑는 알고리즘의 시간 복잡도가 O(N^2) 라서 시간초과 당했다...

import sys

# 처음 생각 : 문자열에 대해서 b in a 를 이용하면 좀 길긴해도 되긴 할 것 같다.
# 정렬하지 않고 모든 "문자열"에 대해서 bubble sort처럼 전부 조사
# -> 시간초과 O(n^2) 시간복잡도...

T = int(sys.stdin.readline().rstrip())
for _ in range(T):
    n = int(sys.stdin.readline().rstrip())
    lst = []
    for i in range(n):
        lst.append(sys.stdin.readline().rstrip())

    flag = 0
    for i in range(n):
        for j in range(i + 1, n):
            if len(lst[i]) == len(lst[j]): # 같은 수는 없으니까
                continue
            elif len(lst[i]) > len(lst[j]): # lst[i] 가 lst[j]보다 긴 경우
                if lst[j] in lst[i]:
                    flag = 1
                    break
            else: # lst[j]가 lst[i] 보다 긴 경우
                if lst[i] in lst[j]:
                    flag = 1
                    break
        if flag == 1:
            break

    if flag == 0:
        print("YES")
    if flag == 1:
        print("NO")

어떤 원소보다 긴 지 아닌 지도 if문을 여러개 써가면서 장황하고 복잡하게 풀었다 ( 물론 시간초과로 오답 ) 

import sys

# 처음 생각 : 문자열에 대해서 b in a 를 이용하면 좀 길긴해도 되긴 할 것 같다.
# -> 시간초과 O(n^2) 시간복잡도...

T = int(sys.stdin.readline().rstrip())

for _ in range(T):
    n = int(sys.stdin.readline().rstrip())
    lst = [sys.stdin.readline().rstrip() for _ in range(n)]

    lst.sort()  # 팀소트 함 ( nlogn )
    # 112  1122  11223

    # 반례 : 12 랑 112가 붙어있으면 YES 출력
    for idx in range(len(lst)-1):
        if lst[idx] in lst[idx + 1]:
            print("NO")
            break
    else:
        print("YES")

 

다음 생각한 것은 정렬이었다. 미리 정렬해놓는다면, 뒤에 나오는 원소는 무조건 다음 순서인 원소일 거니까 ( String 정렬일 경우 ) 다음 순서이면 앞 원소에 추가로 원소가 들어가거나, 앞 원소랑 차이를 가지거나 ( 다르고 글자순서가 뒤면 ) 둘 중 하나일테니까, a in b를 한번만 해도 되겠구나 ( 정렬에 O(nlogn),  a in b 연산 하는데 O(N) )의 시간이 걸리니, 그래도 좀 낫다 라는 생각으로 제출했다. 

import sys

T = int(sys.stdin.readline().rstrip())

for _ in range(T):
    n = int(sys.stdin.readline().rstrip())
    lst = [sys.stdin.readline().rstrip() for _ in range(n)]

    lst.sort() 

    for idx in range(len(lst)-1):
        # 앞부분만 서로 비교함 ( prefix )
        if lst[idx] == lst[idx + 1][:len(lst[idx])]:
            print("NO")
            break
    else:
        print("YES")

 

이전 풀이의 문제점은 in 의 기능을 일부만 보고 알고리즘을 짜서 생겼다.

반례로, 12와 112가 붙어있다면 당연히 YES를 출력해야하지만, 12라는 문자열은 112에 들어간다. 뒷부분에.

그래서 NO를 출력하게 된 것이다.

이를 해결하기 위해서, 앞의 원소의 길이만큼만 판단하도록 알고리즘을 수정해주면 제대로 작동하는 것을 알 수 있다. 

 

주말 평가 시험문제

1번. Race Results

https://www.acmicpc.net/problem/5939

5939번: Race Results

세 개의 값을 받아서 순서대로 출력하면 되는 구현문제. 

import Time을 이용해서 시 분 초를 저장해서 소팅한 사람도 봤고, 시 * 3600 + 분 * 60 + 초 를 해서 초로 환산한 시간을 소팅한 경우도 있었다. 

나는 그냥 시 분 초의 공간은 똑같으니까, 위치에 대해서 sort()해줬다. 파이썬 소팅은 stable Sort라서 값이 똑같은 원소에 대해서는 위치가 바뀌지 않는다

Stable Sort?

예를들어 0 3 / 1 1 / 0 1 을 소팅한다면 

index = 0를 가지고 소팅한 첫 결과는 0 3 / 0 1 / 1 1

이 배열을 index = 1을 가지고 소팅한 결과는 0 1 / 1 1 / 0 3 으로 0 1 과 1 1 의 위치가 바뀌지 않은 것을 볼 수 있다. 

이걸 stable sort라고 한다. 

String Permutation 문자열 순열

이 문제로 진짜 고생을 많이 했다. 교재에서 배운 대로 했는데, 왜 안될까... 하고 고민을 많이 해봤는데, 문제의 조건에 입력 문자열은 서로 다른 문자다 라는 말이 없어서 설마..? 하고 인덱스를 visited로 보고 DFS 를 돌리니까 정답 처리 되었다...

기존에 공부했던 코드는 len(visited) == len(s) 일때 visited를 모아서 출력하고 return 하는 구조였는데, 여기서 중복된 문자가 있다면 처리할 수 없다는 맹점이 존재했다. (visited에 방문한 문자를 넣는다면 항상 len(visited) < len(s)니까 )

그래서 인덱스를 visited 에 넣었고, 같은 문자열 순열에 대해서도 출력을 잘 하는 것을 볼 수 있었다. 

T = int(input())

for _ in range(1, T+1):
    s = input()
    print(f"Case # {_}:")

    def dfs(idx, visited):
# 문제 코드
        # visited.append(s[idx])
        # if len(visited) == len(s):
        #     print("".join(visited))
        #     return
        
# 수정 코드
        visited.append(idx)
        if len(visited) == len(s):
            ans = ""
            for char in visited:
                ans += s[char]
            print(ans)
            return
            
        for i in range(len(s)):
            if i not in visited:
                dfs(i, visited)
                visited.pop()

    for j in range(len(s)):
        dfs(j, [])

 

 

 

 

새롭게 알게 된 점

파이썬에서 쓰는 sort()는 Tim Sort 라는 소팅 알고리즘을 이용한다고 한다.

간단히 말하면, Insertion Sort와 Merge Sort를 사용하는 소팅 알고리즘이라고 하는데, 관심이 있다면 다음 글도 보도록 하자.

https://d2.naver.com/helloworld/0315536