완전 탐색과 시뮬레이션

완전탐색

모든 경우의 수를 모두 계산하는 방법

시뮬레이션

문제에서 제시한 알고리즘을 한 단계식 차례대로 직접 수행해야 하는 문제 유형

구현 문제에 접근하는 방법

구현 문제는 문제의 길이가 긴 편이데, 문법에만 익숙하다면 쉽게 풀 수 있다.
API 개발 문제 또한 구현 유형과 상당히 연관이 있는데, 이러한 문제는 알고리즘 문제와 별개로 웹 서버나 데이터 분석에 대한 기초 지식도 필요하다.

백준 2231번: 분해합

n = int(input())
r = 0
for i in range(1, n+1):
    nums = list(map(int, str(i)))
    r = sum(nums) + i
    if r == n:
        print(i)
        break
    if i == n:
        print(0)

접근 방식
아직 알고리즘에 익숙치 않아서 그런지 접근방식이 너무 기초적이었다.
(자릿수라서 10으로 나누는 것 먼저 떠올랐다 ㅠ)
1. 파이썬의 라이브러리 map을 통해 각 자리수 값으로 리스트에 저장한다.
2. sum()함수를 이용해서 각 값을 모두 합친다.
3. 자릿값의 합이 n과 같으면

백준 12784번: 인하니카 공화국

import sys
input = sys.stdin.readline

def dfs(x):
    visited[x] = True
    dynamite = 0
    for g in graph[x]:
        if not visited[g[0]]:
            dynamite += min(g[1], dfs(g[0]))
    return dynamite if dynamite else 10000


for _ in range(int(input().rstrip())):
    N, M = map(int, input().rstrip().split())
    if N == 1:
        print(0)
    else:
        graph = [[] for _ in range(N + 1)]
        visited = [False for _ in range(N + 1)]
        for _ in range(M):
            a, b, c = map(int, input().rstrip().split())
            graph[a].append((b, c))
            graph[b].append((a, c))
        print(dfs(1))

백준 14889번 : 스타트와 링크

def dfs(depth, idx):
    global min_diff
    if depth == n//2:
        power1, power2 = 0, 0
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    power1 += graph[i][j]
                elif not visited[i] and not visited[j]:
                    power2 += graph[i][j]
        min_diff = min(min_diff, abs(power1-power2))
        return

    for i in range(idx, n):
        if not visited[i]:
            visited[i] = True
            dfs(depth+1, i+1)
            visited[i] = False


n = int(input())

visited = [False for _ in range(n)]
graph = [list(map(int, input().split())) for _ in range(n)]
min_diff = int(1e9)

dfs(0, 0)
print(min_diff)