[알고리즘] 비트마스크(BitMask)란?

비트마스크(BitMask)란? 비트마스크는 이진수를 사용하는 컴퓨터의 연산 방식을 이용해, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말합니다. 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 2가지 경우가 있는데, 비트가 1이면 "켜져 있다"라고 말하며, 0이면 "꺼져 있다"라고 말합니다. 비트마스크를 사용하는 이유 🟢 빠른 수행시간 원소의 수가 많지 않을 때 사용되며, bit연산이기 때문에 시간복잡도 O(1)에 구현되는 것이 많습니다. 🟢 작은 메모리 사용량 만약 bit가 10개인 경우, 각 bit당 두 가지의 경우를 가지기 때문에 2^10가지의 경우를 10bit 이진수 하나로 표현 가능합니다. 그렇기 때문에 하나의 정수로 매우 많은 경우의 수를 표현할 수 있기 때문에 메..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 2. 4.
• textsms

[알고리즘] 다익스트라(Dijkstra) - 최단거리 알고리즘

다익스트라(Dijkstra) 다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프에서 최단 거리를 구하는 알고리즘입니다. 가장 짧은 경로를 찾으므로 "길 찾기" 문제에 많이 사용됩니다. 이전 다익스트라의 경우 O(n^2)의 시간복잡도를 가졌었지만, 현재는 우선순위 큐를 이용한 개선된 다익스트라 알고리즘이 탄생해 O(ElogE)의 시간복잡도를 가집니다. ( E는 Node의 간선의 수 ) 만약 음의 간선이 존재한다면 "벨만-포드 알고리즘"을 활용해야 합니다. 다익스트라 알고리즘은 그리디 알고리즘과 다이나믹 프로그래밍 기법을 사용한 알고리즘입니다. 그 이유는 아래의 알고리즘 특징에서 설명하겠습니다. 다익스트라 알고리즘 특징 각 지점은 그래프에서 '노드' 또는 정점으로 표현되고 지점간 연결된 ..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 2. 1.
• textsms

[알고리즘] 라인 스위핑 (Sweeping)

Line SweepingSweeping이라는 단어를 번역하면 "싹슬이 하는"이라는 뜻을 가집니다.즉, "한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것"입니다.보통  라인스위핑 알고리즘은 좌표 문제에 많이 사용되며 O(nlogN)의 시간 복잡도를 가집니다.  라인 스위핑 알고리즘 문제 (백준 2170 : 선 긋기) 문제 설명매우 큰 도화지에 자를 대고 선을 그으려고 한다.매우 큰 도화지에 자를 대고 선을 그으려고 한다.선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다.선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 2. 1.
• textsms

[알고리즘] 투 포인터(Two Pointers)란?

투 포인터(Two Pointers) 투 포인터는 말 그대로 두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 것 입니다. 투 포인터를 활용하기 위한 조건은 주어진 배열에서 연속된(정렬이 아닌) 부분 배열을 통해 문제를 해결할 수 있어야 합니다. 투 포인터 알고리즘을 활용하는 대표적인 예로는 배열에서 특정한 합을 갖는 부분 연속 수열을 찾을 때가 있습니다. 만약 이중 반복문을 통해 부분 연속 수열을 찾는다면 O(n^2)의 시간복잡도가 소요되는 반면 투 포인터를 활용한다면 O(n)의 시간복잡도로 시간을 단축 시킬 수 있습니다. 투 포인터는 두 개의 포인터를 사용하기 때문에 두 개의 인덱스를 가르키는 변수가 필요합니다. 그 변수를 하나는 "시작점을 가르키는 start", 다른 하나는 "..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 1. 27.
• textsms

[알고리즘] LIS(최장 증가 부분 수열)이란 ?

LIS (Longest Increasing Subsequence) 최장 증가 부분 수열 최장 증가 부분 수열은 말 그대로 가장 길게 증가하는 부분 수열으로 즉, 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열을 LIS라고 합니다. 좀 더 이해하기 쉽도록 아래 그림을 봅시다. 만약 위와 같은 배열이 있을 때 만들수 있는 증가 부분 수열은 위와 같으며 최장 증가 부분 수열은 만들 수 있는 증가 부분 수열 중 길이가 가장 긴 [1, 2, 6]이 됩니다. LIS를 구현하는 방법으로는 두가지가 있습니다. DP [알고리즘] 동적 프로그래밍 (DP) 란? feat.동적 계획법 동적 프로그래밍(Dynamic programming) 란? 동적 프로그래밍은 "큰 문제"를 "부분 문제"로..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 1. 26.
• textsms

[알고리즘] 힙 정렬(Heap Sort)이란?

먼저 힙 정렬에 대해 다루기 전에 "힙"에 대한 이해가 필요합니다. 힙에 대해 알고 싶다면 아래 링크를 참고하시면 도움됩니다. 힙(Heap) 자료구조 힙(Heap)이란 ? 완전 이진 트리의 일종으로, 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 만들어진 자료구조입니다. 힙을 사용하는 이유는 최댓값과 최솟값을 찾기 위해 배열을 사용하는 경 hstory0208.tistory.com 힙 정렬(Heap Sort) 힙 정렬 알고리즘은 삽입과정 없이 삭제과정만이 이뤄집니다. 최대힙(max heap)을 구현한뒤, 루트 노드를 삭제하여 마지막 노드가 루트 노드가 되어 최대힙의 규칙에 맞게 재구조화 되며 정렬합니다. 힙 정렬 알고리즘은 주로 다음과 같은 경우에 유용하게 사용됩니다. 최댓값과 최솟값을 구할 때 최대 k만..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 1. 21.
• textsms