CS

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번째부터 마지..

프로그래밍 언어와 빌드 과정 [Build Process]

⦁ Build 란? 컴퓨터는 근본적으로는 0과 1밖에 모른다. 우리가 작성하는 코드들은 거의 대부분 고급언어를 사용하기 때문에 결국에는 컴퓨터(CPU)가 이해할 수 있도록 번역을 해주어야한다. (C, Java, C++ 등 어셈블리를 제외한 대부분 언어가 고급언어다.) 컴퓨터가 이해하는 언어를 기계어라고 하는데, 우리가 만든 소스 코드가 컴퓨터 입장에서는 해외판 책이 되는 것이고, 이 책을 기계어(machine code)로 번역하여 컴퓨터에서 이해할 수 있는, 즉 실행 가능한 파일로 만드는 과정을 빌드(Build) 라고 한다. ⦁ Build Process 1. Compile Type 이렇게 한 번에 번역하는 언어들을 보통 Compile Language 라고 하는데, 대표적으로 C, C++, Go 언어가 있..

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

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

Stateful (동기) / Stateless (비동기) 서버

Stateful (실시간 온라인 게임) 게임서버 Stateless (비실시간 비동기 온라인 게임) 게임서버 이 두 가지의 서버기술은 완전히 다른 방식의 기술을 사용한다. 먼저 게임의 종류에 대해 알아보자. 게임은 크게 '실시간 온라인 게임'과 '비실시간 비동기 온라인 게임'으로 나뉜다. 실시간/비실시간 게임 실시간 온라인 게임 리니지 LOL 오버워치 크레이지아케이드 이런 실시간 온라인 게임들은 다수의 유저들과 실시간 액션 플레이를 해야한다. 그렇기 때문에 모든 클라이언트는 서버에 접속하여 연결을 유지한 상태로 플레이를 진행한다. 또한 게임의 로직과 전투의 판정 등, 모든 데이터와 결정은 게임서버가 주도적으로 진행해야만 한다. 우리는 이런 게임을 ‘실시간 온라인 게임’ 이라고 부르며 이런 목적의 게임 서버..

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

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

아스키코드, 유니코드, UTF-8의 차이

인코딩 : 문자를 어떻게 출력할지에 대한 약속 숫자를 문자로 바꿈 예를 들어, 메모장에 A라고 친 다음 저장하면 실제로 하드디스크에 기록되는 정보는 65라는 숫자값. A -> 65라고 저장하도록 만들어놨기 때문에 가장 처음 만들어진 인코딩이 ASCII코드 아스키코드 : 128개의 문자조합을 제공하는 7비트 부호 아스키코드만으로는 각 나라별 언어를 표현할 수 없다. 이를 해결한 코드가 유니코드 알파벳, 숫자, 특수기호, 그 외 컴퓨터에 필요한 몇 가지만이 정의되어 있어서 점차 여러 나라에서 컴퓨터를 사용하게 되고 통신이 발달하다보니 기존의 아스키 인코딩보다 더 많은 문자들을 정의한 새로운 인코딩이 필요해짐 유니코드(Unicode) : 각 나라별 언어를 모두 표현하기 위해 나온 코드 체계가 유니코드 숫자와 ..

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

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