CS/자료구조 & 알고리즘

누적 합 (Prefix Sum)

계산 양을 줄여서 시간적으로 많은 이득을 볼 수 있는 알고리즘이다. 1. 기본 원리 1) 1차원 배열 1차원 배열에서 i번째부터 j번째 인덱스까지 k를 더한 것을 기록하려면, 새로운 배열의 i번째 인덱스에 k를 더하고 j+1번째 인덱스에 k를 빼면 된다. 새로운 배열의 크기는 기존 배열 크기보다 하나 이상 크게 만든다. 예를 들어 크기가 5인 배열에서 0번째부터 2번째 인덱스까지 N을 빼고 싶다면 다음과 같이 누적 합 배열을 만든다. { -N, 0, 0, N, 0, 0 } 위 새로운 배열을 0번째부터 마지막 인덱스까지 누적 합을 계산하게 되면 다음과 같다. 추가로 1번째부터 2번째 인덱스까지 M을 더하고 싶다면 누적 합 배열에 값을 추가한다. { -N, -M, 0, N, M, 0 } 다시 0번째부터 마지..

비트마스크 (BitMask) 알고리즘

1. 비트마스크(BitMask)란? - 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. - 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지이다. - 보통 어떤 비트가 1이면 "켜져 있다"라고 말하며, 0이면 "꺼져 있다"라고 말한다. 2. 비트마스크의 장점 1. 수행 시간이 빠르다. 비트마스크 연산은 bit 연산이기 때문에 O(1)에 구현되는 것이 많다. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르게 동작하게 된다. 다만, 비트마스크를 이용하는 경우에는 비트의 개수만큼 원소를 다룰 수 있기 때문에 연산 횟수가 적은 경우에는 속도에 큰 차이가 없지만, 연산 횟수가 늘어날수록 ..

[C++] 배열 초기화, 벡터 초기화, fill 함수

C++에서 배열을 선언하고 초기화를 해주지 않으면 배열은 쓰레기 값으로 채워져있다. 아래의 코드를 실행해보면 #include using namespace std; int main() { int arr[5]; for (int i = 0; i < 5; i++) { cout

각 정렬의 특징 및 장단점 & 시간복잡도 + 코드

선택정렬 (Selection Sort) 선택정렬은 앞에서부터 차례대로 먼저 주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 진행하는 정렬 방법이다. 코드가 직관적이기에 구현도 비교적 간단하다. n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하며 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점이다. 따라서 교환이 많이 이루어져야하는 자료 상태에서 가장 효율적으로 적용될 수 있다. 선택 정렬이 가장 적합한 자료 상태는 역순 정렬이다. 즉, 내림차순으로 정렬되어 있는 자료를 오름차순으로 재정렬할 때 최적의 효율을 보여준다. 반대로 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 때에는 최악의 처리 속도를 보여준..

유클리드 호제법 - 최대공약수(GCD) 구하기

유클리드 알고리즘(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를 활용한 알고리즘이다. ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8 구현 재귀 함수 활용 int GCD(int a, int b) { if(b==0)return a; else return GCD(b,a%b); } 반복문 활용 int GCD(int a,int b){ while(1){ int r = a%b; if(r==0) return b; a = b; b = r; }..

에라토스테네스의 체

소수를 판별하는 알고리즘이다. 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 단일 숫자 소수 여부 확인 어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다. 만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다. 에라토스테네스의 체 원리 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다. 배열을 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지..

C++ 다익스트라(Dijkstra) 알고리즘 개념 및 구현 (무방향 그래프)

다익스트라 알고리즘 다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 참고로 그래프 알고리즘 중 최소 비용을 구하는 데는 다익스트라 알고리즘 외에도 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다. 동작 단계 ① 출발 노드와 도착 노드를 설정한다. ② '최단 거리 테이블'을 초기화한다. ③ 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다. ④ ..

[C#] 연결 리스트(Linked List)란?

1. 연결 리스트(Linked List)란? * 연결 리스트(Linked List) : 데이터를 저장하는 자료구조. 각 노드가 데이터와 포인터를 가지고 있으면서 노드들이 한 줄로 쭉 연결되어 있는 방식. 2. 단일 연결 리스트(Singly Linked List) : 단방향으로 노드들을 연결한 간단한 자료 구조. (ex) 아래는 4개의 노드를 갖는 단일 연결 리스트를 그림으로 표현한 것. using System; public class LinkedList_Study { public T Data { get; set; } public LinkedList_Study Next { get; set; } public LinkedList_Study(T data) { this.Data = data; this.Next =..

[C#] .NET의 연결 리스트 : LinkedList<T>

LinkedList : 이중 연결 리스트로 되어 있으며, 리스트 노드는 LinkedListNode 클래스를 사용. 노드를 추가하기 위한 AddFirst(처음), AddLast(끝), AddBefore(특정 노드 앞), AddAfter(특정 노드 뒤) 등 다양한 메서드가 있음. LinkedList의 메서드 종류 코드 예시) LinkedList list = new LinkedList(); list.AddLast(1); list.AddLast(2); list.AddLast(3); list.AddLast(4); var node = list.Find(2); var newNode = new LinkedListNode(3); list.AddAfter(node, newNode); //2가 들어있는 노드 다음에 3을 집..

[C#] 힙 (Heap)

1. 힙이란? : 완전 이진 트리(Complete Binary Tree)의 일종. 여러 값의 데이터들 중 최대값과 최소값을 빠르게 찾아낼 수 있는 자료구조입니다. (시간복잡도로 따지면 O(logn)이 걸림) * 힙의 특징 - 중복 값을 허용 - 루트가 최대값(새로운 데이터가 추가될 때 부모노드와 크기를 비교해 크기가 더 큰 값을 부모노드로 올리기 때문) - 새로운 데이터를 추가할 때 작은 레벨 순서대로 채움(왼쪽부터) 2. 이진 탐색 트리와 힙의 차이 * 공통점 : 둘 다 이진 트리. * 차이점 - 힙은 이진 탐색 트리와 달리 중복 값을 허용. - 힙은 각 노드들이 부모노드의 데이터 값보다 작거나 같음. - 이진 탐색 트리는 말 그대로 탐색을 위한 자료구조이고, 힙은 최대값과 최소값 검색을 위한 자료구조..