해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 1920 수 찾기 - 이분 탐색

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

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

문제 풀이

1. 이 문제는 이분 탐색 알고리즘을 이용하여 풀 수 있는 문제입니다.
(하나씩 순차적으로 찾게 되면 시간초과가 됩니다.)

2. 우선 입력된 배열 N을 정렬시킵니다.

3. 시작과 끝 지점을 각각 left와 right로 놓고, 중간 지점을 mid로 놓습니다.

4. mid에 위치한 값과 비교하여,
 4-1. 동일한 값이면, 1을 반환합니다.

 4-2. 값이 크면 left를 mid + 1로 놓고, 다시 검색합니다.

 4-3. 값이 작으면 right를 mid -1로 놓고, 다시 검색합니다.

 4-4. 원하는 값이 없으면, 즉 left 값이 right 값보다 크면 0을 반환합니다.

전체 코드

from sys import stdin

n = stdin.readline()
N = sorted(map(int,stdin.readline().split()))
m = stdin.readline()
M = map(int, stdin.readline().split())

def binary(value, left, right):
    print(value, left, right)
    if left > right:
        return 0
    mid = (left+right)//2
    if value == N[mid]:
        return 1
    elif value < N[mid]:
        return binary(value, left, mid-1)
    else:
        return binary(value, mid+1, right)

for v in M:
    left = 0
    right = len(N)-1
    print("v 입니다.")
    print(binary(v,left,right))

파이썬 / BOJ 백준 / 1780 종이의 개수 - 분할정복

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

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

풀이

1. 이 문제는 분할정복으로 풀 수 있는 문제입니다. 

2. 조건이 만족하지 않는 경우(색상이 모두 같은 경우가 아닌 경우)는 9개로 쪼개서 다시 푸는 방식입니다.

3. 9개로 쪼개는 것은 재귀 함수를 호출하여 풀고, 전달인자로 그 9개의 각각 종이 중 가장 왼쪽 위의 좌표와 크기를 넣습니다.

4. 조건이 만족하는 경우(하나의 색상으로만 구성되는 경우)는 해당 색상의 값을 +1해줍니다.

전체 코드

N = int(input())

board = [list(map(int, input().split())) for _ in range(N)]

result_minus = 0
result_zero = 0
result_plus = 0


def dfs(x, y, n):
    global result_minus, result_zero, result_plus

    num_check = board[x][y]
    for i in range(x, x + n):
        for j in range(y, y + n):
            if (board[i][j] != num_check):
                for k in range(3):
                    for l in range(3):
                        dfs(x + k * n // 3, y + l * n // 3, n // 3)
                return

    if num_check == -1:
        result_minus += 1
    elif num_check == 0:
        result_zero += 1
    else:
        result_plus += 1


dfs(0, 0, N)
print(f'{result_minus}\n{result_zero}\n{result_plus}')

파이썬 / BOJ 백준 / 9663 N-Queen - 백트래킹

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

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다. 백트래킹의 가장 기초적인 문제라 할 수 있습니다.

2. 한 줄에 두 개 들어가는 게 불가능하기 때문에, 행과 열 중에 하나를 정해서 기준점 잡고 백트래킹에 들어갑니다.

3. 열을 기준점으로 잡은 경우에 col[x]에 행의 번호를 넣습니다. 이때, col[x]에 행의 번호를 넣었을 때, 다른 퀸이 공격할 수 있는지 check합니다. 퀸이 공격할 수 없는 위치라면, dfs(x+1)함수를 호출하여, 그 다음 열에 대해서 같은 작업을 반복합니다.

4. 재귀함수에서 전달인자의 크기가 N이면 결과값으로 카운팅 합니다.

전체 코드

def check(x):
    for i in range(x):
        if col[x] == col[i] or abs(col[i]-col[x]) == x-i:
            return False
    return True

def dfs(x):
    global res
    if x == n:
        res += 1
        return
    for i in range(n):
        col[x] = i
        if check(x):
            #print(x, " ", i)
            dfs(x+1)

n = int(input())
res = 0
col=[0]*15

dfs(0)
print(res)

파이썬 / BOJ 백준 / 15652번 N과 M(4) - 백트래킹

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

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다. 백트래킹의 가장 기초적인 문제라 할 수 있습니다. 15651의 문제에서 약간 변형된 문제입니다.

https://zidarn87.tistory.com/329

2. 중복이 가능하기 때문에, 재귀 시 i를 넘겨주어 같은 수도 고를 수 있게 합니다.

3. 비내림차순이기 때문에 index 적용합니다. for 문은 index부터 시작하여, 비내림차순으로 출력하도록 합니다.

전체 코드

N, M = map(int, input().split())
lst = []

def dfs(cnt, index):
    if cnt - 1 == M:  # 탈출 조건
        print(' '.join(map(str, lst)))
        return

    for i in range(index, N+1):
        lst.append(i)
        dfs(cnt+1, i)
        lst.pop()
dfs(1, 1)