IT

최근 개발자들이 취업을 준비할 때 필수 관문이 된 코딩 테스트에서 다양한 언어들이 사용되지만, 그중에서도 많은 개발자들이 C++을 선호하는 경향이 있다. 오늘은 C++이 코딩 테스트에서 유리한 이유과 장점에 대해서 분석해보도록 하겠다. 빠른 실행 속도 C++의 실행 속도는 다른 언어에 비해 상당히 빠른 편이다. 일반적인 알고리즘 문제의 경우, Python보다 약 10 ~ 100배 정도 빠른 실행 속도를 보이며, Java보다 약 1.2 ~ 2배 정도 빠른 것으로 평가된다. 특히 수백만 개의 반복 연산이나 대규모 데이터 구조를 다룰 때 속도 차이가 두드러진다.  C++은 컴파일 시점에 기계어 코드로 변환되므로, 실행 시간에는 기계어 수준에서 곧바로 연산이 이루어진다. 반면 Python과 같은 인터프리터 언어..

최소 신장 트리(MST: Minimum spanning tree)는 그래프에서 모든 노드를 연결할 때 사용된 Edges의 가중치의 합을 최소로 하는 트리를 의미한다. MST의 특징은 다음과 같다. 사이클을 포함하지 않는다. (사이클이 포함되면 가중치의 합이 최소가 될 수 없는 모순 발생) N개의 노드가 있다면 Edge의 개수는 N-1개다. MST를 구할 때 사용하는 알고리즘은 다음과 같다. 크루스칼(kruskal) 알고리즘 프림(Prim) 알고리즘 이 포스터에선 크루스칼 알고리즘으로 MST를 구현해보도록 하겠다. MST: 크루스칼 알고리즘 크루스칼 알고리즘으로 MST를 구할 땐 Union-Find 알고리즘을 사용한다. Union-Find 알고리즘에 대해 익숙하지 않다면 아래 포스터를 참고하자. https..

플로이드-워셜(Floyd-warshall) 알고리즘은 모든 노드에 대해 그래프에서 최단 거리를 구하는 알고리즘이다. 이 알고리즘의 특징은 다음과 같다. 음수 가중치가 있어도 수행할 수 있다. 동적 계획법(Dynamic Programming) 원리를 따른다. 시간 복잡도는 O(V ^ 3)으로 많이 느린 편에 속한다. 그래서 N이 1000개 이상인 경우에는 사용하기 어렵다. 플로이드-워셜 자료구조 먼저 그래프를 표현할 인접 행렬이 필요하다. 인접 행렬은 2개의 노드 인덱스와, 1개의 거리 요소로 구성되어 있다. 이 자료구조 하나로 플로이드-워셜 알고리즘을 구현할 수 있다. 플로이드-워셜 원리 플로이드-워셜의 핵심 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존..

벨만-포트(Bellman-ford) 알고리즘은 다익스트라 알고리즘과 유사하게 특정 노드로부터 그래프에서 최단 거리를 구하는 알고리즘이다. 차이점은 아래과 같다. Edge 가중치가 음수를 가질 수 있다. 음수 사이클의 존재 여부를 판단할 수 있다. 시간 복잡도: O(V * E) 벨만-포드 자료구조 벨만-포드는 Edge 기반으로 동작하기 때문에 엣지 리스트로 그래프를 표현한다. 엣지 리스트는 보통 Edge 구조체로 저장한다. 그리고 다익스트라와 마찬가지로 최단 거리를 저장하기 위한 정답 리스트가 필요하다. 시작 노드는 0으로, 나머지는 무한대에 가까운 Dummy 값으로 초기화해준다. 벨만-포드 원리 벨만-포드는 Edge에 대해 for문을 돌기 때문에 업데이트 반복 횟수는 (N-1) 이다. 음수 사이클이 없을..

다익스트라(Dijkstra) 알고리즘은 그래프에서 특정 지점에서 모든 노드를 지나는 최단 거리를 구할 때 사용하는 알고리즘이다. 이때 그래프가 다음 특성을 가질 때 사용 가능하다. 모든 Edge의 비용이 양수여야 한다. 다익스트라의 시간 복잡도는 O(E * log V)이다. 다익스트라 자료구조 먼저, 그래프를 표현하기 위해서 인접 리스트 자료구조를 사용한다. 인접 리스트의 인덱스는 Start 노드이며, 각 인덱스에 해당하는 요소는 (End 노드, 가중치)이다. 만약 양방향 그래프의 경우 이방향에 대해 저장해줘야 한다. 추가로 최단 거리 배열이 필요하다. 이것은 다익스트라 원리를 구현하기 위해 필요한 자료구조이다. 처음에는 무한대에 가까운 Dummy 값으로 초기화해준다. (시작 노드는 0으로 초기화) 또한..

위상 정렬(Topological Sort)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 이때 그래프에 사이클이 존재하면 안되며 시간 복잡도는 O(V + E)이다. 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다는 특징이 있다. 위상 정렬 자료구조 가장 먼저 위상 정렬을 위한 자료구조를 생성한다. 그래프를 나타내는 인접 리스트 자료구조를 사용한다. 이째, 위상 정렬을 위해선 진입 차수 배열이 하나 필요하다. 진입 차수 배열 초기값은 모두 0으로 설정한 뒤, 인접 리스트를 수행하면서 해당하는 노드의 값을 1씩 증가시킨다. 그리고 위상 정렬을 결과를 저장할 배열을 하나 선언한다. 또한 진입 차수가 0인 노드를 선택해야 하기 때문에, 위 노드들을 저장할 큐가 필요하다 따라서 필요한 자료구..

Union-Find 정의 유니온 파인드(Union-Find)는 여러 노드에 대해 특정 2개의 노드를 연결해 1개의 집합으로 묶는 처리를 의미한다. Union은 집합으로 묶기 기능, Find는 노드가 속한 집합 탐색 기능으로 구성된 알고리즘이다. Union-Find의 처리 방식은 다음과 같다. Union-Find 동작 원리 Union-Find 동작 원리는 아래와 같은 순서를 가진다. 모든 노드들에 대해 1차원 int 배열을 선언하여 자신의 index를 저장한다. 처음에는 모든 노드가 연결되어 있지 않기 때문에 각 노드가 대표 노드가 된다. 2개의 노드에 대해 각각의 대표 노드를 찾아 연결하는 Union 연산을 수행한다. Union(1, 4)의 경우, 4번 노드의 대표 노드를 1번 대표 노드로 변경해준다. ..

이 포스터에선 그래프와 관련된 기본적인 알고리즘을 소개하도록 하겠다. 그렇다면 그래프(Graph)가 무엇인가? 그래프(Graph) 그래프는 노드(Node)와 간선(Edge)로 구성된 집합이다. 노드는 데이터를 표현하는 단위이고 간선은 노드를 연결한다. 그래프는 여러 알고리즘에서 많이 사용되는 자료구조이다. 그래프 알고리즘 그래프 자료구조를 활용한 대표적인 알고리즘은 다음과 같다. 유니온 파인드: 그래프에 사이클이 존재하는지 판별하는 알고리즘 위상 정렬: 그래프를 선형 정렬한다. 사이클이 없는 방향 그래프에서 사용한다. 다익스트라: 시작점을 기준으로 모든 노드를 방문하는 최소 비용을 구한다. (음수 간선 포함 X) 벨만-포드: 시작점을 기준으로 모든 노드를 방문하는 최소 비용을 구한다. (음수 간선 포함 ..

이 포스터에선 유클리드 호제법에 대해 알아보도록 하겠다. 유클리드 호제법은 두 수 A와 B에 대해 최대 공약수를 구할 때 사용된다. 앞으로 A와 B의 최대 공약수는 GCD(A, B)로 가정하겠다. GCD(A, B) 수학적 정의 2개의 자연수 A, B에 대해서 A를 B로 나눈 나머지를 r이라 하면 (단 A > B), A와 B의 최대공약수는 B와 r의 최대공약수와 같다. 이 성질에 따라, B를 r로 나눈 나머지 r0를 구하고, 다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 A와 B의 최대공약수이다. GCD(A, B) 코드 정의 A % B == 0이면 B를 가지고, A % B != 0이면 GCD(B, A % B)를 수행한다. 즉, 나머지가 0이 될 때의 B가 최대..

이 포스터에선 오일러 피에 대해 알아보도록 하겠다. 먼저, 오일러 피가 무엇인지 살펴보도록 하자. 오일러 피 함수 P[N]은 다음과 같이 정의된다. P[N] = [1, N] 범위에서 N과 서로소인 자연수의 개수 (1와 N 포함) 오일러 피 함수의 증명 과정을 공부해야 완벽하게 이해할 수 있지만 이 포스터에서는 구현 부분만 알아보도록 할 것이다. 오일러 피 함수 원리 오일러 피는 이전 포스터에서 봤던 에라토스테네스의 체와 매우 유사하다. 1. 사전에 미리 N개의 int 배열 메모리를 할당한다. 2. 각 배열의 값은 K로 초기화한다. 3. K의 배수에 해당하는 자리마다 P[K] = P[K] - P[K] / K을 수행한다. 4. K를 2부터 N까지 해당하는 범위에 대해 3번을 반복한다. 과정은 매우 간단하다...