CS/자료구조 & 알고리즘

[C++] 이분 탐색 (Binary Search)

이분 탐색(Binary search)이란? - 정렬된 리스트(배열)에서 원하는 값(target)의 존재 여부(존재 위치)를 찾는 알고리즘. - 반드시 리스트(배열)를 정렬해서 사용해야 한다는 단점이 있다. - 탐색할 때마다 검사 범위가 절반으로 줄어든다. - 재귀적인 방법, 반복문, STL를 이용하여 이분 탐색(Binary Search)을 실행할 수 있다. - Time Complexity : O(log N) 변수 설명 1. int low & int high 검사 범위의 시작점, 끝점의 인덱스를 가리키기 위한 변수. left는 시작점을, right를 끝점의 인덱스를 가리킨다. // nums에 수들이 들어가있다고 가정 vector nums; int low = 0; // 초기 세팅: 제일 앞 인덱스 int h..

C++ MST 크루스칼 + 프림 알고리즘 코드

이미지 출처) Minimum Spanning Tree - Kruskal - Algorithms for Competitive Programming (cp-algorithms.com) 정답) 1 + 2 + 3 + 4 + 7 = 17 순회하는 순서가 추가되는 노드 순서에 따라 상이할 수 있음. 입력 데이터 From 1 To 2 Value 2 Edge형 구조체에 담음, int from, to, val; 9 1 2 2 1 4 1 1 5 4 2 4 3 2 3 3 2 6 7 3 6 8 4 3 5 5 4 9 0 0 0 크루스칼 알고리즘 핵심 포인트) 모든 부모 노드들을 포함하고 있을 int형 벡터와 Edge형 벡터, 한 방향만 연결. #include #include #include using namespace std;..

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) / 장단점, 구현 및 시간복잡도

DFS의 장/단점 장점 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다. 깊이가 무한히 깊어지면 스택오버플로우가 날 위험이 있다. (깊이 제한을 두는 방법으로 해결가능) DFS의 구현 그래프를 인접 행렬(adjacency matrix)로 구현했는지, 인접 리스트(adjacency list)로 구현했는 지에 따라 구현방법이 달라진다. 인접 행렬로 구현했을 경우 [시간복잡도] DFS 하나당 N번의 loop를 돌게 되므로 O(n)의 시간복잡도를 가진다. 그런데 N개의 정점을 모두 방문 해야하므로 n*O(n)이므로 O(n..

1e9? 2e9? 알고리즘 문제해결

알고리즘 문제를 풀다 보면 1e9, 2e9라는 코드를 자주 볼 수 있다. 1e9 = 1*109 = 1000000000, 2e9 = 2*109 = 2000000000 위와 같이 간단하게 표현하는 방법이다. 특히, 2e9는 int 범위내에서 무한대 값을 나타내기 위해 사용하는 경우가 많다. 1e9? 2e9? 알고리즘 문제해결 (tistory.com)

누적 합 (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부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지..