99클럽 코테 스터디 21일차 TIL : 그리디, DFS 문제 풀이

 

• 문제

체육복 - 그리디 

 

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

 

 

 

 

• 코드

def solution(n, lost, reserve):
    # 도난당한 학생이 여벌 체육복을 가진 경우를 먼저 처리
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)

    # 체육복을 빌려줄 수 있는 경우 처리
    for student in sorted(reserve_set):
        if student - 1 in lost_set:
            lost_set.remove(student - 1)
        elif student + 1 in lost_set:
            lost_set.remove(student + 1)

    # 체육수업을 들을 수 있는 학생 수
    return n - len(lost_set)

 

 

• 설명 및 개념

집합 자료형

• 중복을 허용하지 않는다
• 순서가 없다
• 집합은 리스트 혹은 문자열을 이용해서 초기화할 수 있다
  • 이 때 set()함수를 이용한다
• 중괄호 안에 각 원소를 콤마를 기준으로 구분하여 삽입함으로써 초기화할 수 있다
• 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다

💡 lost_set = set(lost) - set(reserve) : 차집합을 통해서 체육복을 도난당한 학생들 중 여벌 체육복이 없는 학생들의 집합을 만든다 

💡 reserve_set= set(reserve)- set(lost) : 차집합을 통해서 여벌 체육복을 가지고있어 빌려줄 수 있는 학생들의 집합을 만든다 

 

 

 

---

• 문제

중복순열 구하기 - DFS

 

 

 

• 상태트리가 N 가닥이라고 생각하면 된다 

 

 

• 코드

 

def DFS(L):
  global cnt
  if L==m:
    for j in range(m):
      print(res[j], end=' ')
    print()
    cnt+=1

  else:
    for i in range(1,n+1):
      res[L]=i
      DFS(L+1)
    



n,m = map(int,input().split())
cnt=0
res=[0]*m
DFS(0)
print(cnt)

 

 

 

 

 

 

 

---

 

 

• 문제

동전교환 - DFS

 

 

 

 

 

•  코드 

def DFS(L,sum):
  global res
  if sum >m:
    return
  if L> res:
    return
  if sum==m:
    if L<res:
      res=L
  else:
    for i in range(n):
      DFS(L+1,sum+a[i])
      


n=int(input())
a=list(map(int,input().split()))
m=int(input())
res=217000000
DFS(0,0)
print(res)