Awesome

lst 라는 이차원 행렬에서 3개를 조합으로 뽑고 싶을 때

중복되는 경우 없이 뽑고 싶다면 

row, col을 기억하면서 같은 row일 때는 해당 col보다 작은 값들은 보지 않도록 하면 된다.

(같은 row에서 해당 col보다 작은 값들은 이미 본 것이므로)

lst = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
check = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
n, m = 3, 3


def combination(count, r, c):
    global ret  # 조합 갯수 세기
    if count == 3:
        print(selected)
        ret += 1
        return
    for i in range(r, n):
        if i == r:  # 해당 row일 때는 col보다 작은 값은 보지 않기
            c2 = c
        else:
            c2 = 0
        for j in range(c2, m):
            if check[i][j] == 0:
                check[i][j] = 1
                selected.append(lst[i][j])
                combination(count+1, i, j)
                check[i][j] = 0
                selected.pop()
ret = 0
selected = []

combination(0, 0, 0)
print(ret)

https://www.acmicpc.net/problem/14888

import sys

'''
chosen 리스트에 담긴 순서대로 계산하는 함수
0: +, 1: -, 2: *, 3: / 로,
chosen에 0, 0, 1, 2, 3이 담겨있다면 연산자 순서는 + + - * / 이 된다.
그리고 numbers와 chosen에서 하나씩 꺼내오면서 계산 후 결과를 리턴 
'''
def calc():
    ret = numbers[0]  # 일단 첫번째 숫자를 결과에 넣고 시작
    for idx, op in enumerate(chosen):
        if op == 0:
            ret += numbers[idx+1]
        elif op == 1:
            ret -= numbers[idx+1]
        elif op == 2:
            ret *= numbers[idx+1]
        else:
            if ret < 0:
                ret = -(abs(ret) // numbers[idx+1])  # 문제에 있던 c++14 스타일 음수 나눗셈
            else:
                ret = ret // numbers[idx+1]
    return ret


'''
연산자의 종류는 총 4개이므로, 4번을 for문으로 돌되 
선택된 연산자는 oper 리스트에서 1씩 빼 준다. 0이 되면 그 연산자를 패스한다.
순열과 똑같다.
'''
def dfs(count):
    global minValue, maxValue
    if count == sum:
        minValue = min(minValue, calc())
        maxValue = max(maxValue, calc())
        return
    for i in range(4):
        if oper[i] <= 0:
            continue
        oper[i] -= 1
        chosen.append(i)  # 0-더하기,1-빼기,2-곱,3-나누기
        dfs(count+1)
        chosen.pop()
        oper[i] += 1


n = int(sys.stdin.readline()) # 숫자의 갯수. 문제에서의 n
numbers = list(map(int, sys.stdin.readline().split()))  # 숫자 리스트
oper = list(map(int, sys.stdin.readline().split()))  # 입력 받는 연산자 배열. ex) 0 1 0 0
sum = 0  # 입력 받은 oper 리스트의 합. 이제 연산자 선택을 다 했으니 계산해라~할 때 조건문에 쓰임
for i in oper:
    sum += i
chosen = []  # 선택된 연산자
ret = 0  # 각 케이스 별 계산 결과를 담을 변수
minValue = 1000000000  # 주의! 0으로 초기화하면 min이 0이 되어버릴 수 있음
maxValue = -1000000000
dfs(0)
print(maxValue)
print(minValue)

https://www.acmicpc.net/problem/2580

참고로 문법은 python2, 제출은 pypy2로 했다.

python3으로 하니 시간 초과가 났다.

주요 아이디어는 zero라는 리스트에 값이 0인 것들의 행렬을 튜플로 저장해놓은 것이고,

또 작은 사각형에 중복된 숫자가 있는지 검사할 때

속하는 작은 사각형의 범위를 (row//3)*3, (col//3)*3으로 표현한 것이다.

이것만이 정답은 아니지만 프로그래밍을 할 때

'무언가 정보를 담을 새로운 공간'를 떠올려 보는 것도 좋을 것 같다.

import sys
r = sys.stdin.readline

board = []
for i in range(9):
    board.append(list(map(int, r().split())))

zero = []
for i in range(9):
    for j in range(9):
        if board[i][j] == 0:
            zero.append((i, j))

def Print():
    for row in range(9):
        for col in range(9):
            print board[row][col],
        print("")

def isPossible(num, row, col):
    if num in board[row]:
        return False
    for i in range(9):
        if num == board[i][col]:
            return False
    row_t = row // 3 * 3
    col_t = col // 3 * 3
    for r in range(row_t, row_t + 3):
        for c in range(col_t, col_t + 3):
            if num == board[r][c]:
                return False
    return True

def dfs(zeroIndex):
    if zeroIndex == len(zero):
        Print()
        exit(0)
    for num in range(1, 10):
        row = zero[zeroIndex][0]
        col = zero[zeroIndex][1]
        #print("row col: {} {}".format(row, col))
        if isPossible(num, row, col):
            board[row][col] = num
            dfs(zeroIndex+1)
        board[row][col] = 0

dfs(0)

https://www.acmicpc.net/problem/9663

앞선 문제인 N과 M에서 사용되는 DFS를 활용한 문제이다.

중요한 아이디어는 같은 row에는 퀸이 하나밖에 존재할 수 없으며, 또 하나는 무조건 있다는 것이다.

이번 row에는 퀸이 어디에 와야할 지 column을 차례대로 늘려가면서 findColumn 함수를 통해 검사한다.

개인적으로는 row와 col이 서로 헷갈리고, for문의 range를 정하는 것 때문에 어려웠던 문제이다.

코드 설명은 주석으로 대신한다. 밑에서부터 보면 된다.

def isPossible(row, col):  # 위 혹은 양방향 대각선에 퀸이 있는지 검사
    # 좌우는 볼 필요가 없다. 하나의 row에는 하나의 퀸!

    # 위 (아래를 안 보는 이유는 아직 다음 row 자체를 안 봤기 때문
    for i in range(1, n):  # 주의: 1부터다. 0으로하면 7번째 줄에서 자기 자신과 같은지 검사하게 됨
        if row-i >= 0:  # row를 1씩 줄여가되 음수가 되지 않도록 한다. 
            if chess[row-i][col]:  # 퀸을 발견했다
                return False

    # \ 방향 대각선. row, col에서 1씩 빼면서 확인
    for i in range(1, n):
        if row-i >= 0 and col-i >= 0:
            if chess[row-i][col-i]:
                return False

    # / 방향 대각선. row는 -1, col은 +1 (그림으로 생각해보자)
    for i in range(1, n):
        if row-i >= 0 and col+i < n:
            if chess[row-i][col+i]:
                return False
    return True  # 위 모든 검사를 통과했다면 그거슨 퀸

def findColumn(row):
    global answer  # 전역변수를 함수 내에서 수정하기 위해 global 선언
    if row == n:  # 하나의 row에는 하나의 퀸이 무조건 들어가므로, row가 n이라면 퀸의 자리를 다 찾은 것임
        answer += 1
        return
    for col in range(n):  # row는 정해져 있으니 column을 1씩 증가시키면서 확인한다
        if isPossible(row, col):  # 놓을 수 있다면 
            chess[row][col] = True  # True로 퀸의 자리를 표시
            findColumn(row+1)  # 다음 row에서 퀸의 자리를 찾는다
        chess[row][col] = False  # 재귀가 끝난 후, 백트래킹해야하므로 다시 False로 돌려놓는다

n = int(input())
chess = [[False]*n for _ in range(n)]  # 체스판. True면 퀸이 있는 자리
answer = 0
findColumn(0)  # 인자는 row. 0번째 row부터 퀸이 들어갈 column을 찾는다.
print(answer)

https://www.acmicpc.net/problem/15650

조합 문제이다.

구현에 있어서 순열과 다른 점은,

조합의 경우 순서가 없기 때문에 check만 확인해서 True인 것들만 출력하면 되지만

순열의 경우 1, 2, 5와 1, 5, 2가 다른데 check 확인 후 출력하면 항상 앞에서부터 1, 2 5로 출력이 될 것이기 때문이다.

따라서 조합은 뽑은 수열을 위한 리스트가 따로 없음을 유의하면 순열과 다른 점은 없다.

순열과 달리 시작부가 dfs(0, 0) = dfs(idx, cnt) 으로 시작하는 것은

dfs를 재귀호출 했을 때 리스트의 처음부터 다시 탐색해야 하는 '순열'과는 달리

조합은 지금까지 탐색했던 것들은 다시 탐색할 필요가 없기 때문에 현재 인덱스를 저장해놓기 위함이다.

(설명추가: 조합은 1을 한번 선택해서 조합을 꾸렸다면, 그게 1이 포함된 조합의 전부이다.

즉, 1이 포함된 조합 선택이 끝나면, 그 이후로는 1을 선택하지 않을 것이다. )

n, m = map(int, input().split())
lst = []
check = [False] * n
for i in range(1, n+1):
    lst.append(i)

def Print():
    for i, v in enumerate(check):
        if v == True:
            print(lst[i], end = ' ')
    print("")

def dfs(idx, cnt):
    if cnt == m:
        Print()
        return
    for i in range(idx, n):
        if check[i] == True:
            continue
        check[i] = True
        dfs(i, cnt+1)
        check[i] = False

dfs(0, 0)  # lst의 0번째 인덱스부터 살펴보면서 / 0번째 수열부터 뽑을 것임

https://yabmoons.tistory.com/99

를 참고했다.

백트래킹 단계를 시작하면서, 이게 무엇인지부터 찾아봤다.

완전 탐색의 일종인데, 완전 탐색은 모든 경우를 다 살펴보지만

백트래킹의 경우 그게 아니라면 쳐내고 살펴본다고 한다.

DFS, BFS가 그 예시라고 함.

나같은 경우 직접 순열을 DFS로 코딩해본 적이 없어서 기본기를 잡느라 오래 걸렸던 문제였다.

DFS가 무엇인지 알고, 스택을 사용한다는 것도 알고 있었는데 직접 내 손으로 만들어보려니 생각이 나질 않았다.

많이 쓰이는 알고리즘이라고 하니 한 번 이해하고 스택 구현하듯이 외울 정도가 되어도 나쁘지 않을 것 같다.

n, m = map(int, input().split())
lst = []
for i in range(1, n+1):
    lst.append(i)
check = [False] * n
tmp = []

def Print(string):
    for num in string:
        print(num, end=' ')
    print("")

def dfs(cnt):
    if cnt == m:
        Print(tmp)
        return
    for i, v in enumerate(check):
        if v == True:
            continue
        check[i] = True
        tmp.append(lst[i])
        dfs(cnt+1)
        tmp.pop()
        check[i] = False

dfs(0)

자세한 설명은 밑에 참고한 블로그에 써 있긴 하지만, 정리할 겸 내 언어로 풀어가보면 이렇다.

코드를 실행하면 마지막 줄의 dfs(0)부터 시작되는데 맨 처음에 인덱스 0부터 탐색하겠다는 뜻이다.

15649번 문제를 보면 '오름차순'으로 정렬하라고 했기 때문이다. 리스트를 오름차순으로 정렬해놨기 때문에...

dfs 함수에 처음 들어가게 되면, 14번줄 cnt가 m인지 묻는 것은 나중을 위한 것이다. 

일단 17번째 줄을 보게 되면 check 리스트를 순회하는 것을 볼 수 있다.

check 리스트는 False로 초기화되어있는데,

처음에는 True인 것이 아무것도 없으므로 일단 check[0]을 True로 만들고 (=순열로 선택하고)

같은 인덱스를 가진 리스트의 원소를 tmp 리스트에 추가시킨다. (21 line)

중요한 것은 22번째 줄 dfs 함수를 재귀호출하는 것에 있는 듯 하다.

아까 말했듯 14번째 줄에 m개만큼 선택을 전부 다 했는지 묻고, 그렇다면 프린트를 한다.

이후에 재귀를 벗어나 15번째 줄로 돌아오게 되는데, 선택했던 것을 다시 빼내고 check도 False로 바꾼다.

이러한 아이디어다.

중간에 실수했던 점은 tmp.pop()을 재귀함수 밑이 아닌 프린트 함수 내에 썼던 것인데,

프린트를 한다=출력을 한번 했으니까 그 다음엔 빼내야지. 라고 단순하게 생각했기 때문이다.

저 생각이 틀린 것은 아닌데, 문제는 pop의 위치이다.

프린트할 때만 pop을 하니까 

1 2

1 3 

1 4

1 5 

1 2 3

1 2 4

...

이런 식으로 출력이 되었다. 1, 5 -> 1, 2, 3으로 넘어갈 때 5만 pop하고 그 다음 넣을 원소를 찾게 됐던 것.

14번째 줄의 cnt == m 일 때만 pop을 했던 것이다.

1, 5에서 5를 빼낸 후 리스트에 1만 남아있을 때 다시 재귀 복귀를 해서 또 pop이 이루어져서 1도 빼내야 하는데 말이다.

말로 하니까 어려운데...그랬다.

https://yabmoons.tistory.com/99

를 참고했다.