[6]알고리즘스터디 - 섹션6_3주차 스터디

파이썬 알고리즘 문제풀이 스터디 - 알까기 _ 섹션 6

 

티스토리 마크다운이 이상해서 깃허브 주소도 올린다. 

 

https://github.com/dumi33/TIL_TodayILearn/blob/main/220223/%EC%84%B9%EC%85%986.md

문제 1 - 재귀함수를 이용한 이진수 출력

• <내가 만든 코드>

def dfs(x) :
    if x >0:
        tmp = x//2
        dfs(tmp)
        print(x%2,end = '')
if __name__ == "__main__" :
    n = int(input())
    dfs(n)

• <강사님이 만드신 코드>

def dfs(x) :
    if x == 0 :
        return 
    else :
        dfs(x//2)
        print(x%2,end = '')


if __name__ == "__main__" :
    n = int(input())
    dfs(n)

문제 2 - 이진트리 순회

• 전위순회

def dfs(x) :  
if x > 7 :  
return  
else :  
print(x,end=' ')  
dfs(x_2) # 왼쪽 자식  
dfs(x_2+1) # 오른쪽 자식

if **name** == "**main**" :  
dfs(1)

문제 3 - 부분집합 구하기

def dfs(v) :
    if v == n+1 : # 종료지점
        for i in range(1,n+1) :
            if ch[i] == 1 :
                print(i, end = ' ')
        print()
    else :
        ch[v] = 1  # 왼쪽으로 # 사용
        dfs(v+1)
        ch[v] = 0 # 오른쪽으로 # 사용 X 
        dfs(v+1)


if __name__ == "__main__" :
    n = int(input())
    ch= [0] *(n+1)
    dfs(1)

문제 4 - 합이 같은 부분집합

def dfs(L,sum) :# L : level , sum : 지금까지의 합 
    if sum > total // 2 :
        return 
    if L == n : # 종료지점
        if sum == (total-sum) :
            print("YES")
            sys.exit(0)
    else :
        dfs(L+1, sum + nums[L])
        dfs(L+1, sum)
if __name__ == "__main__" :
    n = int(input())
    nums = list(map(int,input().split()))
    total = sum(nums)
    dfs(0,0)
    print("NO")

• 종료하는 코드 sys.exit(0)

 

 

 

 

문제 5 - 바둑이 승차 - Cut Edge Tech

def dfs(L,sum, tsum) :# level 과 지금까지의 합 
    global ans
    if sum > c :
        return 
    #  cut edge tech 
    if sum + (total - tsum) < ans : # tsum 은 지금가지 지나온 값들 
        return # 전부 다 더해봤자 ans보다 작으면 하지 않음 
    if L == n : # 종료지점
        ans = max(ans,sum)
    else :
        dfs(L+1, sum + nums[L],tsum + nums[L])
        dfs(L+1, sum, tsum + nums[L])

if __name__ == "__main__" :
    ans = 0
    c, n = map(int, input().split())
    nums = []
    for i in range(n) :
        nums.append(int(input()))
    total = sum(nums)
    dfs(0,0,0)
    print(ans)

 

 

 

 

 

문제 6 - 중복순열 구하기

def dfs(L) :# level 과 지금까지의 합 
    global cnt
    if L == m : # 종료지점
        cnt+=1
        for i in res :
            print(i, end = ' ')
        print() # 줄 바꿈 
    else :
        for i in range(1,n+1) :
            res[L] = i
            dfs(L+1)
if __name__ == "__main__" :
    cnt = 0
    n, m  = map(int, input().split())
    res = [0] *(m)
    dfs(0)
    print(cnt)

문제 7 - 동전교환

def dfs(L,sum) :# level 과 지금까지의 합 # level : 사용한 동전의 개수 
    global cnt
    if sum > m or L > cnt: 
        return 
    if sum == m :
        cnt =  min(cnt,L)
    else :
        for i in range(n) :
            dfs(L+1,sum+nums[i])

if __name__ == "__main__" :
    cnt = sys.maxsize
    n = int(input())
    nums = list(map(int,input().split()))
    m = int(input())
    nums.sort(reverse=True) # 내림차순으로 # 더 빠르게 구하기 위해 (큰 수부터 사용하므로)
    dfs(0,0)
    print(cnt)

• level을 사용한 동전의 개수로 사용하는 것이 신기

문제 8 - 순열 구하기

def dfs(L) :# level
    global cnt 
    if L == m :
        cnt +=1 
        for i in res :
            print(i, end = ' ')
        print() # 줄 바꿈
    else :
        for i in range(1,n+1) :
            if ch[i] == 0 : # 적용이 되지않은 수 일 때 
                ch[i] = 1 #  사용
                res[L] = i
                dfs(L+1)
                ch[i] = 0 # 비사용 
if __name__ == "__main__" :
    n,m  = map(int,input().split()) 
    ch = [0] * (n+1)
    res = [0] * (m)
    cnt =0 
    dfs(0)
    print(cnt)

문제 9 - 수열 추측하기

def dfs(L,sum) :# level
    if L==n and sum == f :
        for x in p :
            print(x,end=' ')
        sys.exit(0)
    else :
        for i in range(1,n+1) :
            if ch[i] == 0 : # 중복없애기
                ch[i] = 1
                p[L] = i
                dfs(L+1, sum+(p[L]*b[L]))
                ch[i] = 0

if __name__ == "__main__" :
    n,f  = map(int,input().split()) 
    p = [0]*n # 숫자의 순서 
    b = [1] *n # 이항계수
    ch = [0]*(n+1)
    for i in range(1,n) :
        b[i] = b[i-1]*(n-i)//i
    dfs(0,0)

문제 10 - 조합 구하기

def dfs(L,s) :# level, start
    global cnt
    if L==m :
        cnt+=1
        for x in res :
            print(x,end=' ')
        print()
    else :
        for i in range(s,n+1) :
            res[L] = i
            dfs(L+1,i+1)

if __name__ == "__main__" :
    n,m  = map(int,input().split()) 
    res = [0] *(m)
    cnt = 0
    dfs(0,1)
    print(cnt)

문제 11 - 수들의 조합

• 내가 푼 풀이
• def dfs(L,s) :# level, start global cnt if L==k : if (sum(res)%m)==0: cnt+=1 else : for i in range(s,n) : res[L] = nums[i] dfs(L+1,i+1)

if name == "main" :
n,k = map(int,input().split())
nums = list(map(int,input().split()))
m = int(input())
res = [0] *(k)
cnt = 0
dfs(0,0) # 0level, 0부터 시작
print(cnt)

<br><br>
### 문제 12 - (수열 추측하기 라이브러리를 이용) 


```py

import itertools as it

if __name__ == "__main__" :
    n,f  = map(int,input().split())
    cnt = 0
    b = [1] * n
    for i in range(1,n) :
        b[i] = b[i-1] * (n-i) // i 
    a = list(range(1,n+1))
    for tmp in it.permutations(a) : # 모든 조합 
        sum =0 
        for L, x in enumerate(tmp) :
            sum += (b[L] * x )
        if sum == f :
            for x in tmp :
                print(x, end= ' ' )
            break  # for문 break

- itertools의 permutation을 이용해 순열 구함 

- 라이브러리에 너무 의존하지 않기 

문제 13 - <수들의 조합>_라이브러리를 이용한 조합

import itertools as it

if __name__ == "__main__" :
    n,k  = map(int,input().split())
    a = list(map(int,input().split()))
    m = int(input())
    cnt = 0
    for x in it.combinations(a,k) :
        if sum(x) % m == 0 :
            cnt += 1
    print(cnt)

문제 14 - 인접행렬(그래프 dfs)

if __name__ == "__main__" :
    n,m = map(int,input().split())
    graph = [[0] * (n+1)  for _ in range(n+1)] # 이차원 배열 


    for _ in range(m) :
        a,b,c = map(int,input().split())
        graph[a][b] = c
    for i in range(1,n+1) :
        for j in range(1,n+1) :
            print(graph[i][j],end = ' ')
        print()

문제 15 - 경로탐색(그래프 dfs)_

• (경로 출력코드 포함)
• def dfs(v) : # v는 현재 노드 global cnt if v == n : # n에 도착 cnt += 1 for x in path : print(x, end= ' ') print() else : for i in range(1, n+1 ) : # n개의 가지 뻗기 if graph[v][i] == 1 and ch[i] == 0 : ch[i] = 1 path.append(i) dfs(i) path.pop() ch[i] =0

if name == "main" :
n,m = map(int,input().split())
graph = [[0] * (n+1) for _ in range(n+1)] # 이차원 배열
ch = [0]*(n+1)

for _ in range(m)  :
    a,b= map(int,input().split())
    graph[a][b] = 1
cnt =0 
path = []
path.append(1)
ch[1] = 1 # 1번 노드 방문 
dfs(1) # 1에서 시작 
print(cnt)

<br>

- 경로 출력 미포함

```py
def dfs(v) : # v는 현재 노드 
    global cnt
    if v == n : # n에 도착 
        cnt += 1
    else :
        for i in range(1, n+1 ) : # n개의 가지 뻗기
            if graph[v][i] == 1 and ch[i] == 0 : # 갈수있고 안가본 노드로 
                ch[i] = 1
                dfs(i) 
                ch[i] =0 

if __name__ == "__main__" :
    n,m = map(int,input().split())
    graph = [[0] * (n+1)  for _ in range(n+1)] # 이차원 배열 
    ch = [0]*(n+1)

    for _ in range(m)  :
        a,b= map(int,input().split())
        graph[a][b] = 1
    cnt =0 
    ch[1] = 1 # 1번 노드 방문 
    dfs(1) # 1에서 시작 
    print(cnt)