목록개인 공부/알고리즘 (6)

hyunjin

imos 알고리즘 - 누적합 문제 효율적으로 푸는 방법

imos - 예제 문제 백준 20440 , 백준 3020,  백준 5541, 백준 16436, 카카오 파괴되지 않은 건물  imos (Indexed Modification of Sums)법특정 구간을 빠르게 업데이트하고, 이를 통해 누적합을 구할 때 유용한 알고리즘 핵심은 업데이트 구간을 배열에 기록 후, 누적 합을 통해 최종 값을 계산 이외에서 육각형 좌표계 등 다양한 특수 좌표계에서 써먹을 수 있다. 수직선 위에 선을 여러 개 그어서, 가장 선이 많이 겹치는 부분 찾는 것 정해진 구간 내에서 시작과 끝이 포함된 부분 집합에 대한 명령이 여러 개 들어올 때, 반복적으로 연산하게 되면 연산 시간이 매우 커질 수 있다.  O(QN)상황 예시를 들어보면,아래는 0 ~ 16 시 까지 한 장소에 대해 N명의 사..
개인 공부/알고리즘 2024. 6. 30. 14:00
[C++] DFS 깊이 우선 탐색 알고리즘

깊이 우선 탐색 (Depth - First Search) 개념 DFS(깊이 우선탐색) : 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 현재 정점에서 다음 분기로 넘어가기 전에 해당 분기를 완변하기 탐색 노드를 깊게 탐색 DFS 장점 1. 현재 경로상의 노드들만 기억하면 되므로, 저장 공간 수요 비교적 적음 2. 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음 3. 구현이 BFS보다 간단 DFS 단점 1. 단순 검색 속도는 BFS 보다 느림 2. 사전에 임의의 깊이를 지정 후 탐색하고, 목표 노드를 발견하지 못할 경우 다음 경로 탐색하도록 하는 것이 좋음 3. 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로 , 구한 해가 최단 경로가 된다는 보장이 없음. (목표에 이르는 경로가 다수인 ..
개인 공부/알고리즘 2021. 2. 18. 21:32
[C++] BFS 너비 우선 탐색 알고리즘

너비 우선 탐색 (Breadth - First Search) 개념 BFS(너비우선탐색) : 현재 정점에서 연결된 가까운 점들 부터 탐색 가까운 정점 먼저 방문 후 멀리 떨어져 있는 정점 나중에 방문 노드를 넓게(wide) 탐색 주로 두 노드 사이 최단 경로 혹은 임의의 경로 찾고 싶을 때 사용 응용하면 미로찾기 같은 알고리즘도 구현 가능 BFS 장점 1. 노드 수 적고 깊이 얕은 경우 빠름 2. 단순 검색 속도가 DFS 보다 빠름 3. 너비 우선 탐색하기 때문에 답이 되는 경로가 여러 개인 경우라도 최단 경로임을 보장 4. 최단 경로가 존재한다면 어느 한 경로가 무한히 깊어져도 반드시 최단 경로 찾을 수 있음 BFS 단점 1. 재귀 호출의 DFS 와 달리 큐에 다음에 탐색할 정점들을 저장해야해 저장 공간..
개인 공부/알고리즘 2021. 2. 18. 13:14
유클리드 호제법 알고리즘, 최대공약수, 최소공배수

유클리드 호제법이란? 두 수의 최대 공약수를 구하는 알고리즘의 하나. 2개 자연수 a, b ( a > b )에 대해 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 또 다시 b , r 에 대해 b를 r로 나눈 나머지 r' 을 가지고 위의 과정을 반복해 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수. ( a , b ) = ( b , r (=a%b) ) = ( r , r' ) ( 1071 , 1029 ) = ( 1029 , 42 ) = ( 42 , 21 ) = ( 21 , 0 ) = 21 21은 1071과 1029의 최대 공약수 GCD 관련 법칙 GCD( u , v ) = GCD( u - v, v ) if u < v GCD( u, v ) = GCD(..
개인 공부/알고리즘 2021. 2. 16. 18:49
insertion sort(삽입 정렬) 알고리즘

데이터 정렬 이유 : 탐색을 위해서 (정렬이 탐색보다 시간이 덜 걸린다 했나?..) 1. 삽입 정렬(Insertion Sort) 두 번째 원소부터 맨 마지막 원소까지 각 원소가 왼쪽에 있는 모든 원소 보다 크거나 같을 때 까지 왼쪽으로 이동 현재 위치보다 아래쪽 순회하며 알맞은 위치에 넣는 정렬 //insertion sort #include using namespace std; template void insertSort( Vector* v, const int l, const int r){ for(int i = l+1 ; i left && v[j] < v[j-1] ; j--){ swap(v[j-1],v[j]); } } } 이미 정렬되어 있는 자료 구조에선..
개인 공부/알고리즘 2021. 2. 9. 20:12
Dynamic Programming이란?

1. Dynamic Programming(동적 계획법) 이란? 큰 문제를 작은 문제로 나누어 푸는 문제 1.1 Divide&Conquer(분할정복) 과 다른 점은? 거의 비슷하지만 결정적 차이가 있다. 작은 문제가 중복이 일어나나는 아닌지 분할 정복 큰 문제를 해결하기 어려워 단순히 작은 문제로 나누어 푸는 방법 작은 문제에서 반복이 일어나는 부분이 없다 DP 작은 부분 문제들이 반복되는 것(답이 바뀌지 않는다.)을 이용해 풀어나는 것 1.2 Dynamic Programming 방법 모든 작은 문제들은 한 번만 풀어야함. 정답을 구한 작은 문제들을 어딘가에 메모해놓고 다시 그보다 큰 문제 풀어나갈 때 똑같은 작은 문제가 나타나면 앞에서 메모한 작은 문제의 결과값 이용 1.3 Dynamic Programm..
개인 공부/알고리즘 2021. 2. 3. 10:44
이전 Prev 1 Next 다음