완전탐색(Brute Force)

• 특징: 가능한 모든 경우의 수를 탐색하는 방법. 작은 데이터셋에서 유용하며, 시간이 허락되는 한 최적해를 찾는 데 유리함.
• 자주 나오는 문제 유형:
  1) 가능한 모든 경우를 시도하여 해를 찾는 문제
  2) 순열 및 조합 문제

 

1. 백준 - 부분수열의 합

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

 

부분수열이란? 배열에서 일부 원소를 선택하여  순서는 유지하되, 연속하지 않아도 되는 수열

ex. [-7, -2, 3, 4] 의 부분수열: [-7] [-2] [3] [4] [-7, -2] [-7, 3] [-7, 4] [-2, 3] [-2, 4] [3, 4]  [-7, -2, 3] [-7, -2, 4] 

 이처럼 연속하지 않아도 순서만 유지하면 됨

 

 아이디어)

각 원소는 선택 하거나, 선택하지 않거나 두 경우가 존재

>> 각 원소마다 재귀함수로 반복

def find_subsequences(idx, current_sum):
    global count

    if idx == N:
        return
    
    # 현재 원소를 선택한 경우
    current_sum += arr[idx]

    if current_sum == S:
        count +=1

    # 현재 원소를 선택한 경우와, 선택하지 않은 경우 각각 재귀 호출
    find_subsequences(idx + 1, current_sum)
    find_subsequences(idx + 1, current_sum - arr[idx] ) # 더하지 않고 그대로 패스 해야하므로 다시 빼준다


# 입력
N, S = map(int, input().split())
arr = list(map(int, input().split()))

count = 0  # 합이 S인 부분수열의 개수를 저장하는 변수

# 부분수열 탐색
find_subsequences(0, 0)

print(count)

 

 

2. 백준 - 체스판 다시 칠하기

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

 

슬라이딩 윈도우 개념. 이동 가능한 행/열 범위 내에서 8칸씩 모든 부분을 체크해야 한다

N = 10  # 열 개수
M = 13  # 행 개수

matrix = [
    # 예시 체스판
]

min_count = float('inf')  # 최소 칠해야 할 칸의 수를 저장

# 체스판을 8*8로 잘라서 모든 범위를 확인
for i in range(N-7):
    for j in range(M-7):
        count_w_start = 0 # W로 시작하는 체스판일 경우
        count_b_start = 0 # B로 시작하는 체스판일 경우

        for x in range(i, i+8):
            for y in range(j, j+8):
                if (x+y)%2 == 0: # 짝수 위치
                    if matrix[x][y] != 'W':
                        count_w_start += 1
                    if matrix[x][y] != 'B':
                        count_b_start += 1
                else:  # 홀수 위치
                    if matrix[x][y] != 'B':
                        count_b_start += 1
                    if matrix[x][y] != 'W':
                        count_w_start += 1

    # W, B 두 경우 중 더 적은칸을 칠하는 경우로 갱신
    min_count = min(min_count, count_b_start, count_w_start)
                    
print(min_count)

 

 

3. 백준 - 숫자야구

드디어 스스로 풀수 있게 된 문제...

몇가지 놓친 부분이 있다.

1. 문제에서 '각기 다른' 세자리 수 라고 했으니 중복되는 숫자는 제외 하고, 0이 포함된 숫자도 제외해야햠
> set()으로 중복된 숫자는 삭제해버리고, len이 3이아니면 중복된 숫자가 있다는 의미

2. number는 숫자이므로 인덱스 접근하려면 str변환을 먼저 해주어야함
3. 123 숫자를 ['1', '2', '3'] 으로 변환하는법 > list(str(123))

# 동일한 위치: 스트라이크, 다른자리에 위치하면 볼 
array = [ [123, 1, 1], [356, 1, 0], [327, 2, 0], [489, 0, 1] ]

# 세 자리 수: 100 ~ 999 까지
answer = 0

for number in range(100, 1000):
    # 각 자리 숫자가 중복되거나 0이포함되면 패스
    str_number = str(number)
    if len(set(str_number)) != 3 or '0' in str_number:
        continue

    match_count = 0
    for hintArr in array:
        hint = list(str(hintArr[0])) # ['1','2','3']
        strike = 0
        ball = 0
        for i in range(3):
            if str_number[i] == hint[i]:
                strike += 1
            elif str_number[i] in hint:
                ball += 1

        if [strike, ball] == [hintArr[1], hintArr[2]]:
            match_count += 1
        
    if match_count == len(array): # 모든 힌트를 만족하는 경우만 정답 카운트 증가
        answer += 1

print(answer)

 

 

 

4. 백준 연산자 끼워넣기

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

백트래킹: 재귀함수 호출이 모든 연산자를 사용한 후에 종료 조건에 도달하면, 이전 호출로 돌아가 다른 연산자를 사용하여 새로운 경로 탐색

def insert_operators(numbers, operators):
    n = len(numbers)
    max_value = -float('inf')
    min_value = float('inf')

    def dfs(depth, current_result, add, sub, mul, div):
        nonlocal max_value, min_value

        # 모든 연산자가 소진된 경우, min/max  업데이트
        if depth == n:
            max_value = max(max_value, current_result)
            min_value = min(min_value, current_result)
            return
        
        # 각 연산자가 남아있을때 까지 dfs반복
        if add > 0:
            dfs(depth+1, current_result + numbers[depth], add - 1, sub, mul, div)
        if sub > 0:
            dfs(depth+1, current_result - numbers[depth], add, sub - 1, mul, div)
        if mul > 0:
            dfs(depth+1, current_result * numbers[depth], add, sub, mul - 1, div)
        if div > 0:
            dfs(depth+1, int(current_result / numbers[depth]), add, sub, mul, div - 1)

    # DFS 탐색 시작
    dfs(1, numbers[0], operators[0], operators[1], operators[2], operators[3])
    
    return max_value, min_value

 

 

* nonlocal / global의 차이

- global: 전역 변수(global variable)를 참조하고, 함수 내부에서 이를 수정할 때 사용

x = 10  # 전역 변수

def modify_global():
    global x
    x = 20  # 전역 변수 x를 수정
    print(x)  # 출력: 20

modify_global()
print(x)  # 출력: 20 (전역 변수 x가 변경됨)

 

- nonlocal: 중첩 함수(함수 안에 함수가 있는 경우)에서 외부 함수의 지역 변수를 수정

def outer():
    x = 10  # 외부 함수의 지역 변수
    
    def inner():
        nonlocal x  # 외부 함수의 x를 참조
        x = 20  # 외부 함수의 지역 변수 x를 수정
        print(x)  # 출력: 20
    
    inner()
    print(x)  # 출력: 20 (외부 함수의 지역 변수 x가 변경됨)

outer()

 

 

5. 백준 쿼드트리
https://www.acmicpc.net/problem/1992

4번과 유사하게 재귀함수 중첩 호출 문제

솔루션 안보고 스스로 구현해보는 연습 필요

def compress_quad_tree(x, y, n):
    # 첫 번째 값으로 전체 영역의 색상이 같은지 확인
    first_color = image[x][y]
    all_same = True

    # 전체 구역이 같은 색인지 확인
    for i in range(x, x + n):
        for j in range(y, y + n):
            if image[i][j] != first_color:
                all_same = False
                break
        if not all_same:
            break

    # 모두 같은 색이라면 해당 색상 반환
    if all_same:
        return str(first_color)

    # 다른 색이 포함되어 있으면, 다시 4등분하여 재귀 호출
    half = n // 2
    top_left = compress_quad_tree(x, y, half)
    top_right = compress_quad_tree(x, y + half, half)
    bottom_left = compress_quad_tree(x + half, y, half)
    bottom_right = compress_quad_tree(x + half, y + half, half)

    # 4등분 결과를 괄호로 묶어서 반환
    return f"({top_left}{top_right}{bottom_left}{bottom_right})"


# 입력 처리
N = int(input())  # 영상의 크기
image = [list(map(int, input().strip())) for _ in range(N)]

# 결과 출력
print(compress_quad_tree(0, 0, N))