/*★편집 거리 알고리즘★편집 거리 알고리즘은 두 문자열이 주어지고 한 문자열을 다른 문자열으로 최소한의 연산을 사용해서 바꾸는 알고리즘이다연산은 수정, 삭제, 삽입 3가지 연산을 사용한다.이 알고리즘으로 구한 최소 편집 거리는 두 문자열간의 유사도를 판단하는 기준이 될 수 있다.알고리즘은 다이나믹 프로그래밍으로 접근 할 수 있고 문자열 A와 B에 대해DP[i][j] = A문자열 (1~i)번 까지를 B문자열 (1~j)번 까지로 바꾸는 최소 편집 거리 라고 정의 할 수 있다.A문자열의 i번째 B문자열의 j번째를 비교해서 단어가 같으면 연산을 수행 필요가 없으므로 인덱스를 증가시켜준다.만약 단어가 다르면 삽입, 수정, 삭제 세가지 연산 준 가장 작은 값을 취해주고 +1을 해주면 된다.*/ #include #..
※우선순위 큐를 이용한 위상정렬의 방법※ 1.모든 일의 선행 필요조건 관계를 따라 그래프를 그린다.(방향 그래프 완성)2. 각 일에 대해 indegree를 센다.(자신으로 들어오는 간선의 개수)3. indegree가 0인 일을 모두 찾아 우선순위 큐에 넣는다4. 우선순위 큐에서 일 하나를 꺼낸다.(위상정렬의 결과 출력을 위해 이때 꺼내진 일을 출력하면 된다.)5. 방금 꺼낸 일에 연결된 모든 일들의 indegree를 1씩 감소시킨다.6. indegree가 감소된 일들 중 indegree가 0인 일이 있으면 우선순위 큐에 넣어준다.7. 우선순위 큐가 빌 때까지 4~6을 반복한다. ※bfs와 dfs를 이용한 위상정렬의 방법※ 공통적으로 먼저 사이클이 있는지 없는지를 판단해야 위상정렬이 생기게 된다.하지만 위..
참고) 32bit integer 이내 답이다 가 들어갈시에 만약 최소값의 범위를 잡을시 그냥 큰값이 아닌 99999999999999999와 같이 정말로 엄청나게 큰 수를 넣는다 #include#include#include using namespace std; //우선순위 큐//방법 3가지//1. 배열 기반//2. 연결리스트 기반//3. 힙 기반 - min heap 기준 //int가 안되서 longlong으로 바꿈 queue arr[101];int result[101]; int main() {int K, N;scanf("%d %d", &K, &N);int a; for (int i = 0; i < K; i++) {scanf("%d", &a);arr[i].push(a); result[i] = a;} // 자료..
우선순위큐
큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오나 우선순위 큐는 다르다. 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 우선순위 큐를 구현하는 방법 3가지 1. 배열을 기반으로 구현하는 방법2. 연결리스트를 기반으로 구현하는 방법3. 힙(Heap)을 이용하는 방법 배열을 사용하는 경우 단점 - 데이터 삽입 및 삭제과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산을 계속 하여야 한다. - 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다.이 경우 우선순위가 가장 낮은 데이터를 저장하는 경우에 발생할 최악의 경우임 연결리스트를 사용하는 경우 단점 - 삽입의 위치를 찾기 위해 첫번째 노드에서부터 시작해 마지막 노드에 저장된 데이터와 우선순위를 비료를 진행할지..
백준 문제 가기 분할 정복법을 배운 후 푼 문제 #include#include#includeusing namespace std; long long n, arr[100001];long long histogrm() { long long i, ret = 0; stackst; // 스택에 왼쪽 끝 인덱스 값을 미리 삽입 st.push(-1); for (i = 0; i < n; i++) { // 스택이 비어있지 않고 while (!st.empty() && arr[i] < arr[st.top()]) { //right는 i int tmp = st.top(); st.pop(); if (!st.empty()) { //left는 st.top //left-right-1 너비, 높이 arr[tmp]의 직사각형 넓이 ret =..