우주의 IT 소행성

DFS (Depth First Search, 깊이 우선 탐색)

- 그래프에서 깊은 부분을 우선 탐색하는 알고리즘

그래프란?

- 노드와 간선(정점)으로 표현된 자료구조

- 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 그래프 탐색이라고 한다.

- 두 노드가 간선으로 이어져 있으면 '두 노드는 인접(Adjacent) 하다'라고 표현한다.

그래프의 표현 방식

- 그래프를 프로그래밍에서 표현하는 방식은 크게 2가지이다

1. 인접 행렬 방식 (Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현

표로 표현했을 때

INF = 999999999 # 무한

# 2차원 리스트의 인접 행렬 표현
graph = [
	[0, 3, 5],
    [3, 0, INF],
    [5, INF, 0]
}

print(graph)

파이썬 코드로 표현했을 때

- 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리의 낭비가 심함

- 인접 행렬 방식이 인접 리스트 방식보다 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠름

2. 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현

graph = [[] for _ in range(3)]

graph[0].append((1, 5))
graph[0].append((2, 3))

graph[1].append((0, 5))

graph[2].append((0, 3))

print(graph)

- 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용함

- 인접 리스트 방식은 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림 (데이터를 하나씩 확인)

# DFS
def dfs(graph, v, visited):
	visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
dfs(graph, 1, visited)

BFS (Breadth First Search, 너비 우선 탐색)

- 가까운 노드부터 탐색하는 알고리즘

- DFS와 반대(가장 가까운 노드부터 / 가장 먼 노드부터)

- 선입선출의 큐 자료구조를 사용

- 재귀로 DFS를 구현하면 수행 시간이 느려질 수 있음

- 스택을 사용하여 DFS구현을 빠르게 동작시킬 수 있음

- 일반적인 경우 DFS보다 BFS의 동작이 빠름

# BFS
from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    while queue:
    	v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
bfs(graph, 1, visited)

처음에는 주어진 수를 2개의 중복순열로 리스트를 만들어

해당 리스트가 전부 소수로 되어있으면 추출하는 방식으로 했는데, 그 수많은 수들을 매 케이스마다 반복하려니

시간초과가 나왔다.

from itertools import product
import math
for _ in range(int(input())):
    target = int(input())
    array = [True for i in range(target + 1)]
    result = []

    for i in range(2, int(math.sqrt(target)) + 1):
        if array[i]:
            j = 2
            while i * j <= target:
                array[i * j] = False
                j += 1

    data = []
    for i in range(2, target + 1):
        if array[i]:
            data.append(i)

    result = []
    for i in product(data, repeat=2):
        if i[0] + i[1] == target:
            result.append(i)

    if len(result) % 2 == 0:
        index = len(result) // 2 - 1
        print(result[index][0], result[index][1])
    else:
        index = len(result) // 2
        print(result[index][0], result[index][1])

최초 코드

그래서 결국 처음에 에라토스테네스의 체로 구별해 낸 소수 리스트을 1회 이용하여 연산해야 할 방법을 찾아야 했다.

중간값부터 1씩 올리고 / 1씩 내리고 를 반복하며 찾아가는 방식으로 n/2 회로 시간 복잡도를 줄여나갔다.

import math, sys
input = sys.stdin.readline
array = [True for i in range(10001)]

for i in range(2, 101):
    if array[i]:
        j = 2
        while i * j <= 10000:
            array[i * j] = False
            j += 1

for _ in range(int(input())):
    target = int(input())
    x = target // 2
    y = x

    for _ in range(10000):
        if array[x] and array[y]:
            print(x, y)
            break
        x -= 1
        y += 1

결과 코드