삽입 정렬이란? 삽입 정렬: 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입한다. key값은 2번째 인덱스부터 시작되며, key값이 자료의 길이만큼 이동했을 때 정렬된다. 1) 정렬되지 않은 배열에서 2번째 인덱스를 key값으로 잡는다. 2) 앞의 인덱스와 비교하여 교환한다. 3) 2번째를 key값으로 잡았기 때문에 다음, 3번째 인덱스를 key값으로 잡는다. 4) 마찬가지로 앞의 인덱스들과 비교하여 교환한다. 시간복잡도 최선의 경우 O(n) 시간복잡도를 가지게 되지만, 최악의 경우 O(n^2)이 될 수 있다. JAVA CODE public cl..
버블 정렬이란? 버블 정렬(거품 정렬): 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하여 정렬하는 알고리즘이다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 이를 양방향으로 번갈아 수행하면 칵테일 정렬이 된다. 1) 그림과 같이 정렬되지 않은 배열이 있다고 가정하자. 2) 맨 앞부터 비교를 하게 된다. 그럼 7과 2를 비교하게 되는데, 7이 더 크기 때문에 두 수를 바꾼다. * 버블 정렬을 동그라미 표시(거품)를 하며 바꾼다는 의미로 외웠음 3) 2와 7을 바꾼 뒤 한 칸 앞으로 가서 다시 7과 0을 비교한다. 4) 마찬가지로 7이 더 크기 때문에 두 원소를 교환한다. 이런 식으로 제일 큰 수 부터 정렬하는 방법이 bubble sort ..
최소 신장 트리(Minimum Spanning Tree)란? 💡최소 신장 트리: 그래프에서 모든 정점에 대해 최소한의 연결만을 남긴 그래프이다. 즉 간선의 가중치 합이 가장 작은 트리를 뜻한다. 사이클이 존재하지 않아야 한다. 최소 신장 트리를 찾는 알고리즘으론 크루스칼 알고리즘, 프림 알고리즘이 있다. 이 알고리즘은 그리디 알고리즘 기법을 활용한 알고리즘이다. 프림 알고리즘은 바이너리 힙을 이용하는 경우 O(E+VlogV)의 시간 복잡도를 가지며, 크루스칼 알고리즘은 경로 최적화를 이용하지 않는 경우 O(ElogV), 경로 최적화를 이용하는 경우 O(Elog∗V)의 시간 복잡도를 가지기 때문에, 그래프의 간선 밀도를 고려하여 최적의 알고리즘을 선택하는 것이 필요하다. 크루스칼 알고리즘(Kruskal A..
유니온 파인드 알고리즘이란? 💡유니온 파인드 알고리즘: 상호 배타적 집합, Disjoin-set(서로소 집합) 이라고도 부른다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어 주고, 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다. 왜 이름이 유니온 파인드인가? 유니온 파인드 알고리즘은 두가지의 연산을 진행한다. 이 연산 과정을 Union, Find라고 부른다. Union: 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 자료구조에서는 상호 배타적 집합만을 다루므로 Union 연산은 합집한 연산과 같다. Find: 하나읜 원소가 어떤 집합에 속해있는지를 판단한다. 크루스칼 알고리즘과 프림 알고리즘을 알기 위해선 유니온 파인드 알고리즘을 알아야 한다. 유니..
다익스트라 알고리즘이란? 💡다익스트라 알고리즘: 데이크스트라 또는 다익스트라 알고리즘이라 불리는 이 알고리즘은 음의 가중치가 없는 그래프에서 최단 경로 및 최단 거리를 찾는 알고리즘이다. 매번 최단 경로의 정점을 선택하기 때문에 그리디 알고리즘 기법을 활용한 예라고 볼 수 있다. 중요한 점은 음의 가중치가 없을 때만 사용이 가능하다는 점이다. 인접행렬을 사용하는 경우 O(n^2)의 시간복잡도를 가지지만, 우선순위 큐(=힙 트리)등을 이용한다면 O((v+e)logV)(V는 정점의 개수, E는 한 정점의 주변노드)의 시간복잡도를 가진다. 음의 가중치를 가지는 간선이 있으며, 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용할 수 있다. 가능한 적은 비용으로 가장 빠르게 해답에 도달하는..
탐욕 알고리즘이란? Greedy Algorithm: 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 각 단계에서 가장 최선의 선택을 하는 기법이다. 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘인 것이다. 탐욕 알고리즘은 일정 공식없이 창의력을 요구하는 문제 유형이다. 때문에 문제를 풀기위한 최소한의 아이디어를 떠올려야 할 것이다. 물론 모든 경우에서 그리디 알고리즘이 통하는 것은 아니다. 예를 들어 지금 선택하면 1개의 마시멜로를 받고, 1분 기다렸다 선택하면 2개의 마시멜로를 받는 문제에서는, 그리디 알고리즘을 사용하면 항상 마시멜로우를 1..
DFS와 BFS를 알기전에 트리와 그래프가 무엇인지 부터 알아야 한다. https://memodayoungee.tistory.com/85 [자료구조] 02. Tree 트리 란? 💡트리: 단반향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗는 형태가 나무와 닮았다고 해서 트리라 부르는 자료구조이다. 데이터가 바로 아래에 있는 하나 이상의 데 memodayoungee.tistory.com https://memodayoungee.tistory.com/84 [자료구조] 01. 그래프 DFS, BFS에 대한 이야기를 하려다 어쩌다보니 그래프를 작성하게 되었다.. 안좋을 점은 없으니까.. 블로그에 남겨두고 간다... 그래프 란? 💡그래프: 여러 개의 점들이 서로 복잡하게 연결되어 있 memodayoun..
💡비트마스크: 알고리즘보다는 기법이나 테크닉에 가깝다. 자료구조를 사용해야하는 상황에서 이진수를 이용하여 빠르게 연산하는 기법이라 말할 수 있다. 비트 마스크를 알기 전에 비트가 무엇인지 부터 알아야 한다. 비트(Bit) 💡비트(Binary Digit, Bit): 데이터들을 나타내는 최소 단위, 이진수로 표현한다.(0과 1) 비트 연산자 구분 연산자 의미 설명 예시(a=1001, b= 1100) 비트연산자 & 비트 단위 AND 양쪽 비트가 모두 1이면 결과도 1이고 나머지는 0을 반환한다. a&b = 1000 | 비트 단위 OR 양쪽 비트 중 하나라도 1이면 1을 반환, 나머지는 0을 반환한다. a|b = 1101 ^ XOR(배타적 OR) 양쪽 비트가 서로 다르면 1, 같은면 0을 반환한다. a^b = ..
