[TIL Day10] 라이브 세션 - 코딩테스트 문제 같이 풀기

라이브 세션 - 코딩테스트 문제 같이 풀기

1. 빙고

• 문제 설명
  - 빙고 게임 보드에 적힌 숫자가 담겨있는 배열 board, 게임 보드에서 순서대로 지운 숫자가 들어있는 배열 nums가 매개변수로 주어진다.
  • board에서 nums에 들어있는 숫자를 모두 지우면 몇 개의 빙고가 만들어지는지 return하도록 함수를 완성하라.

def solution(board, nums):
    answer = 0
    size = len(board) # 빙고판의 사이즈(N)
    
    hor = [0] * size # 가로
    ver = [0] * size # 세로
    diag = [0] * 2 # 대각선
    
    # 빙고에서 중요한건 결국 인덱스
    # 인덱스를 먼저 기억해두자
    idx = {}
    
    # 이중 loop를 통해서 board -> (x, y)
    for i in range(size): # 행
        for j in range(size): # 열 [i][j]
            idx[board[i][j]] = (i, j)
            
    # num을 순회!
    for elem in nums:
        y, x = idx[elem]
        # 대각선 체크 주의
        if y == x: diag[0] += 1
        # 우상향 대각선
        if y == size - x - 1: diag[1] += 1
        ver[x] += 1
        hor[y] += 1
    
    # counting
    answer = hor.count(size) + ver.count(size) + diag.count(size)
    return answer

2. 2 x n 타일링

• 문제
  - 가로의 길이가 n, 세로의 길이가 2인 바닥을 가로의 길이가 2 x 세로의 길이가 1인 직사각형 모양의 타일로 가득 채우려고 한다.
  - 타일을 채울 때는 다음과 같이 2가지 방법이 있다.
  • 타일을 가로로 배치 하는 경우
  • 타일을 세로로 배치 하는 경우
  • 이 직사각형을 채우는 방법의 수를 return하는 함수를 완성하라.

# 재귀적으로 구현하면 depth 초과
# 메모이제이션으로 풀자!

def solution(n):
    # basis condition n = 1, n = 2
    dp = [1, 2]
    for i in range(2, n):
        dp.append((dp[i - 1] + dp[i - 2]) % 1000000007)
    return dp[-1]
    

3. N-Queen

• 문제
  - 가로, 세로 길이가 n인 정사각형으로 된 체스판이 있다.
  - 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하는 방법의 수를 return하는 함수를 완성하라.
  - 퀸은 가로, 세로, 대각선으로 이동할 수 있으며 n은 12이하의 자연수이다.
  - 완전 탐색 과정에서 가지치기를 통해 경우의 수를 구한다.(back-tracking)
  

# DFS(깊이 우선 탐색) 알고리즘
# stack, recursive 구조

# row번째 행을 check
def n_queen(lst, row, n):
    """
    lst: 어떤 열에 담았는지 저장하는 list
    # 행별로 퀸이 1개씩만 들어갈 수 있으니, 열 값만 기억한다. -> 1행 1퀸 보장
    # 1차원 리스트에서 idx는 행, value는 열을 나타내도록 저장
    
    row: 현재 행
    
    n: 체스판 사이즈
    """
    count = 0
    # 종료 조건
    if row == n:
        return 1
    
    for col in range(n):
        lst[row] = col # 일단 row, col 위치에 에 퀸을 두자
        for i in range(row): # 0 ~ 바로 전까지 체크!
            # 열 체크
            if lst[i] == lst[row]:
                break
            # 우상향 대각선 체크
            if i + lst[i] == row + lst[row]:
                break
            # 우하향 대각선 체크
            if i - lst[i] == row - lst[row]:
                break
        # for-else 문으로 for가 break 없이 끝나면 else 실행
        else: 
            count += n_queen(lst, row + 1, n)
    
    return count
    
    
def solution(n):
    return n_queen([-1] * n, 0, n)