우주의 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)

택시 기하학? 이라길래 위 사진의 택시를 생각했는데, 헤르만 민코프스키가 고안안 비유클리드 기하학의 택시 기하학을 의미하는 것이었다.  

단순 식으로 r이 주어졌을 때

유클리드 기하학에서는 r * r * 3.14159265358979323846....

택시 기하학에서는 r * (r * 2) 로 나타낼 수 있다.

코드로 옮겨주기만 하면 끝

r = int(input())
n1 = r * r * 3.14159265358979323846
n2 = r * (r * 2)
print("%.6f" %n1)
print("%.6f" %n2)

이전 포스팅 한 소수 구하기를 응용하여 풀 수 있다.

주어진 수를 소수의 작은 순서로 나누어 떨어지는 데 까지 나누고

마지막 남은 나머지가 소수 리스트 안에 있다면 해결

소수 리스트 안에 없다면 소인수 분해가 불가능 하다고 판단.

import math
n = int(input())
array = [True for i in range(n + 1)]

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


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

while True:
    if n in data:
        print(n)
        break

    elif n == 1:
        break

    for i in range(2, n + 1):
        if n % i == 0:
            n //= i
            print(int(i))
            break