์ ๋ ฌ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
์ด๋ ต๋ค!
์ค๋๋ ์ด์ฝ โ๏ธ
'SW์ฌ๊ดํ๊ต ์ ๊ธ > ๊ฐ๋ฐ์ผ์ง - TIL' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Week03] ์๊ณ ๋ฆฌ์ฆ - DFS / BFS ๋ฐฑ์ค ๋ฌธ์ (5) | 2022.04.21 |
---|---|
[Week03] ์๊ณ ๋ฆฌ์ฆ - ์ ๋์จ ํ์ธ๋ (3) | 2022.04.20 |
[Week02] ์๊ณ ๋ฆฌ์ฆ - ํ (feat. python) (2) | 2022.04.14 |
[Week02] ์๊ณ ๋ฆฌ์ฆ - ์ด๋ถํ์ (5) | 2022.04.09 |
[Week01] ์๊ณ ๋ฆฌ์ฆ - ์ฌ๊ทํจ์ (0) | 2022.04.07 |
๋๊ธ