그래프 탐색3 [DFS/BFS] 탐색 알고리즘 이해하기, 주요 예시 문제 📌 DFS, BFS에서 중요한, 알아야 할 개념 - 스택 - 큐 - 재귀 함수 📍 반복문, 재귀 함수 2가지 방식으로 구현한 팩토리얼(!) 예제 # 반복적으로 구현한 n! def factorial_iterative(n): result = 1 for i in range(1, n + 1): result *= i return result # 재귀적으로 구현한 n! def factorial_recursive(n): if n 연결 리스트 이용 -> 파이썬 2차원 리스트(append, 메소드 제공) 이용하면 된다. - 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용 -> 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 그래프 그래프는 노드(Node)와 간선(Ed.. 2023. 10. 31. [구름톤 챌린지 WEEK 4 - 그래프 탐색] DAY 20. 연결 요소 제거하기 한 달간 진행됐던 구름톤 챌린지 마지막 날이다! 위 사진은 4주간 모은 캐릭터 아이템 🤣 그동안 완벽히 이해하지 못한 알고리즘 문제들도 있는데 9월 달 내로 다시 리뷰하며 풀어보는 것을 목표로 잡았다. 결과적으로 20개 블록을 모두 모았고, 시작하기 전의 내 알고리즘 실력과 지금을 비교하면 배우면서 더 성장했음을 느낀다! DAY 20. 연결 요소 제거하기 def f(y, x, d): graph[y][x] = d stack = [(y, x)] # 조건을 만족하는 연결 요소이면, 포함되는 모든 칸을 '.'으로 바꾸기 위해 해당 위치 저장할 집합 선언 # + 방문 체크 visited = set() while stack: ey, ex = stack.pop() if (ey, ex) in visited: conti.. 2023. 9. 10. [구름톤 챌린지 WEEK 4 - 그래프 탐색] DAY 16.연합 이번 구름톤 WEEK4 주제는 그래프 탐색이다. DFS, BFS 유형 문제가 너무 약해서 백준 기본 문제부터 공부를 시작하고 응용해보고 있다. 먼저 알고리즘 스터디에서 바이러스, DFS와 BFS 문제를 풀어보며 DFS, BFS로 순회하는 법을 배웠다. 이후에 구름톤 문제를 풀어보니 이에 + 서로 연결되어 있지 않은 연합, 컴포넌트 개수를 세는 문제들이 나왔다. 처음 접하는 유형이라 해설을 참고했다. DAY 16. 연합 import sys from collections import deque input = sys.stdin.readline N, M = map(int, input().split()) graph = [[] for _ in range(N + 1)] visited = [0] * (N + 1) re.. 2023. 9. 6. 이전 1 다음
