[Megabyte School : AI 데이터 사이언티스트 취업 완성 과정] Day 43.

 

 

안녕하세요 늑대양입니다 :)

 

 

오늘까지 파이썬 기반 코딩테스트를 학습합니다!! 🤓

 

 

내일부터 본격적으로 ML 학습을 진행합니다!! 🥸

 

 

[AI 데이터 사이언티스트 취업 완성 과정]의 43일차 일과를 정리하여 안내해드리도록 하겠습니다.

 

 

 

 

늑대양 초록 썬더 버전!

 

 

 

 

 

Day 43 시간표:

• 코딩테스트 실전 - 문제풀이
• 코딩테스트 실전 - 문제풀이 (실강)
• 코딩테스트 실전 - 문제풀이

 

 

 

 

코딩테스트 실전 - 이론

그래프

• 그래프는 G(V, E)로 정의하고, V(Vertext : 정점)과 E(Edge : 간선) 의 집합을 의미한다.
• 연결되어 있는 원소들간의 관계를 표현하는 자료구조이다.

 

인접행렬

• 배열을 이용해 그래프를 표현하는 방법

 

1. 무방향 그래프

무방향 그래프의 예시

 

 

 

입력 형식:

edge = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 4]]

 

 

graph = [[0]*(n+1) for _ in range(n+1)] 
for a, b in edge:
    graph[a][b] = 1
    graph[b][a] = 1

 

 

무방향 그래프 표현 예시

 

 

 

2. 방향 그래프

방향 그래프의 예시

 

 

 

입력 형식:

edge = [[1, 2], [1, 3], [2, 5], [3, 4], [4, 2]]

 

 

방향 그래프 표현 예시

 

 

 

3. 가중치 방향 그래프

가중치 방향 그래프 예시

 

 

 

입력형식:
edge = [[1, 2, 2], [1, 3, 4], [2, 5, 5], [3, 4, 5], [4, 2, 2]]

 

 

graph = [[0]*(n+1) for _ in range(n+1)]
for a, b, c in edge:
    graph[a][b] = c

 

 

가중치 방향 그래프 표현 예시

 

 

 

 

인접 리스트

인접 리스트 예시

 

 

 

edges = [[0, 1], [0, 2], [1, 2], [2, 3], [2, 5], [3, 4], [3, 5]]

graph = [[]] for _ in rane(6)]

for a, b in edges:
    graph[a].append(b)
    graph[b].append[a]

[
    [1, 2],
    [0, 2],
    [0, 1, 3, 5],
    [2, 4, 5],
    [3],
    [2, 3]
]

 

 

1. 무방향 그래프

무방향 그래프 예시

 

 

 

입력형식:
edge = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 4]]

 

 

무방향 인접 리스트 그래프 예시

 

 

 

2. 방향 그래프

방향 그래프 예시

 

 

 

입력형식 :
edge = [[1, 2], [1, 3], [2, 5], [3, 4], [4, 2]]

 

 

방향 인접 리스트 그래프 예시

 

 

 

3. 가중치 방향 그래프

가중치 방향 그래프 예시

 

 

 

입력형식:
edge = [[1, 2, 2], [1, 3, 4], [2, 5, 5], [3, 4, 5], [4, 2, 2]]

 

 

graph = [[] for _ in range(n+1)]
for a, b, c in edge:
    graph[a].append((b, c))

 

 

가중치 방향 인접 리스트 그래프 예시

 

 

 

예제

재귀함수

def DFS(n):
    if n == 0:
        return
    else:
        # print(n)
        DFS(n-1)
        print(n, end= " ")

DFS(3)

>1 2 3 %

 

 

 

중복순열

중복순열 예시

 

 

 

중복순열 예시 - 2

 

 

 

중복순열 예시 - 3

 

 

def DFS(L, n, k, p):
    if L == k:
        for x in p:
            print(x, end = " ")
        print()
    else:
        for i in range(1, n+1):
            p.append(i)
            DFS(L+1, n, k, p)
            p.pop()

print(DFS(0, 3, 2, []))


>1 1 
1 2 
1 3 
2 1 
2 2 
2 3 
3 1 
3 2 
3 3 
None

 

 

 

경로 탐색(인접행렬)

answer = 0
path = []

def DFS(v, n, ch, graph):
    global answer
    if v == n:
        answer += 1
        print(path)
    else:
        for i in range(1, n+1):
            if graph[v][i] == 1 and ch[i] == 0:
                ch[i] = 1
                path.append(i)
                DFS(i, n, ch, graph)
                ch[i] = 0
                path.pop()

def solution(n, edge):
    global answer
    graph = [[0] * (n+1) for _ in range(n+1)]
    for a, b in edge:
        graph[a][b] = 1
    
    ch = [0] * (n+1)
    ch[1] = 1
    path.append(1)
    DFS(1, n, ch, graph)
    return answer

print(solution(5, [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]]))


>[1, 2, 3, 4, 5]
[1, 2, 5]
[1, 3, 4, 2, 5]
[1, 3, 4, 5]
[1, 4, 2, 5]
[1, 4, 5]
6

 

 

 

 

경로 탐색(인접 리스트)

answer = 0
path = []

def DFS(v, n, ch, graph):
    global answer
    if v == n:
        answer += 1
        # print(path)
    else:
        for nv in graph[v]:
            if ch[nv] == 0:
                ch[nv] = 1
                path.append(nv)
                DFS(nv, n, ch, graph)
                ch[nv] = 0
                path.pop()

def solution(n, edge):
    global answer
    graph = [[] for _ in range(n+1)]
    for a, b in edge:
        graph[a].append(b)
        
    ch = [0] * (n+1)
    ch[1] = 1
    path.append(1)
    DFS(1, n, ch, graph)
    return answer        

print(solution(5, [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]]))

>6

 

 

 

컴퓨터

cnt = 0
def DFS(v, n, ch, graph):
    global cnt
    cnt += 1
    for nv in graph[v]:
        if ch[nv] == 0:
            ch[nv] = 1
            DFS(nv, n, ch, graph)


def solution(n, edge):
    global cnt
    graph = [[] for _ in range(n+1)]
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
        
    ch = [0] * (n+1)
    ch[1] = 1
    DFS(1, n, ch, graph)
    return n - cnt

print(solution(11, [[1, 2], [1, 4], [2, 3], [4, 5], [5, 6], [7, 8], [7, 10], [8, 9], [10, 11]]))

>5

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다 :)