๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
SW์‚ฌ๊ด€ํ•™๊ต ์ •๊ธ€/๊ฐœ๋ฐœ์ผ์ง€ - TIL

[Week01] ์•Œ๊ณ ๋ฆฌ์ฆ˜ - ์žฌ๊ท€ํ•จ์ˆ˜

by young-ji 2022. 4. 7.

[Week01] ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ‚ค์›Œ๋“œ - ์ •์ˆ˜๋ก , ๋ฐฐ์—ด, ๋ฌธ์ž์—ด, ์žฌ๊ท€ํ•จ์ˆ˜, ์ •๋ ฌ, ์™„์ „ํƒ์ƒ‰, ์‹œ๊ฐ„๋ณต์žก๋„

 

์žฌ๊ท€ํ•จ์ˆ˜

  • ์ž‘์€ ๋ฌธ์ œ์˜ ํ•ด๊ฒฐ๋ฒ•์„ ์‚ฌ์šฉํ•ด์„œ ๋” ํฐ ๋ฌธ์ œ๋ฅผ ํ‘ผ๋‹ค
  • ์ ˆ์ฐจ์  ์ง€ํ–ฅ์  ์‚ฌ๊ณ ๋ฅผ ๋ฒ„๋ฆฌ๊ณ  ์ˆ˜ํ•™์  ๊ท€๋‚ฉ๋ฐฉ์‹์œผ๋กœ ์ƒ๊ฐํ•˜๊ธฐ 
  • ์ ํ™”์‹(๋‘๊ฐœ์˜ ํ•ญ ์‚ฌ์ด์— ์„ฑ๋ฆฝํ•˜๋Š” ๊ด€๊ณ„)๊ณผ ์ดˆํ•ญ ๊ตฌํ•˜๊ธฐ
  • loop(๋ฐ˜๋ณต๋ฌธ)์™€ recursion(์žฌ๊ท€)์€ ์„œ๋กœ ๋ณ€ํ™˜์ด ๊ฐ€๋Šฅํ•˜๋‹ค

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

 

๊ตฌํ˜„๋ฐฉ๋ฒ•

1. ๋ฌธ์ œ์˜ ์ •์˜๋ฅผ ์ •ํ™•ํ•˜๊ฒŒ ํ‘œ๊ธฐํ•œ๋‹ค. (์„ ์–ธํ˜• ํ”„๋กœ๊ทธ๋ž˜๋ฐ*)2. ์ข…๋ฃŒ ์กฐ๊ฑด+ ์ปฌ์Šคํƒ : ํ˜ธ์ถœ์˜ ํ๋ฆ„์„ ์ €์žฅํ•ด์„œ ์ด๋ฒˆ ์ฒ˜๋ฆฌ๊ฐ€ ๋๋‚˜๋ฉด ๋Œ์•„๊ฐˆ ๊ณณ์„ ๊ธฐ์–ตํ•˜๋Š” ์žฅ์†Œ.

               ํ˜ธ์ถœ์˜ ํ๋ฆ„์„ ๋”ฐ๋ผ๊ฐˆ์ค„์•Œ์•„์•ผํ•œ๋‹ค. (์ปฌ์Šคํƒ์ด ์–ด๋–ป๊ฒŒ ์Œ“์ด๊ณ  ์ค„์–ด๋“œ๋Š” ์ง€)

 

 

โœ… ์ˆœ์—ด๊ณผ ์กฐํ•ฉ

 

์ˆœ์—ด - ์„œ๋กœ ๋‹ค๋ฅธ n ๊ฐœ ์ค‘ r ๊ฐœ๋ฅผ ๊ณจ๋ผ ์ˆœ์„œ๋ฅผ ์ •ํ•ด ๋‚˜์—ดํ•˜๋Š” ๊ฐ€์ง“์ˆ˜

def permutation(arr, n):
    result = []
    if n == 0:
        return [[]]
    for i in range(len(arr)):
        elem = arr[i]
        for rest in permutation(arr[:i] + arr[i+1:], n - 1):
            result.append([elem] + rest)
    return result

print(permutation([0,1,2,3], 2))

 

์กฐํ•ฉ - ์„œ๋กœ ๋‹ค๋ฅธ n๊ฐœ ์ค‘ r๊ฐœ๋ฅผ ์ทจํ•˜์—ฌ ์กฐ๋ฅผ ๋งŒ๋“ ๋‹ค. 

def combination(arr, n):
    result = []
    if n == 0:
        return [[]]
    for i in range(len(arr)):
        elem = arr[i]
        for rest in combination(arr[i + 1:], n - 1):
            result.append([elem] + rest)
    return result

print(combination([0,1,2,3], 2))

 

 

 

โœ… ๋ฐฑํŠธ๋ž˜ํ‚น : ํ˜„์žฌ ์ƒํƒœ์—์„œ ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ํ›„๋ณด๊ตฐ์„ ๋”ฐ๋ผ ๋“ค์–ด๊ฐ€๋ฉฐ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜

 

DFS์˜ ์ผ์ข…์ธ ๋ฐฑํŠธ๋ž˜ํ‚น, ๋ฌธ์ œ ์ œํ•œ์ด ํฌ์ง€์•Š์„ ๊ฒฝ์šฐ ์‚ฌ์šฉ๊ฐ€๋Šฅํ•˜๋‹ค.

 

๋ฐฑํŠธ๋ž˜ํ‚น ์—ฐ์Šต ๋ฌธ์ œ - ๋ฐฑ์ค€ 1569(N๊ณผ M)

import sys

x,y = map(int,sys.stdin.readline().split())

arr = [0] * y #์ˆ˜์—ด ์กฐํ•ฉ์„ ๋‹ด๋Š” ๋ฆฌ์ŠคํŠธ
isused = [False] * (x+1) #ํ•ด๋‹น ์ˆ˜๊ฐ€ ์‚ฌ์šฉ๋๋Š”์ง€ ํ™•์ธ - ์ธ๋ฑ์Šค ๊ฐ’์ด ํ•ด๋‹น ์ˆ˜

def back(n) :
    if n == y :
        print(' '.join(map(str,arr)))
    else :
        for i in range(1,x+1) :
            if isused[i] == False :
                    arr[n] = i
                    isused[i] = True
                    back(n+1)
                    isused[i] = False

back(0)

์ข€ ๋” ๊น”๋”ํ•˜๊ฒŒ ํ‘œํ˜„

์ด ๊ฒฝ์šฐ isused list๊ฐ€ ๋”ฐ๋กœ ์—†์–ด ์ค‘๋ณต ๊ฐ’์„ ํ—ˆ์šฉํ•˜๋Š” ๊ฒฝ์šฐ ์ด์Šˆ๊ฐ€ ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ๋‹ค.

n,m = map(int,input().split())
 
arr = []
 
def back():
    if len(arr)==m:
        print(' '.join(map(str,arr)))
        return
    
    for i in range(1,n+1):
        if i not in arr: #์ค‘๋ณต๊ฐ’์„ ํ—ˆ์šฉํ•  ๊ฒฝ์šฐ ์กฐ๊ฑด๋ฌธ์— ๊ฑธ๋ฆฌ์ง€์•Š์Œ
            arr.append(i)
            back()
            arr.pop()
 
back()

 

 

 

์žฌ๊ท€ํ•จ์ˆ˜๋Š” ๋’ค์— ๋‚˜์˜ค๋Š” ๋‹ค์–‘ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฐฉ์‹์— ์“ฐ์ด๊ธฐ ๋•Œ๋ฌธ์— ๊ผญ ์ตํ˜€๋‘๊ธธ ๋ฐ”๋ž€๋‹ค...!

 

๋Œ“๊ธ€