분류 전체보기 (61) 썸네일형 리스트형 위상정렬 (Kahn’s Algorithm) 구현 그래프는 방향 그래프(DAG) 이어야 함.간선 A → B는 "A가 B보다 먼저 처리되어야 한다"는 의미.진입차수(in-degree) 를 이용해서 BFS로 정렬을 수행함.from collections import deque# 입력: 정점 수(n), 간선 수(m)n, m = map(int, input().split())# 인접 리스트로 그래프 표현 (1번부터 시작)graph = [[] for _ in range(n + 1)]# 각 정점의 진입차수 저장용 배열indegree = [0] * (n + 1)# 간선 정보 입력 처리for _ in range(m): a, b = map(int, input().split()) graph[a].append(b) # A → B (방향 그래프) indeg.. 백준(Python) 2667 : 단지번호붙이기 단지번호붙이기문제과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.입력첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.출력첫 번째 줄에는 총 단지수를 출력하시오. 그리고 .. DFS / BFS 구현 공통적인 부분from collections import deque# 1. 입력 처리n, m = map(int, input().split()) # 정점 수 n, 간선 수 mgraph = [[] for _ in range(n + 1)] # 정점 번호를 1번부터 쓰기 위해 n+1 크기로 만듦# 2. 간선 정보 입력 받아서 그래프 구성 (무방향 그래프)for _ in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u)# (선택) 정점들을 정렬해주면 DFS/BFS 순서가 일정하게 나옴for g in graph: g.sort() DFSdef dfs(graph, visited, v): visit.. LIS (Longest Increasing Subsequence) 가장 긴 증가 부분 수열수열: [10, 20, 10, 30, 20, 50]LIS = [10, 20, 30, 50]길이 = 4 기본 DP 풀이 (O(n²))def LIS(arr): n = len(arr) dp = [1] * n # 자기 자신만 있을 때 LIS 길이 = 1 for i in range(n): for j in range(i): if arr[j] 이진 탐색 활용 (O(n log n))매우 빠르지만 실제 수열을 구하기는 불가능. 길이만 가능하다import bisectdef LIS(arr): sub = [] for num in arr: index = bisect.bisect_left(sub, num) .. 그래프 탐색 | DFS/BFS 1. 그래프의 정의그래프는 정점(Vertex)들과 그 정점들을 잇는 간선(Edge)으로 이루어진 자료구조 G = (V, E)V: 정점들의 집합 (예: 도시, 사람 등) | V = {0, 1, 2, 3}E: 정점들을 연결하는 간선의 집합 (예: 도로, 친구 관계 등) | E = {, } “연결 관계”가 있을 때 그래프를 쓰면 좋다 그래프의 종류간선 방향비방향 그래프간선에 방향이 없음 (서로 왕래 가능)〃방향 그래프간선에 방향이 있음 (A → B)간선 가중치가중치 그래프간선마다 비용이 있음 (예: 거리, 시간 등)〃비가중치 그래프간선에 별도의 가중치가 없음그래프 용어 정리경로(Path)정점을 연결하는 간선들의 연속사이클(Cycle)한 정점에서 출발해서 다시 돌아오는 경로차수(Degree)한 정점에 연결된 간.. 동적 프로그래밍(DP : dynamic programming) 큰 문제를 작은 문제로 나누어 해결한 후, 그 결과를 저장하여 재사용하는 방식 동적 프로그래밍 알고리즘의 개발 절차 step 1 : 큰 문제에 대한 해와 작은 문제에 대한 해 사이의 재귀관계식 구하기 step 2 : 작은 문제의 해를 큰 문제의 해결에 사용 항상 최적값을 먼저 구하고 난 후, 최적해를 역으로 구축해야 함분할정복 vs 동적 프로그래밍피보나치 수열1. 분할 정복 방식 (재귀)def fib1(n): if n == 0 or n == 1: # n이 0 또는 1이면 그대로 반환 (기저 조건) return n return fib1(n-1) + fib1(n-2) # f(n) = f(n-1) + f(n-2)를 그대로 재귀 호출❌ 단점: 중복 호출이 많아 비효율적 (지수 .. 파이썬 라이브러리 heapq 1. 파이썬에서 힙(Heap) 자료구조를 쉽게 다룰 수 있게 해주는 표준 라이브러리이다2. 기본적으로는 최소 힙(min-heap) 구조를 사용 한다3. 우선순위 큐(Priority Queue)를 구현할 때 자주 활용한다 기본 특징최소 힙(min-heap) 기반 (가장 작은 값이 루트)**배열(list)**을 힙처럼 다룸 → 별도의 자료구조 없이 사용 가능삽입, 삭제 연산이 **O(log n)**으로 효율적최대 힙은 직접 구현하거나 음수 값 활용 주요 함수 설명heapq.heapify(list)일반 리스트를 힙 구조로 변환heapq.heappush(heap, item)힙에 새 아이템 추가heapq.heappop(heap)가장 작은 아이템 제거하고 반환heapq.heappushpop(heap, item)it.. 최적화 문제 해결 : 브루트포스부터 탐욕 알고리즘 1. 최적화 문제란? 정의:조건을 만족하는 여러 후보 해답 중에서 최적(최대 또는 최소)의 해답을 찾는 문제.예시:최단 경로 문제: 두 정점 사이의 가장 짧은 거리.배낭 문제(Knapsack):0-1 배낭 문제: 물건을 하나씩만 선택 (쪼갤 수 없음).연속 배낭 문제: 물건을 쪼개서 선택 가능 (fractional).해법 종류:완전 탐색( brute-force search ): 모든 가능한 경우를 탐색 → 지수 시간 소요.효율적인 알고리즘 설계 기법:동적 프로그래밍(DP)탐욕적 알고리즘(Greedy)가능한 경우 다항 시간 알고리즘 사용.NP-완전 문제(NP-complete):아직 다항 시간 알고리즘 없음.예: 외판원 문제(TSP), 부분집합 합 문제 등.해결 방법:상태공간 트리 탐색: 백트래킹, 분기 한.. 이전 1 2 3 4 ··· 8 다음
