EDOC 2022.08 2주차

-다이내믹 프로그래밍-

 

 다이내믹 프로그래밍은 재귀- 문제를 해결하는 방법으로 큰 문제를 작은 부분 문제로 나눈 다음, 부분 문제의 결과를 사용하여 큰 문제를 해결하는 데에 사용하는 것-에 대한 최적화이다. 다이내믹 프로그래밍은 사실 중복된 (곧 해결될)부분 문제subproblem가 있다면 이에 대한 결과를 저장하고 동일한 부분 문제가 다시 발생한다면, 이 결과를 재사용하는 것이다. 이 아이디어로 시간과 비교 횟수를 절약해준다.

참고 블로그 : https://ratsgo.github.io/data%20structure&algorithm/2017/11/15/dynamic/

다이내믹 프로그래밍 · ratsgo's blog

 

DFS-깊이 우선 탐색 알고리즘

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

BFS - 넓이 우선 탐색

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

---

<백준 2667번 - 단지 번호 붙이기>

정말.. 어케 짜야 할지 모르겠어서

https://hongcoding.tistory.com/71 감사합니다..

[백준] 2667 단지번호붙이기 (Python 파이썬)

from sys import stdin
from collections import deque
n = int(stdin.readline())
graph =[]
num =[]

for i in range(n):
    graph.append(list(map(int, stdin.readline())))# list()안에 list()로 2차원 하는구남
dx = [0,0,1,-1]
dy = [1, -1, 0, 0]

def DFS(x,y):
    if x<0 or x>=n or y<0 or y>=n:
        return False #대문자
    if graph[x][y] == 1:
        global count 
        count += 1
        graph [x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            DFS(nx, ny)
        return True
    return False
count = 0
result = 0

for i in range(n):
     for j in range(n):
        if DFS(i, j) == True:
            num.append(count)
            result += 1
            count = 0

num.sort()
print(result)
for i in range(len(num)):
    print(num[i])

보고 한줄한줄 쳤는데 저 디에프에스함수가 이해가 안된다..

성장해서 돌아오겟다

---

dfs bfs 말고 다른 알고리즘으로 푼 연희 언니 코드!

인접해있는 집들의 단지의 개수를 합집합으로 구함

union find(조금 다름) 사용

#정연희
from sys import stdin

parent = []
map = []


def find(a):
    a_root = parent[a]
    if a_root != a:
        temp = a_root
        while temp != parent[temp]: #바로 위 부모 노드가 아닌 루트를 가리키도록 매번 업데이트
            temp = parent[temp]
        parent[a] = temp
        return temp
    else:
        return a_root


def union(a, b):
    a_root = find(a)
    b_root = find(b)
    if a_root != b_root:
        parent[a_root] = b_root


def checkTown(h_r, h_c, n):
    for r, c in zip((h_r, h_r, h_r - 1, h_r + 1), (h_c - 1, h_c + 1, h_c, h_c)):
        if 0 <= c < n and 0 <= r < n:
            if map[r][c] == 1:
                union(r * n + c, h_r * n + h_c)


if __name__ == '__main__':
    n = int(stdin.readline())
    parent = [i for i in range(n * n)]
    town = {}

    for _ in range(n):
        map.append([int(i) for i in stdin.readline().rstrip()])

    for r in range(n):
        for c in range(n):
            if map[r][c] == 0:
                parent[r * n + c] = -1
            else:
                checkTown(r, c, n)

    for i in range(len(parent)):   #혹시 몰라 모든 노드가 루트를 가리키도록 다시한번 업데이트
        if parent[i] != -1:
            find(i)

    for t in parent:
        if t != -1:
            try:
                town[t] += 1
            except KeyError:
                town[t] = 1

    town = sorted(town.items(), key=lambda x: x[1])
    print(len(town))
    for t in town:
        print(t[1])

---

-그래프 / 트리-

 

 

-그래프는 노드와 노드를 연결하는 간선들로 구성된 자료구조이다.

-트리는 정점(Node)와 선분(Branch)을 이용하여 사이클이 이루어지지 않게 구성된 자료구조이다.

 

https://gusrb3164.github.io/computer-science/2021/04/16/graph,tree/

그래프와 트리의 정의 및 차이점

https://bamdule.tistory.com/68

[자료구조] 트리와 그래프

---

<백준 1010번 다리 놓기>

수학적 지식을 이용해서 푼다

조합-팩토리얼 사용

M 개 중에서 N 개 뽑기, 다리가 겹치면 안 되므로 중복 제거 mCn

from sys import stdin
T = int(stdin.readline())

def factorial (n,m):
    # m!/(m-n)!*n!
    mr = 1
    mnr = 1
    nr = 1
    for i in range(1,m+1):
        mr *= i
    for i in range(1, m-n+1):
        mnr *= i
    for i in range(1,n+1):
        nr *= i
    return int(mr / (mnr*nr))

for i in range(T):
    N, M = map(int, stdin.readline().split())
    result = factorial(N,M)
    print(result)

return값을 그냥 mr / (mnr*nr) 로 했더니 소수점 자리까지로 출력되어 나왔다 ( 1.0 , 5.0 이렇게 )

int()로(정수) 감쌌더니 해결되었다. 왜 그런거지?

 

백준에서 맞았지만  찾아보니 더 좋은 방법들이 있다

함수를 팩토리얼 함수로만 만들기

from sys import stdin
T = int(stdin.readline())

def factorial (n):
    mr = 1
    for i in range(1,n+1):
        mr *= i
    return mr

for i in range(T):
    N, M = map(int, stdin.readline().split())
    result = int(factorial(M)/ (factorial(M-N)*factorial(N)))
    print(result)

math 모듈 import하기

factorial 

from sys import stdin
import math

T = int(stdin.readline())

for i in range(T):
    N, M = map(int, stdin.readline().split())
    result = int(math.factorial(M) / (math.factorial(N) * math.factorial(M-N)))
    print(result)

comb()

import math
T = int(input())
for i in range(T):
    N, M = map(int,input().split())
    print(math.comb(M,N))

근데 그래프랑 트리를 어디서 어떻게 배워야 하는 거지?

 

끝