본문 바로가기

공부/알고리즘9

파이썬 자주 사용하는 라이브러리 모음 - 코테 꿀팁 1. mathimport mathprint(math.factorial(5)) # 5! = 120print(math.gcd(36, 60)) # 최대공약수(GCD) = 12print(math.sqrt(25)) # 제곱근 = 5.0print(math.ceil(3.1)) # 올림 = 4print(math.floor(3.9)) # 내림 = 32. itertoolsimport itertoolsarr = [1, 2, 3]# 순열 (3개 중 2개를 선택하는 모든 경우) -> 순서 의미 있음print(list(itertools.permutations(arr, 2)))#[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]# 조합 (3개 중 2개를 뽑는 경우) -> 순서 .. 2025. 3. 22.
2D 누적 합(Prefix Sum) 기법 이런게 있더라고요. 2D 누적 합은 이차원 배열(행렬)에서 특정 부분 영역의 합을 빠르게 계산해야 할 때 주로 사용됩니다. 언제 사용 할까요?1. 특정 부분 영역의 합을 자주 계산할 때 (O(1)로 최적화) 기본적으로 특정 부분의 합을 구하려면 O(N*M)이 걸리지만, 누적 합 배열을 미리 만들어두면 O(1)로 구할 수 있음.ex) 2D 배열에서 (r1, c1)부터 (r2, c2)까지의 합을 여러 번 구해야 하는 경우 부분 합 = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1] 2. 다차원 배열에서 특정 범위를 여러 번 업데이트해야 할 때 (차이 배열과 함께 사용) 특정 영역을 업데이트하는 연산이 많을 때, 차이 배열(D.. 2025. 3. 21.
배낭 문제(Knapsack Problem) 제한된 용량을 가진 상태에서 여러 개의 아이템을 선택하여 최대 가치를 구하는 방식입니다. 이때 아이템의 무게를 나눌 수 있는지 없는지로 나눠집니다. 1. 0-1 배낭 문제 각 아이템은 선택하거나(1) 선택하지 않거나(0) 두 가지 경우만 존재할 경우DP를 사용하여 해결하며, 시간 복잡도는 O(nW)문제 정의배낭의 최대 용량이 Wn개의 아이템이 있으며, 각 아이템 i는 무게 w[i]와 가치 v[i]를 가진다.배낭에 넣을 수 있는 최대 가치를 구하는 것이 목표이다. 코드# 0-1 Knapsack Problem (Dynamic Programming)def knapsack_01(W, weights, values, n): dp = [[0] * (W + 1) for _ in range(n + 1)] .. 2025. 2. 28.
알고리즘 접근 방법 1. 문제를 읽고 이해한다.2. 문제를 익숙한 용어로 재정의한다.3. 어떻게 해결할지 계획을 세운다.4. 계획을 검증한다.5. 프로그램으로 구현한다.6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다. 나는 보통 계획을 세운 후(3번) 바로 구현하려고 하는데 검증하는 과정(4번)을 추가해야겠다. 작은 기능에서 시작해서 점차 키워가기 => 점진적 개선문제를 풀 수는 없더라도 해결법을 알아가는데 도움을 줌 2025. 2. 24.
다익스트라(Dijkstra) - Python, heapq 코드import heapqimport sysdef dijkstra(graph, start): INF = float('inf') n = len(graph) distance = [INF] * n distance[start] = 0 pq = [] heapq.heappush(pq, (0, start)) # (거리, 정점) while pq: dist, now = heapq.heappop(pq) if distance[now]  과정  거리 배열 초기화: 시작 정점에서 모든 정점까지의 최단 거리를 무한(∞)으로 설정, 시작 정점의 거리는 0으로 설정우선순위 큐(Priority Queue) 사용: 시작 정점을 큐에 넣음 (우선순위 큐는 Python.. 2025. 2. 7.
유니온 파인드(Union-Find) - Python Why?왜 쓰냐 => 여러 개의 원소가 있을 때 다음 두 가지 작업을 효율적으로 수행하기 위해 사용 Union? Find?1. Union : 두 개의 집합을 합침2. Find : 특정 원소가 속한 집합을 찾음 주로 그래프 알고리즘, 사이클 검출, 최소 신장 트리 등의 문제에 사용  핵심 개념 1. 부모 노드(parent): 각 원소는 자신이 속한 집합을 대표하는 "부모 노드"를 가집니다. 초기에는 모든 원소가 자기 자신을 부모로 가집니다.Find 연산을 통해 부모를 찾을 수 있습니다.  2. 경로 압축(Path Compression): Find 연산을 수행하면서 트리의 깊이를 줄여 효율성을 높이는 기법입니다.경로 압축을 통해 원소들이 직접 루트 노드를 가리키게 되어 Find 연산이 매우 빠르게 수행됩니다.. 2024. 12. 10.

티스토리툴바