본문 바로가기

Algorithms102

[백준 11725번] 트리의 부모 찾기 🤯 문제 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 예제 입력 1에 대한 트리 1 / \ 6 4 / / \ 3 7 2 / 5 BFS import sys input = sys.stdin.readline from collections import deque # 노드의 개수 N (2 ≤ N ≤ 100,000) N = int(input().rstrip()) tree = [[] for _ in range(N+1)] for i in range(1, N): a, b = map(int, input().split()) tree[a].append(b) tree[b].append(a) .. 2024. 3. 15.
[백준 2468번] 안전 영역 - Python 문제 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 from collections import deque import sys input = sys.stdin.readline N = int(input()) max_rain = 0 graph = [] for _ in range(N): row = list(map(int, input().split())) graph.append(row) max_row = max(row) max_rain = max(max_rain, max_row) now_rain = 1 max_safe.. 2024. 3. 14.
[백준 2589번] 보물섬 - PyPy3 문제 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 예전에 푼 문제인데 오랜만에 다시 푸니 이틀 정도 애먹었다.. python으로 제출시 시간 초과가 나서 PyPy3로 제출. 풀이 # 2589번 보물섬 # 육지 L, 바다 W # 상하좌우 육지 이동 가능, 한 칸 이동시 한 시간 # 보물 -> 서로 간에 최단 거리로 이동(BFS)하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있음. # -> 끝에서 끝으로 이동시 서로 가장 긴 시간이 걸리는 육지에서 최단거리를 구해라! (완전 탐색) # 보물이 묻혀 .. 2024. 3. 14.
[백준 11724번] 연결 요소의 개수 - Python, DFS/BFS 문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 정점(N)과 간선(M)의 개수가 주어질 때 연결 요소의 개수를 구하라. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 간선 u, v (1 ≤ u, v ≤ N, u ≠ v) 대표적인 DFS/BFS 문제이다. 시간 제한 3초, 메모리 제한 512 MB에 주의해야 한다. 풀이 ✏️ DFS import sys input = sys.stdin.readline sys.setrecursion.. 2024. 3. 12.
[백준 2667번] 단지번호붙이기 - Python 문제 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 # 1 - 집이 있는 곳, 0 - 집이 없는 곳 # 단지 수 출력, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력해라. import sys input = sys.stdin.readline # 정사각형 지도 크기 n = int(input()) square_map = [] for i in range(n): square_map.append(list(map(int, input().rstrip()))) cnt = 0 result = 0 def dfs(x.. 2024. 3. 9.
[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.

티스토리툴바