์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
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 |
- ๋จ๋ฐฉํฅํ์
- ์๊ณ ๋ฆฌ์ฆ
- ๋ชจ๋ํ
- subscreen
- SAP
- Import
- call function
- Export
- ์ด๋ถํ์
- t์ฝ๋
- screen program
- screen
- abap dictionary
- qas
- PRD
- ๋๋น์ฐ์ ํ์
- Function Module
- ๊น์ด์ฐ์ ํ์
- ์คํธ๋ญ์ฒ
- modify
- ABAP
- ์ค๋ฒ2
- ๋ฐฑ์ค
- Internal Table
- tasknumber
- ์ค๋ฒ3
- select
- structure
- dev
- ์๋ฐฉํฅํ์
- Today
- Total
CS Student’s SAP&Tech Journey๐ซ
[์๊ณ ๋ฆฌ์ฆ] ๊ทธ๋ฆฌ๋(Greedy) ์๊ณ ๋ฆฌ์ฆ์ด๋ ๋ณธ๋ฌธ
[์๊ณ ๋ฆฌ์ฆ] ๊ทธ๋ฆฌ๋(Greedy) ์๊ณ ๋ฆฌ์ฆ์ด๋
์ธํฌ๋งํฑ 2025. 5. 16. 15:301. ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ(ํ์๋ฒ)์ด๋?
๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ(ํ์๋ฒ)์ ํ์ฌ ์ํฉ์์ ์ง๊ธ ๋น์ฅ ์ข์ ๊ฒ๋ง ๊ณ ๋ฅด๋ ๋ฐฉ๋ฒ์ ์๋ฏธํฉ๋๋ค.
์ฝ๊ฒ ๋งํ๋ฉด ํ์์ค๋ฝ๊ฒ ์ต๊ณ ์ ์ ํ๋ง ์ทจํ๋ ๊ฒ์ ๋งํฉ๋๋ค.
- ์ผ๋ฐ์ ์ธ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ฌธ์ ๋ฅผ ํ๊ธฐ ์ํ ์ต์ํ์ ์์ด๋์ด๋ฅผ ๋ ์ฌ๋ฆด ์ ์๋ ๋ฅ๋ ฅ์ ์๊ตฌํฉ๋๋ค.
- ๊ทธ๋ฆฌ๋ ํด๋ฒ์ ๊ทธ ์ ๋น์ฑ ๋ถ์์ด ์ค์ํฉ๋๋ค.
๋จ์ํ ๊ฐ์ฅ ์ข์ ๋ณด์ด๋ ๊ฒ์ ๋ฐ๋ณต์ ์ผ๋ก ์ ํํด๋ ์ต์ ์ ํด๋ฅผ ๊ตฌํ ์ ์๋์ง ๊ฒํ ํฉ๋๋ค.
โ๏ธ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ํญ์ ์ต์ ์ ํด๋ฅผ ๋ณด์ฅํ์ง ์์ต๋๋ค.
- ์ผ๋ฐ์ ์ธ ์ํฉ์์ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ต์ ์ ํด๋ฅผ ๋ณด์ฅํ ์ ์์ ๋๊ฐ ๋ง์ต๋๋ค.
- ํ์ง๋ง ์ฝ๋ฉ ํ ์คํธ์์์ ๋๋ถ๋ถ์ ๊ทธ๋ฆฌ๋ ๋ฌธ์ ๋ ํ์๋ฒ์ผ๋ก ์ป์ ํด๊ฐ ์ต์ ์ ํด๊ฐ ๋๋ ์ํฉ์์, ์ด๋ฅผ ์ถ๋ก ํ ์ ์์ด์ผ ํ๋ฆฌ๋๋ก ์ถ์ ๋ฉ๋๋ค.
ํธ๋ฆฌ์์ ๊ฒฝ๋ก๋ฅผ ์ด๋ํ๋ฉด์ ๊ฐ ๋ ธ๋์ ํฉ์ด ์ต๋๊ฐ ๋๋ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด๋ด ๋๋ค.
์ค์ ๊ฐ ๋ ธ๋์ ํฉ์ด ์ต๋๊ฐ ๋๋ ๊ฒฝ์ฐ๋ ์ผ์ชฝ๊ณผ ๊ฐ์ต๋๋ค. ํ์ง๋ง, ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ์ฌ ๋งค์๊ฐ ์ต์ ์ ๊ฐ์ ์ ํํ๊ฒ ๋๋ค๋ฉด ์ค๋ฅธ์ชฝ๊ณผ ๊ฐ์ ๊ฒฝ๋ก๊ฐ ์ค์ ๋๊ณ ์ต์ ์ ํด๊ฐ ์๋๋๋ค.
์ด์ฒ๋ผ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ํญ์ ์ต์ ์ ํด๋ฅผ ๋ณด์ฅํ๋ ๊ฒ์ ์๋์ง๋ง ์๋๊ฐ ๊ต์ฅํ ๋น ๋ฅด๊ธฐ ๋๋ฌธ์ ์์ฃผ ์ฌ์ฉ๋ฉ๋๋ค. ๊ทธ๋ ๊ธฐ ๋๋ฌธ์ ํญ์ ์ต์ ์ ํด๋ฅผ ๋ณด์ฅํ๋๋ก ํน์ํ ์กฐ๊ฑด์ ๋ง์กฑ์์ผ์ค์ผ ํฉ๋๋ค.
2. <๋ฌธ์ > ๊ฑฐ์ค๋ฆ๋
๋น์ ์ ์์์ ์ ๊ณ์ฐ์ ๋์์ฃผ๋ ์ ์์ ๋๋ค. ์นด์ดํฐ์๋ ๊ฑฐ์ค๋ฆ๋์ผ๋ก ์ฌ์ฉํ 500์, 100์, 50์, 10์์ง๋ฆฌ ๋์ ์ด ๋ฌดํํ ์กด์ฌํ๋ค๊ณ ๊ฐ์ ํฉ๋๋ค. ์๋์๊ฒ ๊ฑฐ์ฌ๋ฌ ์ฃผ์ด์ผ ํ ๋์ด N์์ผ ๋ ๊ฑฐ์ฌ๋ฌ ์ฃผ์ด์ผ ํ ๋์ ์ ์ต์ ๊ฐ์๋ฅผ ๊ตฌํ์ธ์. ๋จ, ๊ฑฐ์ฌ๋ฌ ์ค์ผ ํ ๋ N์ ํญ์ 10์ ๋ฐฐ์์ ๋๋ค.
์ต์ ์ ํด๋ฅผ ๋น ๋ฅด๊ฒ ๊ตฌํ๊ธฐ ์ํด์๋ ๊ฐ์ฅ ํฐ ํํ ๋จ์๋ถํฐ ๋์ ๊ฑฐ์ฌ๋ฌ ์ฃผ๋ฉด ๋ฉ๋๋ค.
- N์์ ๊ฑฐ์ฌ๋ฌ ์ค์ผ ํ ๋, ๊ฐ์ฅ ๋จผ์ 500์์ผ๋ก ๊ฑฐ์ฌ๋ฌ ์ค ์ ์์ ๋งํผ ๊ฑฐ์ฌ๋ฌ ์ค๋๋ค.
์ดํ์ 100์, 500์, 10์์ง๋ฆฌ ๋์ ์ ์ฐจ๋ก๋๋ก ๊ฑฐ์ฌ๋ฌ ์ค ์ ์์ ๋งํผ ๊ฑฐ์ฌ๋ฌ ์ฃผ๋ฉด ๋ฉ๋๋ค. - N = 1,260์ผ ๋์ ์์๋ฅผ ํ์ธํด ๋ด ์๋ค.
STEP 0)
ํํ ๋จ์ | 500 | 100 | 50 | 10 |
์๋์ด ๋ฐ์ ๊ฐ์ | 0 | 0 | 0 | 0 |
STEP 1)
ํํ ๋จ์ | 500 | 100 | 50 | 10 |
์๋์ด ๋ฐ์ ๊ฐ์ | 2 | 0 | 0 | 0 |
STEP 2)
ํํ ๋จ์ | 500 | 100 | 50 | 10 |
์๋์ด ๋ฐ์ ๊ฐ์ | 2 | 2 | 0 | 0 |
STEP 3)
ํํ ๋จ์ | 500 | 100 | 50 | 10 |
์๋์ด ๋ฐ์ ๊ฐ์ | 2 | 2 | 1 | 0 |
STEP 4)
ํํ ๋จ์ | 500 | 100 | 50 | 10 |
์๋์ด ๋ฐ์ ๊ฐ์ | 2 | 2 | 1 | 1 |
๊ฒฐ๋ก ์ ์ผ๋ก ์๋์ ๋์ ์ ์ต์ ๊ฐ์๋ฅผ ๋ฐ๊ณ ์ต์ ์ ํด๋ฅผ ๋์ถํฉ๋๋ค.
๊ฐ์ฅ ํฐ ํํ ๋จ์๋ถํฐ ๋์ ๊ฑฐ์ฌ๋ฌ ์ฃผ๋ ๊ฒ์ด ์ต์ ์ ํด๋ฅผ ๋ณด์ฅํ๋ ์ด์ ๊ฐ ๋ฌด์์ผ๊น?
- ๊ฐ์ง๊ณ ์๋ ๋์ ์ค์์ ํฐ ๋จ์๊ฐ ํญ์ ์์ ๋จ์์ ๋ฐฐ์์ด๋ฏ๋ก ์์ ๋จ์์ ๋์ ๋ค์ ์ข ํฉํด ๋ค๋ฅธ ํด๊ฐ ๋์ฌ ์ ์๊ธฐ ๋๋ฌธ์ ๋๋ค. ๋ง์ฝ์ 800์์ ๊ฑฐ์ฌ๋ฌ ์ฃผ์ด์ผ ํ๋๋ฐ ํํ๋จ์๊ฐ 500์, 400์, 100์์ด๋ผ๋ฉด ์ต์ ์ ํด๋ฅผ ๋ณด์ฅํ ์ ์์ต๋๋ค.
๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ์์๋ ์ด์ฒ๋ผ ๋ฌธ์ ํ์ด๋ฅผ ์ํ ์ต์ํ์ ์์ด๋์ด๋ฅผ ๋ ์ฌ๋ฆฌ๊ณ ์ด๊ฒ์ด ์ ๋นํ์ง ๊ฒํ ํ ์ ์์ด์ผ ํฉ๋๋ค.
์ฝ๋ ํ์ด
n = 1260
cnt = 0
# ํฐ ๋จ์์ ํํ๋ถํฐ ์ฐจ๋ก๋๋ก ํ์ธํ๊ธฐ
arr = [500, 100, 50, 10]
for i in arr:
cnt = cnt + (n // i) # ํด๋น ํํ๋ก ๊ฑฐ์ฌ๋ฌ ์ค ์ ์๋ ๋์ ์ ๊ฐ์ ์ธ๊ธฐ
n = n % i # ๊ฑฐ์ฌ๋ฌ์ฃผ๊ณ ๋จ์ ๋๋จธ์ง
print(cnt)
์๊ฐ ๋ณต์ก๋
- ํํ์ ์ข ๋ฅ๊ฐ K๋ผ๊ณ ํ ๋, ์์ค์ฝ๋์ ์๊ฐ ๋ณต์ก๋๋ O(K)์ ๋๋ค.
- ์ด ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋๋ ๊ฑฐ์ฌ๋ฌ์ค์ผ ํ๋ ๊ธ์ก๊ณผ๋ ๋ฌด๊ดํ๋ฉฐ, ๋์ ์ ์ด ์ข ๋ฅ์๋ง ์ํฅ์ ๋ฐ์ต๋๋ค.
'์๊ณ ๋ฆฌ์ฆ > ์๊ณ ๋ฆฌ์ฆ ๊ฐ๋ ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๊ณ ๋ฆฌ์ฆ] ๊ตฌํ(Implementation) / ํ๋ ฌ, ์๋ฎฌ๋ ์ด์ ๋ฌธ์ ์ ๊ทผ ๋ฐฉ๋ฒ! (1) | 2025.05.16 |
---|---|
[์๊ณ ๋ฆฌ์ฆ] ๋๋น์ฐ์ ํ์(BFS)์ด๋ (0) | 2024.11.05 |
[์๊ณ ๋ฆฌ์ฆ] ๊น์ด์ฐ์ ํ์(DFS)์ด๋ (0) | 2024.10.31 |