이것저것 개발 블로그

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

그래프에서 깊은 부분을 우선적을 탐색하는 알고리즘. 스택(stack)을 사용한다!

동작 과정:

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

2번 과정에서 방문하지 않은 인접 노드를 스택에 넣을 때 순서는 상관없지만, 문제에 따라서 알파벳 순서 또는 작은 숫자 순서대로 가는 경우가 많으므로 작은 노드 순서대로 넣는 경우가 많다.

그럼 실습해보자!!

def dfs(graph, v, visited):
    # 현재 노드 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3],
    [1, 5],
    [1, 4],
    [3],
    [2, 6, 7],
    [1, 5],
    [5]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 8
# DFS 호출
dfs(graph, 1, visited)


### 출력 결과(stack에 들어간 순서대로): 1 2 5 6 7 3 4

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

가까운 노드부터 탐색하는 알고리즘. 큐(queue)를 사용한다!

동작 과정:

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

BFS와 마찬가지로 작은 노드부터 수행하는 경우가 많다!

위에 있는 그래프를 이용하여 다시 실습해보자!

from collections import deque

# BFS 정의
def bfs(graph, start, visited):
    # queue 구현 위해 deque 라이브러리 사용
    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

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3],
    [1, 5],
    [1, 4],
    [3],
    [2, 6, 7],
    [1, 5],
    [5]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 8
# BFS 호출
bfs(graph, 1, visited)


### 출력 결과(큐에 삽입된 순서대로): 1 2 3 5 4 6 7

"이것이 코딩테스트다" 책 문제 _ 구현 문제

문제)

사람 A는 N x N 크기의 정사각형 공간위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이고, 가장 오른쪽 아래 좌표는 (N, N)이다. A는 상, 하, 좌, 우 방향으로 이동할 수 있고, 시작 좌표는 항상 (1, 1)이다.

이때 A가 이동할 계획이 적힌 계획서가 있는데, 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 이 문자의 의미는 다음과 같다.

• L: 왼쪽으로 한 칸 이동
• R: 오른쪽으로 한 칸 이동
• U: 위쪽으로 한 칸 이동
• D: 아래쪽으로 한 칸 이동

이때 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1) 위치에서 L 혹은 U를 만나면 무시된다.

입력 조건

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 <= N <= 100)
• 둘째 줄에 A가 이동할 계획서 내용이 주어진다. (1 <= 이동횟수 <= 100)

출력 조건

• 첫째 줄에 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

풀이)

1. 내 풀이

이 문제는 x, y 좌표만 계산을 해 주면 간단한 문제이다.

이때 주의할 점은 L, R은 y 좌표에 영향을, U, D는 x 좌표에 영향을 준다는 것이다. (일반적인 좌표평면이 아니라서 그렇다.)

따라서 반복문을 이용하여 계획서 내 L, R, U, D 각각에서 이동할 수 있는 조건에 해당하면 x, y좌표가 이동하도록 조건문을 작성했다.

N = int(input())
moving = input().split()

x = 1
y = 1

for i in moving:
    if y < N and i == 'R':
        y += 1
    elif y > 1 and i == 'L':
        y -= 1
    elif x > 1 and i == 'U':
        x -= 1
    elif x < N and i == 'D':
        x += 1

print(x, y)

2. 답지 풀이

이 문제는 구현 문제에서 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션에 해당한다. 

또한 연산 횟수가 이동 횟수에 비례하게 되어서 시간 복잡도가 O(N)이므로(이때, N은 이동 횟수) 시간 복잡도는 넉넉한 편이다.

N = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > N or ny > N:
        continue
    # 이동 수행
    x, y = nx, ny

print(x, y)

문제를 푸는 알고리즘은 내가 풀었던 방식과 같다. 하지만 풀이에선 L, R, U, D에 따른 이동 거리를 dx, dy로 만들어 주었고 nx, ny라는 변수에 이동한 좌표를 저장해 주었다. 공간을 벗어나지 않을 땐 nx, ny를 x, y로 갱신해주고, 공간을 벗어나는 경우에는 x, y를 갱신하지 않음으로써 예외처리를 해 주었다.

구현 종류

1. 완전 탐색

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

2. 시뮬레이션

문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행하는 방법

파이썬에서 int형 데이터의 개수에 따른 메모리 사용량

데이터 개수(리스트 길이) 1,000 당 메모리 약 4KB

=> 즉, 데이터 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한 확인 필요!!

파이썬에서 채점 시 시간 제한 고려

1초에 2,000만 번의 연산 정도를 한다면 실행 시간 제한에 안정적

만약, 시간 제한이 1초, 데이터의 개수가 100만 개라면 시간 복잡도 O(NlogN) 이내의 알고리즘으로 해결해야함

=> 문제를 풀 때 시간 제한과 데이터의 개수를 확인해야함!

"이것이 코딩테스트다" 책 문제 _ greedy 책 문제

문제)

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

  1. N에서 1을 뺀다.

  2. N을 K로 나눈다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성해라.

입력조건

• 첫째 줄에 N(2 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력조건

• 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

풀이)

N이 1이 되기 위해 횟수가 가장 최소가 되려면 빼는 것 보다 나누는 과정이 숫자를 1에 가장 빨리 도달하게 할 수 있는 방법이다.

즉, 나누기를 최대한 많이 실행하면 된다.

따라서 N을 K로 나누어 떨어질 때까지 뺀 후, K로 나누는 과정을 반복하면 된다.

예를 들어 N = 17, K = 3일 경우 연산 과정은 다음과 같다.

이를 구현한 코드는 다음과 같다.

N, K = map(int, input().split())
count = 0

while (N > 1) :
    if N % K == 0:
        N = N // K
    else:
        N -= 1
    count += 1

print(count)

N이 1이 될 때까지 진행하기 때문에 while문의 조건은 N이 1보다 클 때이다.

while문 내에서 N이 K로 나누어 떨어질 경우 N은 K로 나누었을 때 몫으로 되고, K로 나누어 떨어지는 경우가 아닐 때 N에서 1씩 뺀다.

이때 연산 횟수를 count 변수에 1씩 더하여 저장한다.

문제에서는 N의 범위가 10만 이하이므로, 일일히 1씩 빼도 문제가 없지만, N이 100억 이상일경우 효율성 문제가 발생할 수 있다. 따라서 N이 K의 배수가 되도록 한 번에 빼는 방식으로 작성할 수 있다.

정답 예시)

N, K = map(int, input().split())
count = 0

while True:
    target = (N // K) * K
    count += N - target
    N = target

    if N < K:
        break
    count += 1
    N //= K

count += (N - 1)
print(count)

target을 N보다 작지만 가장 큰, K로 나누어 떨어지는 수이고, count에 N과 target의 차이(N에서 1을 뺀 횟수)만큼 더해준다.

그리고 N을 다시 target으로 갱신해주고 K로 나누어준다. 이때, N이 K보다 작을 경우(몫이 계속 0이 되므로) while문에서 빠져나온다.

그리고 N이 1이 되기까지 횟수이므로 (N-1)만큼 count에 더해주면 된다.(N을 더할 경우 N이 0이 되어버린다.)

"이것이 코딩테스트다" 책 문제 _ greedy 책 문제

문제)

여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.

단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 게임의 룰에 맞게 카드를 뽑는 프로그램을 만들어라.

   1. 숫자가 쓰인 카드들이 N * M 형태로 놓여 있다. 이때 N은 행의 개수를, M은 열의 개수를 의미한다.

   2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.

   3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.

   4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

입력조건

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각가 자연수로 주어진다. (1 <= N, M <= 100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1이상 10,000 이하의 자연수다.

출력조건

• 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

풀이)

각 행마다 가장 작은 수를 찾은 후 그 중에서 가장 큰 수를 출력하면 된다.

N, M = map(int, input().split())
minimum = []
for i in range(N):
    L = list(map(int, input().split()))
    minimum.append(min(L))
print(max(minimum))

N, M을 입력 받아서 정수로 변환해주고, 각 행에서 가장 작은 수를 저장할 minimum이라는 리스트를 생성한다.

행의 수만큼 반복하여 각 행을 입력받으면 L이라는 list로 받고, min()을 이용하여 가장 작은 수를 minimum에 추가한다.

모든 행의 작은 수를 추가한 이후, max()를 이용하여 가장 큰 수를 출력해주면 된다.

이 문제는 앞에서 나온 문제에 비하면 매우 쉬운 난이도고, 답에서 나온 풀이도 비슷하기 때문에 생략한다.