์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- Swift
- SOPT
- ๋์ ๊ณํ๋ฒ
- SwiftUI Tutorials
- SwiftUI ํํ ๋ฆฌ์ผ
- APPJAM
- URLSession
- ์ฐ์ํ์ค๋ถ๋ถ์์ด์ํฉ
- Til
- algoritm
- ์ด์งํ์
- discardableResult
- ํ๋ก๊ทธ๋๋จธ์ค
- 0์ด๋์ด์๋๊ธธ
- duno
- ๋ค์ด๋๋ฏนํ๋ก๊ทธ๋๋ฐ
- binarySearch
- GCD
- ๊ณ ๋์ kit
- SwiftUI
- ๊ธฐ์ด๋ฌธ๋ฒ
- dfs
- SQL
- concurrency
- algorithm
- GroupBy
- BFS
- HAVIT
- IOS
- DynamicProgramming
- Today
- Total
suvera-dev ๐ฅฆ
Algorithm ) Greedy ๋ณธ๋ฌธ
์ฝ๋ฉํ ์คํธ์์ ๊ฐ์ฅ ์ถ์ ๋น๋๊ฐ ๋์ ๋ฌธ์ ๋ ๊ทธ๋ฆฌ๋, ๊ตฌํ, DFS/BFS ๋ฅผ ํ์ฉํ ํ์ ๋ฌธ์ ๋ผ๊ณ ํ๋ค!
์์๋๋ก ํฌ์คํ ํ ์์ ์ด๊ณ , ์ค๋์ ๊ธฐ์ด ๊ทธ๋ฆฌ๋ ๋ฌธ์ ์ ๋ํด ๋ค๋ค๋ณด๊ณ ์ ํ๋ค
๐ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ : ํ์๋ฒ, ํ์ฌ ์ํฉ์์ ์ง๊ธ ๋น์ฅ ์ข์ ๊ฒ๋ง ๊ณ ๋ฅด๋ ๋ฐฉ๋ฒ
- ์ผ๋ฐ์ ์ผ๋ก ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ฌธ์ ๋ฅผ ํ๊ธฐ ์ํ ์ต์ํ์ ์์ด๋์ด๋ฅผ ๋ ์ฌ๋ฆด ์ ์๋ ๋ฅ๋ ฅ์ ์๊ตฌ
- ์ ๋น์ฑ ๋ถ์์ด ์ค์ : ๋จ์ํ ๊ฐ์ฅ ์ข์๋ณด์ด๋ ๊ฒ์ ๋ฐ๋ณต์ ์ผ๋ก ์ ํํด๋ ์ต์ ์ ํด๋ฅผ ๊ตฌํ ์ ์๋์ง ๊ฒํ
- ์ผ๋ฐ์ ์ธ ์ํฉ์์ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ต์ ์ ํด๋ฅผ ๋ณด์ฅํ ์ ์์ ๋๊ฐ ๋ง์
- ํ์ง๋ง, ์ฝ๋ฉํ ์คํธ์์ ๋๋ถ๋ถ์ ๊ทธ๋ฆฌ๋ ๋ฌธ์ ๋ ํ์๋ฒ์ผ๋ก ์ป์ ํด๊ฐ ์ต์ ์ ํด๊ฐ ๋๋ ์ํฉ์์ ์ด๋ฅผ ์ถ๋ก ํ ์ ์์ด์ผ ํ๋ฆฌ๋๋ก ์ถ์ ๋จ
๐ต๋ํ์ ์ธ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ! ๊ฑฐ์ค๋ฆ๋
500์, 100์, 50์, 10์์ง๋ฆฌ ๋์ ์ด ๋ฌดํํ ์กด์ฌ
-> ์๋์๊ฒ ๊ฑฐ์ฌ๋ฌ์ค์ผ ํ ๋์ด N์์ผ ๋ ๊ฑฐ์ฌ๋ฌ์ค์ผ ํ ๋์ ์ ์ต์ ๊ฐ์ ?
(๋จ, ๊ฑฐ์ฌ๋ฌ ์ค์ผ ํ ๋ N์ ํญ์ 10์ ๋ฐฐ์)
โก๏ธ๋ฌธ์ ํด๊ฒฐ ์์ด๋์ด
- ์ต์ ์ ํด๋ฅผ ๊ฐ์ฅ ๋น ๋ฅด๊ฒ ๊ตฌํ๊ธฐ ์ํด์ ๊ฐ์ฅ ํฐ ํํ๋จ์ ๋ถํฐ ๋์ ๊ฑฐ์ฌ๋ฌ ์ฃผ๋ ๊ฒ
- N์์ ๊ฑฐ์ฌ๋ฌ ์ค ๋, 500์์ผ๋ก ๊ฑฐ์ฌ๋ฌ ์ค ์ ์์ ๋งํผ ๊ฑฐ์ฌ๋ฌ ์ฃผ๊ณ , ๊ทธ ๋ค์ 100 50 10 ์์ง๋ฆฌ ๋์ ์ ์ฐจ๋ก๋๋ก ๊ฑฐ์ฌ๋ฌ ์ฃผ๊ธฐ
n = 1260
count = 0
# ํฐ ๋จ์์ ํํ๋ถํฐ ์ฐจ๋ก๋ก ํ์ธํ๊ธฐ
array = [500, 100, 50, 10]
for coin in array:
count += n // coin # ํด๋น ํํ๋ก ๊ฑฐ์ฌ๋ฌ ์ค ์ ์๋ ๋์ ์ธ๊ธฐ
n %= coin
print(count)
๐ฅฆ ์ ๋น์ฑ ๋ถ์
- ๊ฐ์ง๊ณ ์๋ ๋์ ์ค์์ ํฐ ๋จ์๊ฐ ํญ์ ์์ ๋จ์์ ๋ฐฐ์์ด๋ฏ๋ก ์์ ๋จ์์ ๋์ ๋ค์ ์ข ํฉํด ๋ค๋ฅธ ํด๊ฐ ๋์ฌ ์ ์์
- ๋๋ถ๋ถ์ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ์์๋ ์ด์ฒ๋ผ ๋ฌธ์ ํ์ด๋ฅผ ์ํ ์ต์ํ์ ์์ด๋์ด๋ฅผ ๋์ฌ๋ฆฌ๊ณ ์ด๊ฒ์ด ์ ๋นํ์ง ๊ฒํ ํ ์ ์์ด์ผ ๋ต์ ๋์ถ ํ ์ ์์
๐ ์๊ฐ ๋ณต์ก๋ ๋ถ์
- ํํ์ ์ข ๋ฅ๊ฐ K ๋ผ๊ณ ํ ๋, ์์ค์ฝ๋์ ์๊ฐ ๋ณต์ก๋๋ O(K)
- ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋๋ ๊ฑฐ์ฌ๋ฌ์ค์ผํ๋ ๊ธ์ก๊ณผ๋ ๋ฌด๊ด, ํํ์ ์ข ๋ฅ๋งํผ ๋ฐ๋ณตํ๋ฉด ๋ฌธ์ ํด๊ฒฐ
์ด๋ค ์ฝ๋ฉํ ์คํธ ๋ฌธ์ ๋ฅผ ๋ง๋ฌ์ ๋ , ๋ฐ๋ก ๋ฌธ์ ์ ํ์ ํ์ ํ๊ธฐ ์ด๋ ต๋ค๋ฉด ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ์์ฌํ๊ณ , ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ ํ์์ ์ธ ํด๊ฒฐ๋ฒ์ด ์กด์ฌํ๋์ง ๊ณ ๋ฏผํด๋ณด์. ์ค๋ ์๊ฐ์ ๊ณ ๋ฏผํด๋ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํด๊ฒฐ๋ฐฉ๋ฒ์ ์ฐพ์ ์ ์๋ค๋ฉด, ์ดํ์ ๋ค๋ฃจ๊ฒ ๋ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ด๋ ๊ทธ๋ํ ์๊ณ ๋ฆฌ์ฆ ๋ฑ์ผ๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋์ง ์ฌ์ฐจ ๊ณ ๋ฏผ !
์ค์ ๋ก ๊ฑฐ์ค๋ฆ๋ ๋ฌธ์ ์์ ๋์ ์ ๋จ์๊ฐ ์๋ก ๋ฐฐ์ ํํ๊ฐ ์๋๋ผ ๋ฌด์์๋ก ์ฃผ์ด์ง ๊ฒฝ์ฐ์๋ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํด๊ฒฐ ํ ์ ์๋ค. ํํ์ ๋จ์๊ฐ ๋ฌด์์๋ก ์ฃผ์ด์ง ๋ฌธ์ ๋ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ผ๋ก ํด๊ฒฐํ ์ ์๋ค.
์ค์ ๋ฌธ์ ํ์ด
1๏ธโฃ๋ฌธ์ 1 : ํฐ ์์ ๋ฒ์น
- ๋ค์ํ ์๋ก ์ด๋ฃจ์ด์ง ๋ฐฐ์ด์ด ์์ ๋ ์ฃผ์ด์ง ์๋ค์ M ๋ฒ ๋ํ์ฌ ๊ฐ์ฅ ํฐ ์๋ฅผ ๋ง๋๋ ๋ฒ์น์ด๋ค
- ๋จ, ๋ฐฐ์ด์ ํน์ ํ ์ธ๋ฑ์ค์ ํด๋นํ๋ ์๊ฐ ์ฐ์ํด์ K๋ฒ์ ์ด๊ณผํ์ฌ ๋ํด์ง ์ ์๋ ๊ฒ์ด ํน์ง์ด๋ค
- ์๋ฅผ ๋ค์ด ์์๋๋ก 2,4,5,4,6 ์ผ๋ก ์ด๋ฃจ์ด์ง ๋ฐฐ์ด์ด ์์ ๋ M์ด 8์ด๊ณ , K๊ฐ 3์ด๋ผ๊ณ ๊ฐ์ ํด๋ณด์.
์ด ๊ฒฝ์ฐ ํน์ ํ ์ธ๋ฑ์ค์ ์๊ฐ ์ฐ์ํด์ 3๋ฒ๊น์ง๋ง ๋ํด์ง ์ ์์ผ๋ฏ๋ก 6+6+6+5+6+6+6+5 ์ธ 46์ด ๋๋ค.
- ๋จ, ์๋ก ๋ค๋ฅธ ์ธ๋ฑ์ค์ ํด๋นํ๋ ์๊ฐ ๊ฐ์ ๊ฒฝ์ฐ์๋ ์๋ก ๋ค๋ฅธ ๊ฒ์ผ๋ก ๊ฐ์ฃผ. ๋๋ฒ์งธ ์ธ๋ฑ์ค์ 4์ ๋ค๋ฒ์งธ ์ธ๋ฑ์ค์ 4๋ ๋ค๋ฅด๋ค.
๐ ์ ๋ ฅ์กฐ๊ฑด
- ์ฒซ์งธ ์ค์ N, M, K ์ ์์ฐ์๊ฐ ์ฃผ์ด์ง๋ฉฐ, ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ
- ๋์งธ ์ค์ N๊ฐ์ ์์ฐ์๊ฐ ์ฃผ์ด์ง๋ฉฐ, ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ. ๋จ ๊ฐ๊ฐ์ ์์ฐ์๋ 1 ์ด์ 10000์ดํ์ ์๋ก ์ฃผ์ด์ง๋ค.
- ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ K๋ ํญ์ M๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค
๐ ์ถ๋ ฅ์กฐ๊ฑด
- ํฐ ์์ ๋ฒ์น์ ๋ฐ๋ผ ๋ํด์ง ๋ต์ ์ถ๋ ฅํ๋ค.
- ๋ฌธ์ ํด๊ฒฐ ์์ด๋์ด : ๊ฐ์ฅ ํฐ ์์ ๋๋ฒ์งธ๋ก ํฐ ์ ๋ง ์ ์ฅํ๊ณ , ์ฐ์์ผ๋ก ์ต๋ k๋ฒ ๋ํ ์ ์์ผ๋ฏ๋ก ๊ฐ์ฅ ํฐ์๋ฅผ k๋ฒ ๋ํ๊ณ ๋ ๋ฒ์งธ๋ก ํฐ์๋ฅผ 1๋ฒ๋ง ๋ํ๋ ๊ฒ์ ๋ฐ๋ณตํ์!
# N,M,K ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถํ์ฌ ์
๋ ฅ๋ฐ๊ธฐ , N๊ฐ์ ์๋ฅผ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถํ์ฌ ์
๋ ฅ๋ฐ๊ธฐ
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort() # ์
๋ ฅ๋ฐ์ ์๋ฅผ ์ ๋ ฌ
first = data[n - 1] #๊ฐ์ฅ ํฐ์
second = data[n - 2] #๋๋ฒ์งธ๋ก ํฐ์
result = 0
while True:
for i in range(k): # ๊ฐ์ฅ ํฐ ์๋ฅผ k๋ฒ ๋ํ๊ธฐ
if m == 0: # m์ด 0์ด๋ผ๋ฉด ๋ฐ๋ณต๋ฌธ ํ์ถ
break
result += first
m -= 1 # ๋ํ ๋ ๋ง๋ค 1์ฉ ๋นผ๊ธฐ
if m == 0:
break
result += second # ๋๋ฒ์งธ๋ก ํฐ ์๋ฅผ ํ๋ฒ๋ง ๋ํ๊ธฐ
m -= 1 # ๋ํ ๋๋ง๋ค 1์ฉ ๋นผ๊ธฐ
print(result)
ํ์ด 1 : ๋จ์ํ๊ฒ ํธ๋ ์์ -> M์ ์๊ฐ ์ปค์ง๋ค๋ฉด? ์๊ฐ์ด๊ณผ์ ๊ฐ๋ฅ์ฑ์ด ์์ผ๋ฏ๋ก, ๋ ํจ์จ์ ์ธ ํ์ด ํ์
# N,M,K ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถํ์ฌ ์
๋ ฅ๋ฐ๊ธฐ , N๊ฐ์ ์๋ฅผ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถํ์ฌ ์
๋ ฅ๋ฐ๊ธฐ
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort() # ์
๋ ฅ๋ฐ์ ์๋ฅผ ์ ๋ ฌ
first = data[n - 1] #๊ฐ์ฅ ํฐ์
second = data[n - 2] #๋๋ฒ์งธ๋ก ํฐ์
# ๊ฐ์ฅ ํฐ ์๊ฐ ๋ํด์ง๋ ํ์ ๊ณ์ฐ
count = int(m / (k+1)) * k # m์ k+1 ๋ก ๋๋ ๋ชซ์ k ๊ณฑํ๊ธฐ
count += m % (k + 1) # ๋๋์ด ๋จ์ด์ง์ง ์๋ ๊ฒฝ์ฐ, ๋๋จธ์ง ๋งํผ ํฐ์๊ฐ ๋ํด์ง๋ค
result = 0
result += (count) * first # ๊ฐ์ฅ ํฐ์ ๋ํ๊ธฐ
result += (m - count) * second # ๋๋ฒ์งธ๋ก ํฐ์ ๋ํ๊ธฐ
print(result)
ํ์ด 2 : ๋ฐ๋ณต๋๋ ์์ด์ ๋ํด์ ํ์ -> ๊ฐ์ฅ ํฐ ์์ ๋๋ฒ์งธ๋ก ํฐ ์๊ฐ ๋ํด์ง ๋์๋ ํน์ ํ ์์ด ํํ๋ก ์ผ์ ํ๊ฒ ๋ฐ๋ณตํด์ ๋ํด์ง๋ ๊ฒฝํฅ์ด ์์ -> ๊ทธ ๊ธธ์ด๋ K + 1
๐ฅ M์ K + 1๋ก ๋๋ ๋ชซ์ด ์์ด์ด ๋ฐ๋ณต๋๋ ํ์๊ฐ ๋๊ณ , ์ฌ๊ธฐ์ K ๋ฅผ ๊ณฑํด์ฃผ๋ฉด ๊ฐ์ฅ ํฐ ์๊ฐ ๋ฑ์ฅํ๋ ํ์๊ฐ ๋๋ค
๋ง์ฝ์ ๋๋์ด ๋จ์ด์ง์ง ์๋ ๊ฒฝ์ฐ ๋๋จธ์ง๋งํผ ๊ฐ์ฅ ํฐ ์๊ฐ ๋ํด์ง๋ฏ๋ก ์ด๋ฅผ ๋ํด์ค๋ค !
๊ฒฐ๊ณผ์ ์ผ๋ก, ์ต์ข ๊ฒฐ๊ณผ ๊ฐ์ ์ด ํ์ ๋งํผ ๊ฐ์ฅ ํฐ ์๋ฅผ ๋ํด์ฃผ๊ณ ๋จ์ ํ์๋งํผ ๋๋ฒ์งธ๋ก ํฐ ์ ๋ฅผ ๋ํด์ค๋ค !
'Algorithm > CodingTest - Python' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
Algorithm) DFS/BFS ์ค์ ๋ฌธ์ (0) | 2022.04.02 |
---|---|
Algorithm) DFS/BFS (0) | 2022.04.02 |
Algorithm) ์๋ฃ๊ตฌ์กฐ ๊ธฐ์ด (Feat. DFS์ BFS์ ๋ค์ด๊ฐ๊ธฐ ์ ..) (1) | 2022.04.01 |
Algorithm ) Implementation (0) | 2022.04.01 |
Algorithm ) Greedy (2) (2) | 2022.02.06 |