최대 힙을 구현해보자힙은 이진트리로 구현하는 우선순위 큐 이다. (이진트리는 배열로)삽입 O(lgN), 삭제 O(lgN) 힙의 삽입힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입한다.새로운 노드를 부모 노드들과 교환한다.static void add(int x){ tree[++size] = x; int idx=size; while(idx >1){ if(tree[idx] 힙의 삭제최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다. (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것)삭제된 루트 노드에는 힙의 마지막 노드를 가져옴힙을 재구성static int remove(){ if(size == 0) return 0; int top = tree[1]..

이분 탐색에서 언제나 헷갈리는 경계값 lower_bound / upper_boundlower_bound(k): k 이상의 수가 처음 등장하는 위치upper_bound(k) : k 초과의 수가 처음 등장하는 위치 lower bound를 구하는 함수를 만들어보자 mid 위치의 값이 K와 같더라도, 왼쪽으로 범위를 줄인다.더 앞쪽에 K 이상인 값이 존재할 수 있으므로K 이상(≥ K)이 처음 등장하는 위치를 찾는 것이 목적def lower_bound(N, arr, K): answer = N # 못 찾으면 N (arr 끝 다음 위치) l = 0 r = N - 1 while l https://school.programmers.co.kr/learn/courses/30/lessons/..

작업들 사이에 선후관계가 존재할 때,그 선후관계를 유지하면서 전체 작업의 수행 순서를 그래프를 이용해 정렬하는 알고리즘이다.입력값 1 4는 1번 작업을 먼저 수행한 뒤 4번 작업을 수행해야 한다는 의미방향 그래프로 1→4가 된다5→4도 마찬가지 방향 그래프로 표현 가능즉, 입력으로 주어진 작업 순서 정보들을 이용해 방향 그래프를 구성한다.예를 들어 4번 작업은 여러 작업으로부터 영향을 받는 노드이며, 연결된 간선이 총 3개이다. (차수는 3) 노드로 들어오는 간선의 개수를 진입 차수라고 하며,토폴로지 정렬에서는 진입 차수가 중요하고, 나가는 간선은 상대적으로 중요하지 않다.4번 노드의 진입 차수는 2이다. 4번 작업으로 들어오는 간선을 가진 작업들이 모두 먼저 끝나야만 4번 작업을 수행할 수 있다.따라서..

그래프에서 모든 정점에서 모든 정점 쌍 사이의 최단 거리(최소 비용)를 구하는 알고리즘다익스트라 알고리즘과 벨만-포드 알고리즘은 특정 한 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 거였다. 출발 정점, 도착 정점을 모두 고려해야 하므로 DP 테이블은 2차원으로 구성되어야 한다. 그리고 최단 거리 갱신을 위한 점화식이 필요하다.2차원 형태의 dis 배열 준비 dis[i][j]는 i번 노드에서 j번 노드로 이동하는 데 드는 최소 비용초기에는 dis 테이블을 인접 행렬 기준으로 초기화한다. 이는 중간에 어떤 노드도 거치지 않고 i에서 j로 바로 가는 경우의 비용을 의미한다. 예를 들어, dis[1][2]에는 1번 노드에서 2번 노드로 직접 이동할 때 드는 비용을 기록한다.마찬가지로 2- >4 는 1..

최소 비용으로 출발 정점에서 도착 정점으로 가는 방법을 찾는 것, 근데 간선에 음수가 존재한다.여기서는 출발 정점 1, 도착 정점 5먼저 간선을 1번만 사용해서 갈 수 있는 경로가 있다고 가정하고 계산해 보고,그다음엔 간선을 2번 사용해서 갈 수 있다고 가정하고 또 계산해 본다.만약 간선을 2번 사용해서 가는 경로가 더 좋다면(dist가 더 작다면) 그 값으로 갱신한다.이런 식으로 반복.그럼 이 과정을 몇 번까지 반복하느냐?정점이 5개라면, 최단 경로에서 사용할 수 있는 간선의 최대 개수는 4개(V-1)이다.예를 들면 1→2→3→4→5처럼 모든 정점을 한 번씩 거쳐 가는 경우가 간선을 가장 많이 사용하는 경우다. 음의 사이클이 존재면 안된다는 전제 조건이 있다.만약 음의 사이클이 없는한, 노드가 5개일..

가중치가 있는 방향 그래프에서, 한 정점으로부터 다른 정점까지의 최단 거리를 구하는 알고리즘먼저 dist를 무한대로 초기화dist[i]는 1번 정점에서 i번 정점까지의 최소 비용을 저장한다.1번 정점에서 출발하므로 dist[1]은 0으로 초기화한다. 1번 정점에서 2번 또는 3번으로 갈 수 있다.1에서 2로 가는 간선의 가중치가 12이므로, 0에 12를 더한다.기존 값보다 작으면 갱신해준다. 처음에는 무한대니까 갱신된다.1에서 3으로 갈때는 간선이 4니까 0에 4를 더해 dist[3]을 4로 갱신한다. 그렇게 해서 다 바꿨다 하면 다시 최소값을 찾는다. (이때 체크한 것은 제외)이번에는 3이 체크되면서 최소값이 된다.1번에서 3번으로 가는 비용은 4라는 것이다. ★ 이 최소값 4는 앞으로 다른 경로에 의..

대표 예제풀이 방법이 2가지 있다. 9개의 도시가 모두 연결되어야하는데 최소 비용으로 연결해야 한다. 그래프 → 최소비용의 트리로 만들어야한다.트리는 n개의 정점이 있으면 간선은 n-1개만 있으면 된다. Kruskal MST1. 우선 들어오는 간선들의 가중치를 기준으로 오름차순으로 나열한다. 2. 밑에서부터 선택한다. 이 때 무조건 밑에서부터 선택하는 것은 아니고만약에 간선을 선택했는데 회로가 되면 간선을 선택하면 안된다.ex) 2 3 10이 들어 왔을 때 2번과 3번이 이미 연결되어 있는지 find함수로 확인한다.이 때 2번과 3번의 집합이 서로 다른 집합이면 연결한다.8 9 15 까지 했을 때의 모습 3. 만약 같은 집합이 나오면2 8 17이 왔을 때find(2)하고 find(8)하면 같은 집합으로 ..

기본 예제서로 친구이면 하나의 집합으로 묶을 수 있다.만약 1번과 2번이 친구라면 A = {1, 2}만약 2번과 3번이 친구라면 B = {2, 3}이 때 집합 A 와 집합 B에 공통된 원소가 있으면 두 집합을 한 집합으로 본다.즉 공통원소가 있으면 묶어버린다. Disjoint Set은 공통원소가 없는 서로소 집합을 뜻한다.Disjoint Set은 내부적으로 트리 구조로 표현한다.각 집합은 하나의 트리트리의 루트가 집합의 대표같은 루트를 가지면 같은 집합친구일 때마다 트리에 연결하고 그렇게 연결된 노드들은 한 집합이다위 입력 예제에서는 다음과 같이 트리가 2개 생성 코드로 구현1. 먼저 초기화를 해준다.for(int i=1; iunf은 1차원 배열로 트리를 표현한 것이다. 각 idx은 학생을 뜻하고 unf..

여러 제한 사항들에 따라 문제 유형을 분류해 보았다. 풀면서 익혀보자. 1. 가방문제 (최대, 보석 제한X) 먼저 이러한 dp 테이블을 두자. (0으로 초기화)i번째 칸이 의미하는것은 가방에 i(kg)까지 담을 수 있을 때 최대 가치이다. 그러면 5kg짜리 보석만 있다고 생각하자. dp[5]부터 채우면 다음과 같다.i번째 칸에 5kg을 담는다고 가정했으니까 인덱스는 5빼주고 그 dp[i-5]에서 v(12)의 가치를 더해준다. 마찬가지로 이번에 3kg짜리 보석도 함께 있다고 생각해보자dp[i]=max(dp[i],dp[i-w]+v) 로 점화식을 세울 수 있겠다.예를 들어 dp[6]의 경우에는 기존의 dp[6](=12)보다 dp[6-3]+8(=16)이 더 크므로 바꿔준다. 이런식으로 나머지 6,4도 적용해 최..