๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
SW์‚ฌ๊ด€ํ•™๊ต ์ •๊ธ€/๊ฐœ๋ฐœ์ผ์ง€ - TIL

[Week01] ์•Œ๊ณ ๋ฆฌ์ฆ˜ - ์ •๋ ฌ01

by young-ji 2022. 4. 9.

์ •๋ ฌ01

โœ… ํŒŒ์ด์ฌ ๋‚ด์žฅํ•จ์ˆ˜

  • arr.sort() : ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ
  • arr.sort(reverse = True) : ๋‚ด๋ฆผ์ฐจ์ˆœ ์ •๋ ฌ

#๋ฐฑ์ค€11650 - key๊ฐ’์œผ๋กœ ์ •๋ ฌ

arr = []
for _ in range(int(input())):
    arr.append(list(map(int, input().split())))
 
arr.sort(key=lambda x:(x[0], x[1]))
#x[0]์˜ ํฌ๊ธฐ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌ, ๊ฐ’์ด ๊ฐ™๋‹ค๋ฉด x[1]์œผ๋กœ ๋น„๊ต
 
for e in arr:
    print(str(e[0]) + " " + str(e[1]))

 

 

โœ… ๋ฒ„๋ธ” ์ •๋ ฌ

: ์„œ๋กœ ์ธ์ ‘ํ•œ ๋‘ ์›์†Œ๋ฅผ ๊ฒ€์‚ฌํ•˜์—ฌ ์ •๋ ฌํ•œ๋‹ค. (swap)

์‹œ๊ฐ„๋ณต์žก๋„ O(N^2)

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1): #len(arr)-1 ์—์„œ 0๊นŒ์ง€ ์—ญ์ˆœ์œผ๋กœ
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

 

โœ… ์„ ํƒ ์ •๋ ฌ 

: ๋ฆฌ์ŠคํŠธ์— ์ตœ์†Ÿ๊ฐ’์„ ์ฐพ์•„ ๋งจ ์•ž์— ์œ„์น˜์‹œํ‚จ๋‹ค. (swap)

์‹œ๊ฐ„๋ณต์žก๋„ O(N^2)

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

 

โœ… ์‚ฝ์ž… ์ •๋ ฌ

: ์†์•ˆ์— ์นด๋“œ(key)๋ฅผ ๋น„๊ตํ•˜๋Š” ๋ฐฉ์‹. ๋‘๋ฒˆ์งธ ์›์†Œ๋ถ€ํ„ฐ ๊ทธ ์•ž ์ชฝ์˜ ์›์†Œ๋“ค์„ ํ™•์ธํ•ด ์‚ฝ์ž…ํ•  ์œ„์น˜ ํ™•์ธํ•˜์—ฌ ํ•˜๋‚˜์”ฉ ๋’ค๋กœ ๋ฏธ๋ฃฌ๋‹ค.

์‹œ๊ฐ„๋ณต์žก๋„ O(N^2)

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]

 

#๋ฐฑ์ค€2750 - ๋ฒ„๋ธ”์ •๋ ฌ, ์„ ํƒ์ •๋ ฌ, ์‚ฝ์ž…์ •๋ ฌ์„ ์ด์šฉํ•ด ํ•ด๊ฒฐ๊ฐ€๋Šฅ

 

โœ… ์…€ ์ •๋ ฌ

: ์‚ฝ์ž… ์ •๋ ฌ์„ ๋ณด์•ˆํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜. ์š”์†Œ๊ฐ€ ์‚ฝ์ž…๋ ๋•Œ ์ด์›ƒํ•œ ์œ„์น˜๋กœ๋งŒ ์ด๋™ ๊ฐ€๋Šฅํ•˜๋‹ค๋Š” ์‚ฝ์ž… ์ •๋ ฌ์˜ ๋‹จ์ ์„ ๋ณด์•ˆํ•œ๋‹ค.

: ์ •๋ ฌํ•ด์•ผ ํ•  ๋ฆฌ์ŠคํŠธ์˜ ๊ฐ k๋ฒˆ์งธ ์š”์†Œ๋ฅผ ์ถ”์ถœํ•ด์„œ ๋ถ€๋ถ„ ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ ๋‹ค. ์ด๋•Œ k๋ฅผ '๊ฐ„๊ฒฉ'์ด๋ผ๊ณ  ํ•œ๋‹ค. 

์‹œ๊ฐ„๋ณต์žก๋„ O(N^1.5)

def shell_sort(arr):
    N = len(arr)
    k = N // 2
    while k > 0:
        for i in range(k, N):
            temp = arr[i]
            j = i - k
            #์‚ฝ์ž…์ •๋ ฌ
            while j >= 0 and arr[j] > temp:
                arr[j + k] = arr[j]
                j -= k
            arr[j + k] = temp
        k //= 2

์–ด๋ ต๋‹ค!

 

 

์˜ค๋Š˜๋„ ์—ด์ฝ” โ—๏ธ

๋Œ“๊ธ€