본문 바로가기

공부/알고리즘6

알고리즘 접근 방법 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.
Integer.valueOf(String) VS Integer.parseInt(String) Integer.valueOf(String)반환 타입: Integer 객체설명: Integer.valueOf(String)는 문자열을 Integer 객체로 변환합니다. 이 메서드는 내부적으로 Integer 객체를 생성하거나, 이미 생성된 객체를 캐싱하여 반환할 수 있습니다. 따라서 이 메서드는 Integer 객체를 반환하기 때문에 자동 박싱(autoboxing)이 발생합니다.캐싱: Integer.valueOf(int)는 -128부터 127까지의 값을 캐싱합니다. 이 범위 내의 값들은 동일한 객체를 재사용합니다.Integer intValue = Integer.valueOf("123"); Integer.parseInt(String)반환 타입: 기본 타입 int설명: Integer.parseInt(String).. 2024. 5. 25.
메모 DFS 는 완전 탐색 BFS 는 최단 거리 찾기에 적합하다. 2023. 2. 26.
최대 공약수(GCD), 최소 공배수(LCM) 구하기, 유클리드 호제법 - JAVA 최대 공약수와 최대 공배수의 개념 1) 공약수 두 정수의 공통 약수를 공약수라고 한다. 두 정수 a, b에 대하여 e가 a의 약수이면서 b의 약수일 때 e를 a, b의 공약수라고 한다. 2) 최대공약수 두 정수의 공약수 중 가장 큰 것을 최대공약수라고 한다. 또한 최대공약수는 다음의 성질을 만족한다. a, b의 최대공약수가 g이다. ⇔ a = ga′, b = gb′이면 a′, b′는 서로소이다. 3) 공배수 두 정수의 공통 배수를 공배수라고 한다. 두 정수 a, b에 대하여 c가 a의 배수이면서 b의 배수일 때 c를 a, b의 공배수라고 한다. 4) 최소공배수 양의 공배수 중 가장 작은 것을 최소공배수라고 한다. [네이버 지식백과] 최대공약수와 최소공배수 (통합논술 개념어 사전, 2007. 12. 15... 2022. 12. 16.

티스토리툴바