📊 Algorithm/Algorithm 주제별 정리45 🧚♂️알고리즘🧚♂️ - 그래프 - 최소신장트리 🧚♂️최소신장트리 (최소 스패닝 트리)🧚♂️ "모든 노드"를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리 - 사이클을 포함하지 않는다 ( == 이미 방문한 노드를 다시 방문하지 않는다) - 최소 신장 트리를 구성하는 에지의 개수는 항상 "전체 노드의 개수" -1 => 사이클을 알기 위한 유니온 파인드 알고리즘(find 연산)을 구현해야 함 => 에지 중심이므로 에지 리스트로 구현해야 함 1. 에지 리스트로 그래프 구현 / 유니온 파인드 리스트 초기화 2. 에지 리스트의 그래프 데이터를 가중치 기준 오름차순 정렬하기 3. 가중치가 낮은 에지부터 연결 시도하기 - 연결 에지가 N-1이 될 때까지 반복하기 🥇골드 4 (기본 정석 문제!) 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 .. 2023. 7. 15. 🧚♂️알고리즘🧚♂️ - 그래프 - 플로이드 워셜 🧚♂️플로이드 - 워셜🧚♂️ 모든 노드 간 최단 경로 탐색 (음수 가중치 있어도 가능) (종적 계획법(DP) 원리 이용) 시간복잡도 : O(V^3) 노드 개수의 범위가 작아야 함. (모든 노드부터 모든 노드까지의 최단거리 구하기 때문. 시작노드 하나부터 모든 노드까지의 최단 구하는 다익스트라/벨만포드 와는 다름) 최단 경로 위에 어떤 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로임. => 전체 경로의 최단 경로는 부분 경로의 최단 경로 조합으로 이뤄진다. -> 점화식 : "S에서 E까지의 최단 거리" = Math.min("원래 S에서 E까지의 최단 거리", "S에서 K까지의 최단 거리"+"K에서 E까지의 최단 거리") ! 중간다리(K,연결지점) 에 핵심이 있는 알고리즘 1. 리스트 선언하.. 2023. 7. 12. 🧚♂️알고리즘🧚♂️ - 그래프 - 벨만 포드 🧚♂️벨만-포드🧚♂️ 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 "음수 가중치 에지" 가 있어도 수행 가능! 전체 그래프에서 "음수 사이클의 존재 여부" 판단 가능! 다익스트라는 음수 있으면 불가!! 세으니 추천글 [알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 벨만-포드 알고리즘(Bellman-Ford Algorithm)이란? velog.io 1. 에지 리스트 이용해서 그래프를 구현하고 최단 경로 리스트(결과) 초기화 2. 모든 에지를 확인해 정답 리스트 업데이트하기 노드 개수 -1 만큼 업데이트 진행 ( 두 노드 사이 거리는 "노드 개수 -1" 이 최대이기 때문) '종료노드의 결과 리스트값'이 '시작 노드의 결과 리스트값' + '가중치'보다 클 때 이 값.. 2023. 7. 8. 🧚♂️알고리즘🧚♂️ - 그래프 - 다익스트라 Dijkstra Algorithm 그래프에서 최단 거리를 구하는 알고리즘 특정 노드에서 다른 노드들의 최단 거리 구하기 기능 출발 노드와 모든 노드 간의 최단 거리 탐색 특징 에지가 모두 양수 시간 복잡도 O(에지 수*log(노드수)) 최단거리 구하기이기 때문에 BFS와 상당히 유사 (큐 이용/방문리스트활용) 그 세부 버전 같기도(최단거리 계산 추가된) 🥇골드5 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1) 거리 리스트에서 방문하지 않은, 현재 값이 가장 작은 노드.. 2023. 7. 5. 🧚알고리즘🧚-그래프- 위상 정렬 🧚위상 정렬🧚 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 시간 복잡도 : O(노드 수 + 에지 수) 사이클이 존재하면 안 됨 -> 노드 간의 순서를 명확하게 정의할 수 없기 때문 위상 정렬이 늘 같은 정렬 결과를 보장하지는 않음(위상이 같은 노드가 존재할 시) 진입 차수(in-degree) : 자기 자신을 가르키는 에지의 개수 1. 인접 리스트를 만든 후 이를 이용해 진입 차수 리스트를 만든다. 2. 진입 차수가 0인 노트를 선택하고 -> 선택된 노드를 결과 리스트에 저장 / 인접 리스트에서 선택된 노드들의 진입 차수를 1씩 빼기 3. 모든 노드가 정렬될 때까지 2 반복하기. (0이 생기지 않는 경우 없음) 🥇골드 3 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(.. 2023. 7. 1. 🧚알고리즘🧚-그래프- 유니온 파인드 🧚유니온 파인드🧚 두 노드가 같은 그래프에 속하는지 판별하는 그래프 알고리즘 union 연산 : 각 노드가 속한 집합을 하나로 합치는 연산 1. 리스트를 자신의 인덱스값으로 초기화하기 2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 연산을 수행 (인덱스값과 밸류값이 같지 않을 시 대표 노드가 아니므로 대표노드를 찾을 때까지 수행하여 그 값을 밸류값에 넣기) find 연산 : 특정 노드가 속한 집합의 대표 노드를 반환하는 연산 1. 대상 노드 리스트의 '인덱스값==밸류값' 인지 확인 2. 아닐 시 밸류값이 가진 값을 인덱스값으로 한 노드로 이동 3. '인덱스값==밸류값' 일 때까지 1,2를 반복(재귀함수) 4. 대표 노드를 발견하면 거쳐나온 모든 노드의 밸류값을 대표 노드값으로 변경! 시간 복.. 2023. 6. 28. 🧚♂️알고리즘🧚♂️ - 그래프 - 그래프기초 🧚🏻♀️그래프🧚🏻♀️ 노드 : 데이터를 표현하는 단위 에지 : 노드를 연결 🧚🏻♀️그래프 구현법🧚🏻♀️ 1. 에지 리스트 에지를 중심으로 그래프 표현 [출발 노드 / 도착 노드 / (가중치가 있을 시) 가중치] 로 표현 + 벨만 포드 알고리즘 / 크루스칼 알고리즘 등에 사용(노드 중심 알고리즘엔 잘 사용되지 않음) 2. 인접 행렬 노드를 중심으로 그래프 표현 가중치가 존재할 시 1 대신 가중치로 표현 + 노드 개수에 비해 에지가 적을 때는 비효율적 3. 인접 리스트 인덱스 번호의 리스트에 인접한 노드를 다 넣어두기 가중치가 있을 시 [(a,b),(c,d)] 형태로 저장 + 젤 편한 듯 리스트에 같은 값 쉽게 넣는 방법 ([0,0,0] 예시) 1. [0]*3 2. [0 for _ in range(3.. 2023. 6. 24. 🧚♂️알고리즘🧚♂️ - 정수론2(유클리드 호제법) 🔢유클리드 호제법🔢 두 수의 최대공약수 gcd()를 구하는 알고리즘 🍀기본 방법 소인수 분해를 이용 / 공통된 소수들의 곱 구하기 🍀유클리드 호제법 1 ) 큰 수를 작은 수로 나누는 MOD 연산 수행 2 ) 앞 단계에서의 작은 수와 MOD 연산 결과값(나머지)로 MOD 연산 수행 3 ) 단계 2를 반복하다가 MOD 값이 0이 되는 순간의 작은 수가 최대공약수 + MOD 연산 : 두 값을 나눈 나머지를 구하는 연산 (%) + 최소공배수 : 두 수의 곱을 최대공약수로 나누면 됨 최대공약수/ 최소공배수 구하는 보편적 코드 # 최대공약수 def gcd(n, m): for i in range(min(n,m),0,-1): if n%i ==0 and m%i==0: return i # 최소공배수 def lcd(n, m.. 2023. 5. 26. 🧚♂️알고리즘🧚♂️ - 정수론1(소수,오일러 피) 🌊정수론 - 수의 성질을 탐구하고 공부하는 분야 🌊 🔢소수 구하기🔢 소수: 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수. (1과 자기 자신 외에 약수가 존재하지 않는 수) 소수 구하기의 핵심 이론 에라토스테네스의 체 1. 구하고자 하는 소수의 범위만큼 1차원 리스트 생성 2. 2부터 시작하여 지워지지 않은 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지운다. 3. 리스트의 끝까지 2번을 반복한 후 리스트에 남아 있는 수를 출력한다. 에라토스테네스의 체 시간복잡도 O(N^2) 같겠지만 일반적으로 O(Nlog(logN))이라고 한다. 왠지 이해가 안 돼서 검색해봤더니 Sieve of Eratosthenes - Wikipedia From Wikipedia, th.. 2023. 5. 9. 🧚♂️알고리즘🧚♂️ - 이진탐색 이진 탐색(이분 탐색) 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음 기본 틀 1. 데이터 오름차순(내림차순) 정렬하기 2. 현재 데이터셋의 중앙값(mid) 선택 3. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다. (mid값을 바꾸는 방법 사용) 4. 중앙값 이진탐색 알고리즘 사용 중간값 = 블루레이의 크기 블루레이의 크기가 될 수 있는 최솟값 = 최대 길이의 레슨시간 = 시작인덱스 블루레이의 크기가 될 수 있는 최댓값 = 최대 길이의 레슨시간 = 종료인덱스 중앙값(블루레이) 크기로 모든 레슨을 저장할 수 있다면 종료인덱스 = 중앙값-1 중앙값(블루레이) 크기로 모든 레슨.. 2023. 3. 1. 이전 1 2 3 4 5 다음
