์ ๋ ฌ(Sorting)
๋ฐ์ดํฐ๋ฅผ ํน์ ํ ๊ธฐ์ค์ ๋ฐ๋ผ ์์๋๋ก ๋์ดํ๋ ๊ฒ์ ๋งํ๋ค.
์ ํ ์ ๋ ฌ(Selection Sort)
์ ๋ ฌ๋์ง ์์ ๋ฐ์ดํฐ ์ค์์ ๊ฐ์ฅ ์์ ๊ฒ์ ์ ํํด ๋งจ ์์ผ๋ก ๋ณด๋ธ๋ค.
๋ค๋ฅธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ๋ค์ ๋นํด ๋นํจ์จ์ ์ด๋ค.
→ ์๊ฐ ๋ณต์ก๋: O(N^2)
์ฝ์ ์ ๋ ฌ(Insertion Sort)
๋ฐ์ดํฐ๋ฅผ ํ๋์ฉ ํ์ธํ๋ฉฐ, ๊ฐ ๋ฐ์ดํฐ๋ฅผ ์ ์ ํ ์์น์ ์ฝ์ ํ๋ค.
๋ฐ์ดํฐ๊ฐ ๊ฑฐ์ ์ ๋ ฌ๋์ด ์์ ๋ ํจ์จ์ ์ด๋ค.
→ ์๊ฐ ๋ณต์ก๋: O(N^2) <์ต์ ์ ๊ฒฝ์ฐ O(N)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.>
ํต ์ ๋ ฌ(Quick Sort)
๊ธฐ์ค ๋ฐ์ดํฐ๋ฅผ ์ค์ ํ๊ณ , ๊ทธ ๊ธฐ์ค๋ณด๋ค ํฐ ๋ฐ์ดํฐ์ ์์ ๋ฐ์ดํฐ์ ์์น๋ฅผ ๋ฐ๊พผ๋ค.
- ํผ๋ฒ(Pivot): ๊ธฐ์ค ๋ฐ์ดํฐ
→ ํ๊ท ์๊ฐ ๋ณต์ก๋: O(NlogN)
๊ณ์ ์ ๋ ฌ(Count Sort)
- ๊ฐ์ฅ ์์ ๋ฐ์ดํฐ๋ถํฐ ๊ฐ์ฅ ํฐ ๋ฐ์ดํฐ๊น์ง ๋ชจ๋ ๋ด๊ธธ ์ ์๋ ๋ฐฐ์ด(๋ฆฌ์คํธ)์ ์ ์ธํ๋ค.
- ๋ฐ์ดํฐ๋ฅผ ํ๋์ฉ ํ์ธํ์ฌ ๋ฐ์ดํฐ์ ๊ฐ๊ณผ ๋์ผํ ์ธ๋ฑ์ค์ ๋ฐฐ์ด ๊ฐ์ 1์ฉ ์ฆ๊ฐ์ํจ๋ค.
- ๋ฐฐ์ด์๋ ๊ฐ ๋ฐ์ดํฐ๊ฐ ๋ช ๋ฒ ๋ฑ์ฅํ๋์ง ํ์๊ฐ ๊ธฐ๋ก๋๊ณ ๊ทธ ๊ฐ๋งํผ ์ธ๋ฑ์ค๋ฅผ ์์ฐจ์ ์ผ๋ก ์ถ๋ ฅํ๋ค.
๋ฐ์ดํฐ์ ํฌ๊ธฐ ๋ฒ์๊ฐ ์ ํ๋์ด ์ ์ ํํ๋ก ํํํ ์ ์์ ๋๋ง ์ฌ์ฉ ๊ฐ๋ฅํ๋ค.
๋งค์ฐ ๋น ๋ฅธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ
→ ์๊ฐ ๋ณต์ก๋: O(N+K)
์ ๋ ฌ ๋ฌธ์
์์์ ์๋๋ก
ํ๋์ ์์ด์๋ ๋ค์ํ ์๊ฐ ์กด์ฌํ๋ค. ์ด๋ฌํ ์๋ ํฌ๊ธฐ์ ์๊ด์์ด ๋์ด๋์ด ์๋ค.
์ด ์๋ฅผ ํฐ ์๋ถํฐ ์์ ์์ ์์๋ก ์ ๋ ฌํด์ผ ํ๋ค. ์์ด์ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
var n = Int(readLine()!)!
var arr = [Int]()
for _ in 0..<n{
arr.append(Int(readLine()!)!)
}
print(arr.sorted(by: >))
์ฑ์ ์ด ๋ฎ์ ์์๋ก ํ์ ์ถ๋ ฅ
N๋ช ์ ํ์ ์ ๋ณด๊ฐ ์๋ค. ํ์ ์ ๋ณด๋ ํ์์ ์ด๋ฆ๊ณผ ํ์์ ์ฑ์ ์ผ๋ก ๊ตฌ๋ถ๋๋ค.
๊ฐ ํ์์ ์ด๋ฆ๊ณผ ์ฑ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋ ์ฑ์ ์ด ๋ฎ์ ์์๋๋ก ํ์์ ์ด๋ฆ์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
var n = Int(readLine()!)!
var arr = [(String,Int)]()
for _ in 0..<n{
let input_data = readLine()!.split(separator: " ").map{String($0)}
arr.append((input_data[0],Int(input_data[1])!))
}
print(arr.sorted(by: { first, second in first.1 < second.1}).map{$0.0})
๋ ๋ฐฐ์ด์ ์์ ๊ต์ฑ
๋๋น์ด๋ ๋ ๊ฐ์ ๋ฐฐ์ด A์ B๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ๋ ๋ฐฐ์ด์ N๊ฐ์ ์์๋ก ๊ตฌ์ฑ๋์ด ์์ผ๋ฉฐ, ์์๋ ๋ชจ๋ ์์ฐ์์ด๋ค.
๋๋น์ด๋ ์ต๋ K๋ฒ์ ๋ฐ๊ฟ์น๊ธฐ ์ฐ์ฐ์ ์ํํ ์ ์๋๋ฐ,
๋ฐ๊ฟ์น๊ธฐ ์ฐ์ฐ์ด๋ ๋ฐฐ์ด A์ ์๋ ์์ ํ๋์ ๋ฐฐ์ด B์ ์๋ ์์ ํ๋๋ฅผ ๊ณจ๋ผ์ ๋ ์์๋ฅผ ์๋ก ๋ฐ๊พธ๋ ๊ฒ์ด๋ค.
๋๋น์ด์ ์ต์ข ๋ชฉํ๋ ๋ฐฐ์ด A์ ๋ชจ๋ ์์์ ํฉ์ด ์ต๋๊ฐ ๋๋๋ก ํ๋ ๊ฒ์ด๋ค.
var inputdata = readLine()!.split(separator: " ").map{Int(String($0))!}
var n = inputdata[0], k = inputdata[1]
var arr_A = readLine()!.split(separator: " ").map{Int(String($0))!}
var arr_B = readLine()!.split(separator: " ").map{Int(String($0))!}
arr_A = arr_A.sorted()
arr_B = arr_B.sorted(by: >)
for i in 0..<k{
if arr_A[i] < arr_B[i]{
swap(&arr_A[i], &arr_B[i])
}
else {break}
}
print(arr_A.reduce(0, +))
'๐ Computer Science > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๊ณ ๋ฆฌ์ฆ] ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ(Dynamic Programming) (0) | 2022.03.30 |
---|---|
[์๊ณ ๋ฆฌ์ฆ] ์ด์ง ํ์(Binary Search) (0) | 2022.03.25 |
[์๊ณ ๋ฆฌ์ฆ] DFS/ BFS (0) | 2022.03.23 |
[์๊ณ ๋ฆฌ์ฆ] ๊ตฌํ(Implementation) (0) | 2022.03.22 |
[์๊ณ ๋ฆฌ์ฆ] ๊ทธ๋ฆฌ๋(Greedy) (0) | 2022.03.08 |