๊ด€๋ฆฌ ๋ฉ”๋‰ด

CS Student’s SAP&Tech Journey๐Ÿ’ซ

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๊ทธ๋ฆฌ๋””(Greedy) ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€ ๋ณธ๋ฌธ

์•Œ๊ณ ๋ฆฌ์ฆ˜/์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋…

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๊ทธ๋ฆฌ๋””(Greedy) ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€

์ธํฌ๋งˆํ‹ฑ 2025. 5. 16. 15:30

1. ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜(ํƒ์š•๋ฒ•)์ด๋ž€?

๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜(ํƒ์š•๋ฒ•)์€ ํ˜„์žฌ ์ƒํ™ฉ์—์„œ ์ง€๊ธˆ ๋‹น์žฅ ์ข‹์€ ๊ฒƒ๋งŒ ๊ณ ๋ฅด๋Š” ๋ฐฉ๋ฒ•์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.
์‰ฝ๊ฒŒ ๋งํ•˜๋ฉด ํƒ์š•์Šค๋Ÿฝ๊ฒŒ ์ตœ๊ณ ์˜ ์„ ํƒ๋งŒ ์ทจํ•˜๋Š” ๊ฒƒ์„ ๋งํ•ฉ๋‹ˆ๋‹ค.

  • ์ผ๋ฐ˜์ ์ธ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•œ ์ตœ์†Œํ•œ์˜ ์•„์ด๋””์–ด๋ฅผ ๋– ์˜ฌ๋ฆด ์ˆ˜ ์žˆ๋Š” ๋Šฅ๋ ฅ์„ ์š”๊ตฌํ•ฉ๋‹ˆ๋‹ค.
  • ๊ทธ๋ฆฌ๋”” ํ•ด๋ฒ•์€ ๊ทธ ์ •๋‹น์„ฑ ๋ถ„์„์ด ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค.
    ๋‹จ์ˆœํžˆ ๊ฐ€์žฅ ์ข‹์•„ ๋ณด์ด๋Š” ๊ฒƒ์„ ๋ฐ˜๋ณต์ ์œผ๋กœ ์„ ํƒํ•ด๋„ ์ตœ์ ์˜ ํ•ด๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ๊ฒ€ํ† ํ•ฉ๋‹ˆ๋‹ค.

โœ”๏ธ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ•ญ์ƒ ์ตœ์ ์˜ ํ•ด๋ฅผ ๋ณด์žฅํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

  • ์ผ๋ฐ˜์ ์ธ ์ƒํ™ฉ์—์„œ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ตœ์ ์˜ ํ•ด๋ฅผ ๋ณด์žฅํ•  ์ˆ˜ ์—†์„ ๋•Œ๊ฐ€ ๋งŽ์Šต๋‹ˆ๋‹ค.
  • ํ•˜์ง€๋งŒ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์—์„œ์˜ ๋Œ€๋ถ€๋ถ„์˜ ๊ทธ๋ฆฌ๋”” ๋ฌธ์ œ๋Š” ํƒ์š•๋ฒ•์œผ๋กœ ์–ป์€ ํ•ด๊ฐ€ ์ตœ์ ์˜ ํ•ด๊ฐ€ ๋˜๋Š” ์ƒํ™ฉ์—์„œ, ์ด๋ฅผ ์ถ”๋ก ํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ’€๋ฆฌ๋„๋ก ์ถœ์ œ๋ฉ๋‹ˆ๋‹ค.

 

ํŠธ๋ฆฌ์—์„œ ๊ฒฝ๋กœ๋ฅผ ์ด๋™ํ•˜๋ฉด์„œ ๊ฐ ๋…ธ๋“œ์˜ ํ•ฉ์ด ์ตœ๋Œ€๊ฐ€ ๋˜๋Š” ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐํ•ด๋ด…๋‹ˆ๋‹ค.

์‹ค์ œ ์ตœ์ ์˜ ํ•ด / ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ•ด

์‹ค์ œ ๊ฐ ๋…ธ๋“œ์˜ ํ•ฉ์ด ์ตœ๋Œ€๊ฐ€ ๋˜๋Š” ๊ฒฝ์šฐ๋Š” ์™ผ์ชฝ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ, ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜์—ฌ ๋งค์ˆœ๊ฐ„ ์ตœ์ ์˜ ๊ฐ’์„ ์„ ํƒํ•˜๊ฒŒ ๋œ๋‹ค๋ฉด ์˜ค๋ฅธ์ชฝ๊ณผ ๊ฐ™์€ ๊ฒฝ๋กœ๊ฐ€ ์„ค์ •๋˜๊ณ  ์ตœ์ ์˜ ํ•ด๊ฐ€ ์•„๋‹™๋‹ˆ๋‹ค.

์ด์ฒ˜๋Ÿผ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ•ญ์ƒ ์ตœ์ ์˜ ํ•ด๋ฅผ ๋ณด์žฅํ•˜๋Š” ๊ฒƒ์€ ์•„๋‹ˆ์ง€๋งŒ ์†๋„๊ฐ€ ๊ต‰์žฅํžˆ ๋น ๋ฅด๊ธฐ ๋•Œ๋ฌธ์— ์ž์ฃผ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค. ๊ทธ๋ ‡๊ธฐ ๋•Œ๋ฌธ์— ํ•ญ์ƒ ์ตœ์ ์˜ ํ•ด๋ฅผ ๋ณด์žฅํ•˜๋„๋ก ํŠน์ˆ˜ํ•œ ์กฐ๊ฑด์„ ๋งŒ์กฑ์‹œ์ผœ์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค.

 

 

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)์ž…๋‹ˆ๋‹ค.
  • ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ๊ฑฐ์Šฌ๋Ÿฌ์ค˜์•ผ ํ•˜๋Š” ๊ธˆ์•ก๊ณผ๋Š” ๋ฌด๊ด€ํ•˜๋ฉฐ, ๋™์ „์˜ ์ด ์ข…๋ฅ˜์—๋งŒ ์˜ํ–ฅ์„ ๋ฐ›์Šต๋‹ˆ๋‹ค.