10. 온보딩 알고리즘 사전스터디 5일차

코이그·2023년 3월 10일

항해99

목록 보기
9/54

스파르티코딩클럽 알고리즘 강의

그래프

연결되어 있는 정점들 간의 관계를 표현할 수 있는 자료구조.

자료구조 구분:
1. 선형구조: 자료 삽입/추출에 초점
2. 비선형구조: 표현에 초점

그래프는 연결 관계에 초점이 맞춰져 있음.

용어

  • 노드(Node): 연결 관계를 가진 각 데이터. (정점(Vertex)이라고도 부름)
  • 간선(Edge): 노드 간의 관계를 표시한 선.
  • 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드.

그래프 종류 유형

  • 유방향(Directed) 그래프: 간선에 방향이 있음. 간선은 단방향 관계를 나타내고 각 간선은 한 방향으로만 진행.
  • 무방향(Undirected) 그래프: 방향이 없는 간선.

그래프 표현 방법

  • 인접 행렬(Adjacent Matrix): 2차원 배열로 그래프의 연결 관계 표현
  • 인접 리스트(Adjacent List): 연결 리스트로 그래프의 연결 관계 표현

예시 그래프:

  1. 인접 행렬 표현:
    / 0123
    0xoxx
    1oxox
    2xoxo
    3xxox
    배열로 표현(코드):
    graph = [
    [ False, True, False, False ],
    [ True, False, True, False ],
    [ False, True, False, True ],
    [ False, False, True, False ]

  2. 인접 리스트 표현:
    0 -> 1
    1 -> 0 -> 2
    2 -> 1 -> 3
    3 -> 2
    딕셔너리로 표현(코드):
    graph = {
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2]
    }

주로 리스트로 많이 표현하는데, 그 이유는 공간 복잡도가 더 효율적이기 때문이다. 하지만 때로는 행렬로 표현할 때도 있다(노드 간 연결 되어있는 지 확인할 때 행렬로 표현하면 접근법을 쓰면 되서 더 빠름)

DFS

DFS(Depth First Search): 깊이 우선 탐색. 내려갈 수 있을 때까지(깊이) 내려가다가 다시 돌아가는 방식.
https://upload.wikimedia.org/wikipedia/commons/7/7f/Depth-First-Search.gif

DFS 구현

두 가지 구현 방법이 있다:
1. 재귀. (1, 2, 5, 6, 7, 3, 4)
2. 스택. (1, 4, 3, 5, 7, 6, 2)

예시 그래프)

위 그래프를 예시로 DFS를 구현해보기.

재귀

알아야 할 핵심 포인트:
1. 반복적으로 발생하는 일
2. 종료 조건

이번 문제는 단순 방문이기 때문에 종료 조건은 자식이 없는 경우이다. 반복적으로 실행하는 것은 현재 노드에서 인접 노드를 차례대로 방문하는 것이다.

방법:
1. 현재 노드 방문 처리 (visited.append(node))
2. 인접 노드를 순회하면서 아직 방문하지 않은 노드라면 해당 노드를 기준으로 1~2 반복

스택

stack: 방문할 노드를 담은 리스트
visited: 방문한 노드를 담은 리스트
방법:
1. 방문할 노드 리스트가 비어있지 않다면 반복
2. 가장 최근에 삽입된 노드를 꺼내고 방문 처리
3. 꺼낸 노드의 인접 노드를 방문하면서 방문하지 않은 인접 노드는 stack에 추가

DFS 구현 코드

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}

# node: 현재 방문한 노드
# visited: 방문한 노드의 리스트
def dfs_recursive(node, visited):
    # 방문처리
    visited.append(node)

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

    return visited


def dfs_stack(start):
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start]

    # 방문할 노드가 남아있는 한 아래 로직을 반복한다.
    while stack:
        # 제일 최근에 삽입된 노드를 꺼내고 방문처리한다.
        top = stack.pop()
        visited.append(top)
        # 인접 노드를 방문한다.
        for adj in graph[top]:
            if adj not in visited:
                stack.append(adj)

    return visited

BFS

BFS(Breadth First Search): 너비 우선 탐색. 옆으로 갈 수 있을 때까지(너비) 가다가 다시 돌아가는 방식.
Breadth-First-Search-Algorithm.gif

DFS와의 차이점
  • 가장 최근에 삽입된 노드를 꺼내는 게 아닌 맨 처음에 삽입된 노드를 꺼내는 것. (스택이 아닌 큐)

BFS 구현 방법

  1. 루트 노드를 큐에 삽입
  2. 현재 큐의 노드를 추출하여 visited에 삽입
  3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 삽입
  4. 2~3 반복
  5. 큐가 빌 때 탐색 종료

BFS 구현 코드

def bfs_queue(start):
    visited = [start]
    q = deque([start])

    while q:
        node = q.popleft()
        for adj in graph[node]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)

    return visited

백트래킹

필요없는 경우를 가지치기(pruning)하므로써 시간 복잡도를 줄이는 방법.

DFS, BFS와 같은 완전 탐색 기법들을 효율적으로 만들어주는 기법.

DFS와 BFS는 기본적으로 전체 탐색(brute force)이다. 모든 경우의 수를 다 탐색한다는 뜻이다. 하지만 일반적으로 모든 경우의 수를 다 탐색하는 건 가능은 하지만 오래 걸리는 일이다.

백트래킹은 전체 탐색보다 필요가 없는 수는 탐색하지 않는 효율적인 탐색을 하는 것이다.

N-Queen 문제

N-Queen 문제

강의에서 코드를 제공해주고 설명을 해주어서 대충 이해는 했지만 직접 구현은 아직 많이 어려운 것 같다. 내일 다시 처음부터 코드를 잘 살펴보고 새로 구현해보기로 하자.

실습

섬의 개수

풀이:

  1. 전체 맵을 차례대로 모든 요소 방문.
  2. 만약 요소가 1이면 0으로 바꾸고 dfs로 들어가서 인접요소(상하좌우) 확인.
  3. 만약 인접요소 중 1이 있다면 dfs로 계속 방문.
  4. 상하좌우에 0밖에 없으면 dfs 끝내고 섬의 갯수 증가
island_dfs_stack
def island_dfs_stack(grid):
    # dx, dy: 상하좌우의 인덱스
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    # grid의 길이와 높이
    rows, cols = len(grid), len(grid[0])
    # 섬의 개수
    count = 0
    for row in range(rows):
        for col in range(cols):
            # 각 요소를 순회하며 1이 아닐 때는 다음 col로 넘어감
            if grid[row][col] != "1":
                continue

            # 1이라면 무조건 섬의 개수 증가
            count += 1
            # 해당 인덱스를 stack에 저장
            stack = [(row, col)]

            while stack:
                # 가장 최근에 삽입된 인덱스짝 pop
                x, y = stack.pop()
                # 해당 인덱스를 0으로 수정
                grid[x][y] = "0"
                # 상,하,좌,우 총 4개의 위치 확인
                for i in range(4):
                    # nx, ny 상하좌우의 인덱스짝
                    nx = x + dx[i]
                    ny = y + dy[i]
                    # nx나 ny가 범위 밖이거나 해당 인덱스의 값이 1이 아니면 다음 i로 넘어감
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != "1":
                        continue
                    # nx, ny를 stack (grid[nx][ny]는 1임)
                    stack.append((nx, ny))

    return count

def island_dfs_recursive(grid):
    pass
island_dfs_recursive
def island_dfs_recursive(grid):
    # dx, dy: 상하좌우의 인덱스
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    m = len(grid)
    n = len(grid[0])
    count = 0

    def dfs_recursive(r, c):
        # 재귀의 종료 조건: r과 c가 grid의 범위를 벗어나거나 해당 인덱스의 값이 1이 아닌 경우
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != "1":
            return
        # 해당 인덱스의 값을 0으로 바꿈
        grid[r][c] = "0"

        # 현재 인덱스의 상,하,좌,우 인덱스들에 대해 재귀 실행
        for i in range(4):
            dfs_recursive(r + dx[i], c + dy[i])
        return
    
    for r in range(m):
        for c in range(n):
            if grid[r][c] == "1":
                continue

            count += 1
            dfs_recursive(r, c)

    return count
island_bfs_queue
def island_bfs_queue(grid):
    # dx, dy: 상하좌우의 인덱스
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    # grid의 길이와 높이
    rows, cols = len(grid), len(grid[0])
    # 섬의 개수
    count = 0
    for row in range(rows):
        for col in range(cols):
            # 각 요소를 순회하며 1이 아닐 때는 다음 col로 넘어감
            if grid[row][col] != "1":
                continue

            # 1이라면 무조건 섬의 개수 증가
            count += 1
            # 해당 인덱스를 stack에 저장
            q = deque([(row, col)])

            while q:
                # 맨 처음에 삽입된 인덱스짝 pop
                x, y = q.popleft()
                # 해당 인덱스를 0으로 수정
                grid[x][y] = "0"
                # 상,하,좌,우 총 4개의 위치 확인
                for i in range(4):
                    # nx, ny 상하좌우의 인덱스짝
                    nx = x + dx[i]
                    ny = y + dy[i]
                    # nx나 ny가 범위 밖이거나 해당 인덱스의 값이 1이 아니면 다음 i로 넘어감
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != "1":
                        continue
                    # nx, ny를 q (grid[nx][ny]는 1임)
                    q.append((nx, ny))

    return count

페어 프로그래밍

문제풀이

1. 동전 0

내가 생각한 방법과 페어 분이 생각한 방법이 달랐다. 나는 드라이버 역할을 하기로 해서 페어 분의 방법대로 진행했다.

N: 동전의 종류
K: 목표 금액
풀이:
1. 받은 입력들을 역순으로 리스트에 저장 (내림차순)
2. 리스트의 요소들을 순회하면서
2-1. 요소가 K와 같거나 작을 동안 K에서 요소만큼 빼고 count 증가
2-2. K가 0이 되면 반복문 종료

전체 코드

import sys
input = sys.stdin.readline

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

inputs = []

for i in range(N):
    inputs.append(int(input()))


coins = []

for i in range(len(inputs)):
    coins.append(inputs[len(inputs) - 1 - i])

count = 0

for i in coins:
    while i <= K:
        count += 1
        K -= i

    if K == 0:
        break

print(count)

2. 이항 계수 1

이항 계수라는 수학개념을 이해하지 못해도 이항 계수를 구하는 공식만 알면 풀 수 있는 문제다.

이항 정리

위 그림을 코드로 옮기기만 하면 끝이다.

전체 코드

def factorial(n):
    f = 1
    for i in range(n):
        f = f * (i+1)

    return f


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

print(int(factorial(N) / (factorial(K) * factorial(N-K))))

3. 잃어버린 괄호

이 문제 역시 간단하긴 한데 페어 분 덕분에 더 빨리 풀 수 있었다.

exps: 입력받은 문자열
result: 적절한 괄호를 추가해 식의 값을 최소로 만든 값

예시) exps = "55-50+40-30+20-20-20"
풀이:
1. '-'를 기준으로 입력받은 문자열을 자른다. ==> exps = [55, 50+40, 30+20, 20, 20]
2. result에 첫 번째 요소(숫자 혹은 +로 나뉘어진 숫자 리스트)를 넣어준다. ==> result = 55
3. 그 외의 요소(숫자 혹은 +로 나뉘어진 숫자 리스트)는 전부 result에서 빼준다. ==> result = 55 - (50+40) - (30+20) - 20 - 20

전체 코드

exps = input().split('-')

result = sum(list(map(int, exps[0].split('+'))))
for i in range(1, len(exps)):
    result -= sum(list(map(int, exps[i].split('+'))))

print(result)
profile
코이그
COYG🔴⚪
이전 포스트

09. 온보딩 알고리즘 사전스터디 4일차

다음 포스트

11. 온보딩 알고리즘 사전스터디 6일차

0개의 댓글