자료구조, 알고리즘 (14) 썸네일형 리스트형 [알고리즘] 크루스칼(Kruskal) 알고리즘이란? 크루스칼(Kruskal) 알고리즘 간선의 가중치 정보를 이용해 MST(최소신장트리)를 구현하는 알고리즘 이다. 이용되는 알고리즘은 Union Find, 우선순위 큐가 있다. 1) 전체 로직 순서 Comparable을 상속받아 Edge 클래스(정점1, 정점2, 가중치)를 선언한다. compareTo를 오버라이딩 하여 가중치를 기준으로 오름차순 정렬을 조건을 추가한다. Edge형 우선순위큐를 선언하고 주어진 간선의 정보를 이용해 새로운 edge 객체를 우선순위큐에 넣어준다. 우선순위큐에서 간선을 순서대로 빼온다. 빼온 간선에 해당하는 두 정점이 같은 Union인지 확인한다. 같은 Union이라면 -> 이미 추가된 정점들이므로 다음 간선을 빼낸다 다른 Union이라면 -> 해당 정점의 부모노드를 이용해 같은 .. [알고리즘] 최소신장트리, MST란? MST란? Minimum Spanning Tree의 약자로 최소신장트리 라고 불린다. 위 그림과 같이 그냥 Spanning Tree는 모든 정점이 연결되어 있는 Tree이다. 조금 더 구체적으로 말하면 모든 정점이 임의의 간선들을 거쳐 만날 수 있는 Tree이다. 따라서 MST는 최소한의 가중치로 모든 정점을 연결시킨 Tree이다. MST를 만들 수 있는 알고리즘은 크게 2가지가 있는데 다음과 같다. 1) 크루스칼(kruskal) 알고리즘 2) 프림(prim) 알고리즘 1) 크루스칼 알고리즘 이란? 크루스칼 알고리즘이란 주어진 간선의 가중치를 기준으로 MST를 찾는 알고리즘이다. 크루스칼 알고리즘 구현을 위해 쓰이는 자료구조 및 개념 -> 우선순위큐, Union Find 2) 프림 알고리즘이란? 프림 알.. 우선순위 큐는 왜 힙 구조를 사용할까? 우선순위큐에 대해 설명하기 전에 힙에 대해 간단히 정리해보면, 힙은 완전 이진트리의 형태이며 루트노드가 최대값(max-heap기준)이고, 삽입 삭제의 연산이 logN인 특징을 갖는다. 그렇다면 우선순위큐란 뭘까? 기존에 큐(Queue) 자료구조는 넣은 순서대로 출력이 되었다면, 우선순위큐는 기준을 스스로 정할 수 있는것이다. 여기서 기준이란? 데이터를 입력한 자료구조에서 빼내올때 출력되는 순서의 기준을 뜻한다. 큐의 경우 입력순서가 될 것이다. 다시 본론으로 돌아와서 우선순위큐를 구현할 수 있는 자료구조는 많이 있는데 왜 하필 우선순위큐는 힙 구조를 사용할까? 이유는 수행시간 때문이다. 노드(데이터)수를 N이라고 했을때 heap은 삽입 삭제 연산이 모두 logN이지만 배열, 리스트와 같은 선형구조의 형태.. 힙(Heap)의 구조와 동작과정 나머지는 관심없고 부모노드만 알고싶은 힙(Heap) 힙(Heap)이란 (max-heap)일 경우, 루트노드가 가장 큰 노드이고, (min-heap)일 경우, 루트노드가 가장 작은 노드이다. 따라서 루트노드를 제외하고 나머지 노드의 관계는 알 수도 없고, 중요하지도 않다. 어떻게 힙 자료구조가 동작하는지 알아보자. * 힙의 삽입 과정 (max-heap 기준) 1) 완전이진트리의 형태이므로 리프노드 자리중 다음 노드 자리에 일단 new Node 삽입 2) 부모노드와 비교했을때 삽입한 노드가 더 크다면 부모노드와 스왑, 아니면 그대로 3) 더 큰 부모노드를 만날때까지 2번을 반복한다, 루트노드까지 간다면 거기서 종료 위 과정을 그림으로 나타내면 다음과 같다. * 힙의 삭제 과정 (max-heap 기준) 1) .. 트리(Tree)의 개념과 종류들 비선형 자료구조, 트리 이전까지의 자료구조들은 모두 선형 자료구조였다. 배열, 리스트, 스택, 큐 등 모두 선의 모양으로 쭉 나열된 형태의 모양이었다면 트리는 그러한 모양을 띠지 않기 때문에 대표적인 비선형 자료구조라고 불린다. 자료구조의 근본적인 모양이 이전과는 다르므로 용어자체도 다른 부분이 많다. 위 그림을 보면 용어를 알 수 있는데 정리해보면 다음과 같다. 노드(Node) : 각 데이터 간선(edge) : 각 노드를 잇는 선 부모노드: 현재 노드에서 간선을 통해 위쪽으로 연결된 노드, 1개만 가질수 있다. 자식 노드: 현재 노드에서 간선을 통해 아래쪽으로 연결된 노드 Root(+node): 가장 윗부분에 위치한 노드, 부모노드가 없다. 리프 노드: 가장 바깥쪽에 있는 노드 내부 노드: 리프노드를 .. 스택(Stack)과 큐(Queue) 스택과 큐는 가장 기본적인 자료구조이다. dfs, bfs를 구현하는데에도 쓰이며, 여러가지 알고리즘 기법이나 개념등에 적용되는 자료구조이다. 선입후출의 자료구조, 스택(Stack) 스택은 바닥이 막혀있고 윗부분이 뚫려있는 자료구조 라고 생각하면 된다. 그래서 스택은 뚫려있는 위로만 데이터가 들어올 수 있다. 그렇다면 데이터를 뺄때는?? 똑같이 위로만 데이터가 나갈수가 있다. 따라서 먼저 들어온 데이터들은 들어온 순서대로 아래로 깔리게 되고 나중에 들어올수록 먼저 나가게된다. 때문에 스택은 "선입후출"의 자료구조라고 부른다. 이러한 스택의 특성을 이용하여 대표적으로 이용되는 알고리즘이 dfs구현이다. 물론 저러한 모양은 추상적으로 표현한 것일 뿐이며, stack의 내부 구현을 타고 들어가면 배열로 구현이 .. 순열, 조합, 부분집합 순열, 조합, 부분집합은 탐색에서 자주 출제되는 유형이다. 항상 헷갈렸었는데 정리해보자 순열: 순서가 의미있다! 순열이란 ? 순서가 의미있는 조합이다. 즉, 순서가 달라지면 그 의미도 달라진다. 예를들어) 주사위를 3번 던졌을때 나올수있는 모든 수의 순서를 구하라 이경우에 (1,3,5)와 (3,1,5)는 다른 경우이다. 조합과 다르게 현재 선택된 수보다 작은수를 다음에 선택할수있다 -> visit배열을 이용하여 처리한다. 순열의 모든 경우를 구하려면 어떻게 해야할까? for문을 돌리며 result배열의 각 index에 수를 넣는다 import java.util.*; public class 순열_연습 { static int[] result; static int[] visit; static int[] dic.. 2차원 배열 원소 한칸씩 옮기기 달팽이 배열에 이어 2차원 배열에서 원소들을 한칸씩 이동하는 경우도 있을 수 있다. 이 경우도 달팽이 배열을 찍는것과 크게 다르지 않다. 다음과 같이 원소를 한 칸씩 시계방향으로 이동시켜야 한다고 해보자. 두 변수의 값을 switching할때처럼 그냥 바꿀 수는 없고 값을 임시저장할 변수를 이용하는데 이 경우도 그 아이디어는 같다. 어느 위치의 값을 임시저장 해줄것인지는 자유이지만 여기서는 (0,0)이라고 하겠다. 여기서 (0,0)좌표의 값을 임시저장 했으므로 바로 밑에있는 (1,0)의 값을 (0,0)으로 가져와야한다. 즉, 시계방향으로 한칸씩 이동시킬 때, 현재 위치에 놓일 다음 값은 반시계 방향으로 찾으러 가야한다. 따라서 next값의 방향이 이동방향과 반대가 되는것이다. 원소 한칸씩 옮기기는 이 점.. 이전 1 2 다음 1/2
