Brute-Force

Brute-force

  • brute-force๋Š” ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ๊ฐ„๋‹จํ•˜๊ณ  ์‰ฌ์šด ์ ‘๊ทผ๋ฒ•

    • Just-do-it

    • force์˜ ์˜๋ฏธ๋Š” ์‚ฌ๋žŒ(์ง€๋Šฅ)๋ณด๋‹ค๋Š” ์ปดํ“จํ„ฐ์˜ force๋ฅผ ์˜๋ฏธ

  • brute-force ๋ฐฉ๋ฒ•์€ ๋Œ€๋ถ€๋ถ„์˜ ๋ฌธ์ œ์— ์ ์šฉ ๊ฐ€๋Šฅ

  • ์ƒ๋Œ€์ ์œผ๋กœ ๋น ๋ฅธ ์‹œ๊ฐ„์— ๋ฌธ์ œ ํ•ด๊ฒฐ(์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๊ณ„)์„ ํ•  ์ˆ˜ ์žˆ์Œ

  • ๋ฌธ์ œ์— ํฌํ•จ๋œ ์ž๋ฃŒ(์š”์†Œ, instance)์˜ ํฌ๊ธฐ๊ฐ€ ์ž‘๋‹ค๋ฉด ์œ ์šฉ

  • ํ•™์ˆ ์  ๋˜๋Š” ๊ต์œก์  ๋ชฉ์ ์„ ์œ„ํ•ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํšจ์œจ์„ฑ์„ ํŒ๋‹จํ•˜๊ธฐ ์œ„ํ•œ ์ฒ™๋„๋กœ ์‚ฌ์šฉ๋จ

: ์ž๋ฃŒ๋“ค์˜ list์—์„œ key๊ฐ’์„ ์ฐพ๊ธฐ ์œ„ํ•ด ์ฒซ ๋ฒˆ์งธ ์ž๋ฃŒ๋ถ€ํ„ฐ ๋น„๊ตํ•˜๋ฉด์„œ ์ง„ํ–‰

  • ๊ฒฐ๊ณผ

    • ํƒ์ƒ‰ ์„ฑ๊ณต

    • ํƒ์ƒ‰ ์‹คํŒจ

  • ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ƒ์„ฑํ•˜๊ณ  ํ…Œ์ŠคํŠธํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ˆ˜ํ–‰ ์†๋„๋Š” ๋А๋ฆฌ์ง€๋งŒ, ํ•ด๋‹ต์„ ์ฐพ์•„๋‚ด์ง€ ๋ชปํ•  ํ™•๋ฅ ์ด ์ž‘์Œ

    • ์™„์ „ ๊ฒ€์ƒ‰์€ ์ž…๋ ฅ์˜ ํฌ๊ธฐ๋ฅผ ์ž‘๊ฒŒ ํ•ด์„œ ๊ฐ„ํŽธํ•˜๊ณ  ๋น ๋ฅด๊ฒŒ ๋‹ต์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•จ

  • ์ด๋ฅผ ๊ธฐ๋ฐ˜์œผ๋กœ ๊ทธ๋ฆฌ๋”” ๊ธฐ๋ฒ• ์ด๋‚˜ ๋™์  ๊ณ„ํš๋ฒ•์„ ์ด์šฉํ•ด์„œ ํšจ์œจ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ฐพ์„ ์ˆ˜ ์žˆ์Œ

  • ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๋“ฑ์—์„œ ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ, ์šฐ์„  ์™„์  ๊ฒ€์ƒ‰์œผ๋กœ ์ ‘๊ทผํ•˜์—ฌ ํ•ด๋‹ต์„ ๋„์ถœํ•œ ํ›„, ์„ฑ๋Šฅ ๊ฐœ์„ ์„ ์œ„ํ•ด ๋‹ค๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜๊ณ  ํ•ด๋‹ต์„ ํ™•์ธํ•˜๋Š” ๊ฒƒ์ด ๋ฐ”๋žŒ์งํ•จ

Baby-gin Game

์„ค๋ช…

  • 0~9 ์‚ฌ์ด์˜ ์ˆซ์ž ์นด๋“œ์—์„œ ์ž„์˜์˜ ์นด๋“œ 6์žฅ์„ ๋ฝ‘์•˜์„ ๋•Œ, 3์žฅ์˜ ์นด๋“œ๊ฐ€ ์—ฐ์†์ ์ธ ๋ฒˆํ˜ธ๋ฅผ ๊ฐ–๋Š” ๊ฒฝ์šฐ๋ฅผ run์ด๋ผ ํ•˜๊ณ , 3์žฅ์˜ ์นด๋“œ๊ฐ€ ๋™์ผํ•œ ๋ฒˆํ˜ธ๋ฅผ ๊ฐ–๋Š” ๊ฒฝ์šฐ๋ฅผ triplet์ด๋ผ๊ณ  ํ•œ๋‹ค.

  • ๊ทธ๋ฆฌ๊ณ , 6์žฅ์˜ ์นด๋“œ๊ฐ€ run๊ณผ triplet์œผ๋กœ๋งŒ ๊ตฌ์„ฑ๋œ ๊ฒฝ์šฐ๋ฅผ baby-gin ์œผ๋กœ ๋ถ€๋ฅธ๋‹ค

  • 6์ž๋ฆฌ์˜ ์ˆซ์ž๋ฅผ ์ž…๋ ฅ ๋ฐ›์•„ baby-gin ์—ฌ๋ถ€๋ฅผ ํŒ๋‹จํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜๋ผ.

์™„์ „ ๊ฒ€์ƒ‰์„ ํ†ตํ•œ Baby-gin ์ ‘๊ทผ

  1. ๊ณ ๋ คํ•  ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜ ์ƒ์„ฑํ•˜๊ธฐ

    • 6๊ฐœ์˜ ์ˆซ์ž๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ์ˆซ์ž ๋‚˜์—ด (์ค‘๋ณต ํฌํ•จ)

  2. ํ•ด๋‹ต ํ…Œ์ŠคํŠธ ํ•˜๊ธฐ

    • ์•ž์˜ 3์ž๋ฆฌ์™€ ๋’ค์˜ 3์ž๋ฆฌ๋ฅผ ์ž˜๋ผ, run๊ณผ triplet ์—ฌ๋ถ€๋ฅผ ํ…Œ์ŠคํŠธํ•˜๊ณ  ์ตœ์ข…์ ์œผ๋กœ baby-gin ํŒ๋‹จ

์™„์ „ ๊ฒ€์ƒ‰

  • ๋งŽ์€ ์ข…๋ฅ˜์˜ ๋ฌธ์ œ๋“ค์ด ํŠน์ • ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” ๊ฒฝ์šฐ๋‚˜ ์š”์†Œ๋ฅผ ์ฐพ๋Š” ๊ฒƒ

  • ์ „ํ˜•์ ์œผ๋กœ ์ˆœ์—ด(permutation), ์กฐํ•ฉ(combination), ๊ทธ๋ฆฌ๊ณ  ๋ถ€๋ถ„ ์ง‘ํ•ฉ(subsets)๊ณผ ๊ฐ™์€ ์กฐํ•ฉ์  ๋ฌธ์ œ๋“ค (Combinatorial Problems) ๊ณผ ์—ฐ๊ด€๋จ

  • ์™„์ „ ๊ฒ€์ƒ‰์€ ์กฐํ•ฉ์  ๋ฌธ์ œ์— ๋Œ€ํ•œ brute-force ๋ฐฉ๋ฒ•์ด๋‹ค

์ˆœ์—ด (Permutation)

  • ์„œ๋กœ ๋‹ค๋ฅธ ๊ฒƒ๋“ค ์ค‘ ๋ช‡ ๊ฐœ๋ฅผ ๋ฝ‘์•„์„œ ํ•œ ์ค„๋กœ ๋‚˜์—ดํ•˜๋Š” ๊ฒƒ

  • ์„œ๋กœ ๋‹ค๋ฅธ n๊ฐœ ์ค‘ r๊ฐœ๋ฅผ ํƒํ•˜๋Š” ์ˆœ์—ด์€ nPr

  • ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์‹์ด ์„ฑ๋ฆฝํ•จ

    • nPr = n x (n-1) x (n-2) x ... x (n-r+1)

  • nPn = n! ์ด๋ผ๊ณ  ํ‘œ๊ธฐํ•˜๋ฉฐ, Factorial ์ด๋ผ ๋ถ€๋ฆ„

    • n! = n x (n-1) x (n-2) x ... 2x1

  • ์ˆœ์—ด์€ ์ˆœ์„œํ™”๋œ ์š”์†Œ๋“ค์˜ ์ง‘ํ•ฉ์—์„œ ์ตœ์„ ์˜ ๋ฐฉ๋ฒ•์„ ์ฐพ๋Š” ๊ฒƒ๊ณผ ๊ด€๋ จ ์žˆ์Œ

    • ex) TSP (Traveling Salesman Problem)

  • N ๊ฐœ์˜ ์š”์†Œ๋“ค์— ๋Œ€ํ•ด์„œ n!๊ฐœ์˜ ์ˆœ์—ด๋“ค์ด ์กด์žฌ

    • n >12 ์ธ ๊ฒฝ์šฐ, ์‹œ๊ฐ„ ๋ณต์žก๋„ ํญ๋ฐœ!!! (์ง€์ˆ˜์Šน์œผ๋กœ ์˜ฌ๋ผ๊ฐ€๊ธฐ ๋•Œ๋ฌธ์—...)

1. ์žฌ๊ท€ ํ˜ธ์ถœ์„ ํ†ตํ•œ ์ˆœ์—ด ์ƒ์„ฑ - ๊ตํ™˜์„ ํ†ตํ•ด ์ƒ์„ฑ

def perm(n,k):
    if k == n:
        #do something
 else:
        for i in range(k, n):
            swap(k,i)#swap!
            perm(n, k+1)
            swap(k,i) #๋‹ค์‹œ ์›์ƒ ๋ณต๊ท€

Subsets (๋ถ€๋ถ„ ์ง‘ํ•ฉ)

  • ์ง‘ํ•ฉ์— ํฌํ•จ๋œ ์›์†Œ๋“ค์„ ์„ ํƒํ•˜๋Š” ๊ฒƒ

  • ๋‹ค์ˆ˜์˜ ์ค‘์š” ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์ด ์›์†Œ๋“ค์˜ ๊ทธ๋ฃน์—์„œ ์ตœ์ ์˜ ๋ถ€๋ถ„ ์ง‘ํ•ฉ์„ ์ฐพ๋Š” ๊ฒƒ์ž„

    • ex) ๋ฐฐ๋‚ญ ์ง์‹ธ๊ธฐ (knapsack)

  • N๊ฐœ์˜ ์›์†Œ๋ฅผ ํฌํ•จํ•œ ์ง‘ํ•ฉ

    • ์ž๊ธฐ ์ž์‹ ๊ณผ ๊ณต์ง‘ํ•ฉ ํฌํ•จํ•œ ๋ชจ๋“  ๋ฉฑ ์ง‘ํ•ฉ(power set)์˜ ๊ฐœ์ˆ˜๋Š” 2^n๊ฐœ

    • ์›์†Œ์˜ ์ˆ˜๊ฐ€ ์ฆ๊ฐ€ํ•˜๋ฉด ๋ถ€๋ถ„์ง‘ํ•ฉ์˜ ๊ฐœ์ˆ˜๋Š” ์ง€์ˆ˜์ ์œผ๋กœ ์ฆ๊ฐ€

1. ๋‹จ์ˆœํ•˜๊ฒŒ ๋ชจ๋“  ๋ถ€๋ถ„ ์ง‘ํ•ฉ ์ƒ์„ฑํ•˜๋Š” ๋ฐฉ๋ฒ•

  • 4๊ฐœ ์›์†Œ๋ฅผ ํฌํ•จํ•œ ์ง‘ํ•ฉ์— ๋Œ€ํ•œ power set ๊ตฌํ•˜๊ธฐ

2. Binary Counting

  • ์›์†Œ ์ˆ˜์— ํ•ด๋‹นํ•˜๋Š” N๊ฐœ์˜ ๋น„ํŠธ์—ด์„ ์ด์šฉ

  • n๋ฒˆ์งธ ๋น„ํŠธ๊ฐ’์ด 1์ด๋ฉด n๋ฒˆ์งธ ์›์†Œ๊ฐ€ ํฌํ•จ๋˜์—ˆ์Œ์„ ์˜๋ฏธ

Combination (์กฐํ•ฉ)

์„œ๋กœ ๋‹ค๋ฅธ n๊ฐœ์˜ ์›์†Œ ์ค‘ r๊ฐœ๋ฅผ ์ˆœ์„œ ์—†์ด ๊ณจ๋ผ๋‚ธ ๊ฒƒ

  • ์กฐํ•ฉ์˜ ์ˆ˜์‹

    • nCr = n-1 C r-1 +n-1 C r

    • nC0 = 1

Last updated

Was this helpful?