메이쁘

안녕하세요. Matrix chain multiplication(행렬 최소 곱셈 알고리즘) 길죠. 간단하게 설명드리겠습니다! Matrix chain multiplication(행렬 최소 곱셈 알고리즘) 이란? - M : Matrix(행렬), d : dimension(차원) - Matrix는 1 ~ 4 까지 4개가 존재하고, dimension은 0 ~ 4 까지 5개가 존재한다고 하자. - 각 Matrix의 왼쪽 dimension 은 행, 오른쪽 dimension 은 열이다. - 위 알고리즘이 성립하기 위한 필수 조건은 위 그림처럼 1) 이전 Matrix의 열 과 다음 Matrix의 행 이 같다. 2) 이전의 이전 Matrix의 열과 이전 Matrix의 행이 같다. 이다. *** 행렬의 곱셈을 위한 조건과 동..

안녕하세요. 이는 면접 대비 맞춤 포스팅입니다. 그럼, 바로 진행하겠습니다. 삽입 정렬이란 ? - 손 안의 카드를 정렬하는 방법과 유사한 알고리즘이다. - 처음에는 두 번째 원소부터 시작하는데, 해당 원소를 꺼내든다. 그 후, 그 앞의 원소들과 하나씩 비교하여 삽입할 위치를 정한다. *** 만약, 앞의 원소보다 크기가 크면 종료한다. - 종료 시 그 지점에 원소를 넣고, 나머지 원소들은 한 칸씩 뒤로 밀려난다. - 장점 -> 배열 원소의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 정렬들보다 유리할 수 있다. -> 대부분의 원소가 정렬된 상태에서는 매우 효율적일 수 있다. (이는 선택, 삽입, 버블 정렬 한정) - 단점 -> 비교적 많은 원소들의 이동을 요구한다. -> 원소 수가 많고 원소 크기..

안녕하세요. 이는 면접 대비 맞춤 포스팅입니다. 그럼, 바로 진행하겠습니다. 버블 정렬이란 ? - 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘. - 인접한 두 원소를 검사하여 크기 순서를 맞춘다. (SWAP) - 장점 -> 구현이 매우 간단함. - 단점 -> 일반적으로 SWAP(원소 자리 바꿈)이 MOVE(이동) 보다 복잡하기 때문에 거의 쓰이지 않음. -> 시간복잡도가 정렬 알고리즘 중 가장 높다. (비효율적) *** 시간복잡도 == Best : n^2, Avg : n^2, Worst : n^2 알고리즘 간단코드 -> 이런 방식으로 두 개의 for문이 필요하며 내부에는 SWAP을 진행함. 알고리즘 그림설명 코드를 바탕으로 진행되는 버블 정렬이다. 1) 인접한 두 원소 선택해서 크기 비교 -> 큰 ..

허프만 코드란? - 데이터를 효율적으로 압축하는 데 사용하는 알고리즘으로, 그리디 알고리즘에 속함. - 데이터 빈도 수에 따라 우선순위 큐에서 작은 두 개의 노드를 꺼내고 이를 합쳐 트리를 만드는 과정이 있다. - 고정 길이 코드와 가변 길이 코드 두 가지 표현 방법이 존재함. 허프만 코드 인코딩 과정(허프만 코드를 만드는 과정) ** 참고로 여기서 말하는 방식은 가변 길이 코드 표현 방법에 해당한다. - (a) ~ (f) 까지의 과정을 담은 그림으로, 이 그림을 보면 바로 이해할 수 있을 것이다.. - (a) : 예를 들어, 인코딩을 할 문자열이 casdffsdasadceacsd 라고 주어지면, 이 문자열에 각 알파벳 별로 얼마나 포함되어있는지(빈도 수) 나타낸 수 이다. 이 수들을 우선순위 큐에 담아..

Union / Find 알고리즘이란? -> 그래프 알고리즘 중 하나로 합집합을 찾는 방법. -> 상호 배타적 집합(Disjoint-Set)이라고도 함. -> 여러 노드(정점)가 주어질 때, 두 개의 노드(정점)를 선택해서 현재 두 노드(정점)가 서로 같은 그래프에 속하는지 판별하는 알고리즘. -> Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 -> Union : x와 y가 포함되어 있는 집합을 합치는 연산 -> 처음에는 모든 노드의 부모를 해당 인덱스(자기 자신)로 설정 샘플 코드 - Union 함수 // 두 노드를 합치는 함수 public static void union(int x, int y) { x = find(x); y = find(y); if(x != y) parent[y] = x; ..

크루스칼 알고리즘이란? -> 프림 알고리즘과 같이 MST(최소 스패닝 트리) 를 찾기 위한 알고리즘. -> 조금 Greedy한 방법. -> 간선을 중심으로 탐색하면서 노드를 확인용으로만 사용함. -> 핵심은 각 단계에서 사이클을 이루지 않은 간선을 선택하는 것! -> Union-Find 개념이 필요함! https://maivve.tistory.com/11 -> 시간복잡도 : O(ElogV) 지만, 프림보다 크루스칼이 빠르다. 매커니즘 1) 모든 간선들을 우선순위 큐에 넣고 weight를 오름차순해서 가장 작은 값부터 poll 한다. 2) poll 한 간선의 양 끝 점이 같은 부모인지 체크한다. 3) 같은 부모이면 다음 간선을 선택하고 3-1) 다른 부모이면 해당 간선을 최종 선택한다. -> 가중치 추가 ..

벨만-포드 알고리즘이란? -> 그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용하는 알고리즘. 사이클 포함 X. -> 음의 가중치도 계산 가능. 다익스트라 알고리즘보다 시간복잡도 높음(더 느림). -> 간선들을 중심으로 찾음 -> 방문되지 않은 정점(값이 무한대인 정점)에서 출발하는 간선들은 고려하지 않는다. -> 즉, 다익스트라의 변형을 통해 음수간선에 대한 처리 및 음수 사이클을 체크하기 위한 알고리즘. -> 여기서 모든 사이클을 한 번 다 돌아도 distance의 변화가 하나도 없으면 그냥 해당 for문을 종료시켜도 됨. ** 최악의 경우 시간복잡도 O(n^3), 보통 O(VE) 샘플코드 public static boolean bellman(int n, int m, int sta..

프림 알고리즘이란? -> n개의 정점을 가지는 그래프에서 MST(Minimun Spanning Tree = 최소 신장 트리) 를 구하기 위해 사용하는 알고리즘 -> 그래서 결과로 나온 트리는 N-1개의 간선을 가진다. = N-1번 반복 수행 -> 그래프의 간선을 넣을 때 간선이 방향이 없는 양방향이므로 양 쪽 다 넣어야 한다.(한 쪽만 넣어도 가능한 듯) -> 프림 : 원리 상 정점을 중심으로 간선을 탐색함. 크루스칼 : 간선을 중심으로 탐색함 -> 시간복잡도 : O(ElogV) -> 이진 힙(우선순위 큐)을 사용했을 때 매커니즘 1) 정점 중 아무 시작 정점을 고르고, 정점과 연결된 모든 Vertex를 큐에 넣는다. 2) 해당 정점에 연결된 모든 간선 중 가장 최소 비용을 가진 간선을 선택해서 연결. ..

다익스트라 알고리즘? -> 그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용하는 알고리즘. -> 사이클 포함 X -> 음의 가중치가 존재하면 사용 불가능. 매커니즘 1) 체크되어있지 않은 정점 중에서 D(Distance)의 값이 가장 적은 정점(또는 시작점)을 선택(우선순위 큐에 삽입) 2) 우선순위 큐에서 해당 점을 꺼내고, 이 점을 인덱스로 하는 visited 배열의 값을 True로 변경(방문했다는 표시) -> 방문 따지면 안되는 경우도 있음..! 3) 해당 점과 연결된 모든 점을 검사(방문 여부에 관계 없이 진행. 그 이유는 최단 경로가 갱신될 수 있으므로) 4) 해당 점을 x, 연결된 다른 끝 점을 y, 이동하는 Weight를 w라고 했을 때, D[y] > D[x] + w를 만..

버블 정렬 -> 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘. = 인접한 두 원소를 비교하여 크기 순서를 맞춘다. -> 장점 : 구현이 매우 간단하다. -> 단점 : 일반적으로 SWAP(스왑)이 MOVE(이동)보다 복잡하기 때문에 거의 쓰이지 않는다. ** 시간복잡도 : Best : n^2, Avg : n^2, Worst : n^2 // i가 1 증가하면 처음부터 끝까지 정렬을 완료했단 뜻이므로 // 가장 맨 끝의 원소는 정렬이 완료되어있어 굳이 탐색을 하지 않는다. // i를 뺀다. for(int i = 0; i a[j + 1]) {// 여기서 스왑한다. int b =..