codes_python

주요 측정 항목

• List, Stack - [ ].append()
• Queue(Deque) - deque().append()
• Binary Search (이진 검색)
• Greedy
• BFS, DFS
• Flood Fill

[ 2개의 주사위가 나올수 있는 모든 경우의 수 인쇄]

[1] for 2개로 할 경우

for i in range(1,7):
    for j in range(1, 7):
    print(i, j)

---

[2] 중복순열구조

sol = [0]*4
chk = [0]*7
def DFS(n):
    if n>2:
        print(sol)
        return

for i in range(1, 7):
    sol[n]=i
    DFS(n+1)

DFS(1)

---

[3] 순열구조(중복배제)

sol = [0]*4
chk = [0]*7
def DFS(n):
    if n>2:
        print(sol)
        return


for i in range(1, 7):
    if chk[i]==1: continue
    chk[i]=1
    sol[n]=i
    DFS(n+1)
    chk[i]=0

DFS(1)

---

[4] 조합구조

sol = [0]*4
chk = [0]*7
def DFS(n, start):
    if n>2:
        print(sol)
        return

    for i in range(start, 7):
        sol[n]=i
        DFS(n+1, i+1) # i 면 중복 조합

DFS(1, 1)

---

[선택유무에 따른 이중재귀로 조합구조 ]

[1] 3개의 정수를 고르는 모든 경우의 수

arr = [3, 4, 7]
box = [0]*3

def DFS(n):
    if n>=3:
        print(box)
        return
    box[n]=arr[n]
    DFS(n+1)
    box[n]=0
    DFS(n+1)

DFS(0)    

---

[2] 정수중 일부 합산하여 7이 되는 모든 경우의 수

arr = [3, 4, 7, 10]
box = [0]*4

def DFS(n, tot):
    if tot>7: return #가지치기
    if n>=4:
        if tot==7: print(box)
        return
    box[n]=arr[n]
    DFS(n+1, tot+arr[n])
    box[n]=0
    DFS(n+1, tot)

DFS(0, 0) 

---

[ 백준 OJ (www.acmicpc.net)에서 풀어볼 만한 문제 ]

1. DFS

• N과 M 시리즈 (https://www.acmicpc.net/workbook/view/2052) - DFS에 자신이 없으시다면 꼭 풀어보세요. 다양한 경우의 수 모델에 대해 DFS코드를 작성하는 방법을 공부 할 수 있습니다.
• 6603 로또 (실버2)
• 10819 차이를 최대로(실버2)
• 16922 로마 숫자 만들기 (실버3)
• 10971 외판원 순회(실버2)
• 2529 부등호 (실버1)
• 14888 스타트와 링크 (실버1)
• 2529 부등호 (실버1)
• 2580 스도쿠 (골드4)
• 1759 암호 만들기(골드5)
• 6987 월드컵 (골드4)
• 9207 페그 솔리테어 (골드4)
• 1248 Guess(골드3)

---

2. BFS

• 1697 숨바꼭질 (실버1)
• 1389 케빈 베이컨의 6단계 법칙 (실버1)
• 21937 작업 (실버1)
• 16927 뱀과 사다리 게임(골드5)
• 2589 보물섬(골드5)
• 9019 DSLR (골드4)
• 13013 숨바꼭질4 (골드4)
• 12886 돌 그룹 (골드4)
• 2206 벽 부수고 이동하기 (골드3)
• 5972 택배 배송 (골드5)
• 1283 파티 (골드3)
• 10282 해킹 (골드4)

---

3. Binary Search

• 1920 수 찾기 (실버4)
• 10816 숫자 카드2 (실버4)
• 2417 정수 제곱근 (실버4)
• 6236 용돈관리 (실버1)
• 8983 사냥꾼 (골드4)
• 2110 공유기 설치 (골드4)

---

4. 스택 & Queue

• 2504 괄호의 값 (골드5)
• 1662 압축(골드4)
• 17608 막대기(브론즈2)
• 3986 좋은 단어 (실버4)
• 2841 외계인의 기타 연주 (실버1)
• 2493 탑(골드5)
• 17298 오큰수 (골드4)
• 9935 문자열 폭발(골드4)
• 1158 요세푸스 문제(실버4)
• 1966 프린터 큐(실버3)
• 5464 주차장 (실버2)
• 3078 좋은 친구(골드4)