Algorithem
실시간으로 변하는 경우 heap으로 중앙값 찾기
중앙값은 기본적으로 정렬된 배열에서 찾는게 정답이긴한데, 실시간으로 원소가 하나씩 추가되는 경우라면? https://o-tantk.github.io/posts/finding-median/ minheap, maxheap 두개를 동시에 돌리면서 찾을 수 있다. 자세한 알고리즘은 링크의 블로그로,,
전체 글
데이터 엔지니어를 희망하는 개발자 지망생Algorithem
트리의 지름 구하기 : 단 두번의 dfs 탐색
트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다: 1. 트리에서 임의의 정점 x를 잡는다. 2. 정점 x에서 가장 먼 정점 y를 찾는다. 3. 정점 y에서 가장 먼 정점 z를 찾는다. 트리의 지름은 정점 y와 정점 z를 연결하는 경로다. https://blog.myungwoo.kr/112
Algorithem
트리의 두번째 지름 : 지름 구하기 3번으로
1. 트리 지름의 양 끝 노드를 구한다. 2. 각각의 노드를 제거한 트리에서 지름을 구한다. 3. 둘 중 긴 거리가 두번째 지름이다.
Algorithem
수학 : 최대공약수와 최소공배수, 소수 구하기
최대공약수 GCD - 유클리드 호제법 O(logn) r = a%b gcd(a,b) = gcd(b, r) ... r == 0 -> b 는 최대공약수 반복문 혹은 재귀로 해결 가능하다. 최소공배수 LCM lcm = a*b/gcd 소수 1. N이 소수인지 체크하기 - 2~[루트N] 으로 나누었을 때 나누어 떨어지는게 있는지 확인 O(루트N) 2. 에라토스테네스의 체 O(nloglogn) 2~N 까지 모든 숫자를 적어놓고 가장 작은 수 ( = 소수) 의 배수들을 모두 지운다.
Algorithem
최장 공통 부분 수열 (LCS) : 다이나믹, 2차원배열, 역추적
[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence (velog.io) 백준 #17219 비밀번호 찾기
Algorithem
최단경로탐색 : 벨만포드, 다익스트라, 플로이드와샬
백준 #1238 - 파티 벨만포드 : 한 점에서 다른 점들로 이동하는 최단 거리 계산 다익스트라 : 한 점에서 다른 점들로 이동하는 최단 거리 계산 한번도 도달하지 못한 점이거나, 해당 점에서의 최단거리가 갱신되면 거기서 dfs를 돌리는 방식으로도 해결 가능. 일종의 벨만포드에 속할듯? 벨만포드 : 모든 간선에 대해 더 짧게 갱신할 수 있는 거리를 모두 갱신해준다. n-1번 (최단 경로 중 가장 많이 간선을 선택하는 경우가 n-1개) 반복. 효율 개선법 1. 더이상 갱신되는게 없으면 종료 효율 개선법 2. SPFA(Shortest Path Faster Algorithm) 거리를 줄이는데 사용될 수 있는 노드를 별도의 큐로 관리하고 그 노드만 처리한다. 특징 : 음수 간선을 포함한 사이클이 있다면 사용..