Dev On The Coffee Dev On The Coffee

# 투 포인터 (Two Pointers) 알고리즘 투 포인터(Two Pointers) 알고리즘은 리스트에 순차적으로 접근해야 하는 경우에, 두 개의 점의 위치를 기록하면서 처리하는 방식을 말한다. 시작점과 끝점을 사용해 순차적으로 접근할 데이터의 범위를 표현할 수 있다. 투 포인터를 활용하면 유용한 다음 문제를 살펴보자. 위 문제는 전체 수열이 주어지면, 그 수열의 부분 수열 중 특정한 합을 가지는 연속하는 부분 수열을 찾는 문제이다. 이 문제를 해결하는 가장 심플한 방법은 완전탐색으로 각 인덱스마다 해당 인덱스로 시작하는 부분 연속 수열을 모두 찾아보는 방법이다. 다만, 이 완전탐색은 시간 복잡도가 O(N²)이 걸리므로 비효율적이다. 이 때, 투 포인터 알고리즘을 활용하면 선형 시간 복잡도 O(N)으로..

# 소수 (Prime Number) 판별 알고리즘 소수란 1보다 큰 자연수 중 1과 자기자신을 제외한 자연수로는 나누어떨어지지 않는 자연수를 말한다. 코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제되므로 알고리즘을 기억해두면 좋다. 다음은 기본적인 소수 판별 알고리즘을 파이썬으로 구현한 것이다. # 소수 판별 함수 정의 (2이상의 자연수에 대하여) def is_prime_number(x): # 2부터 (x - 1)까지의 모든 수를 확인하며 for i in range(2, x): # x가 해당 수로 나누어떨어진다면 if x % i == 0: return False # 소수가 아님 return True # 소수임 print(is_prime_number(4)) print(is..

# 신장 트리(Spanning Tree)란? 신장 트리(Spanning Tree)란 원본 그래프의 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 뜻한다. 위의 가운데 그림처럼 간선들이 모든 노드를 잇고 있지만, 사이클은 생기지 않는 부분 그래프가 신장 트리의 예시가 된다. 반면, 오른쪽 그림처럼 모든 노드를 잇지도 않고 사이클마저 생기는 것은 신장 트리에 해당되지 않는다. 이 개념을 트리라고 부르는 이유는 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건이 트리의 조건에 해당하기 때문이다. 이러한 트리의 특성으로 인해, 신장 트리가 가지는 총 간선의 개수는 노드의 개수 - 1이 된다. # 최소 신장 트리(MST, Minimum Spanning Tree) 최소 신장 트리(..

# 서로소 집합 (Disjoint Sets) 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어, {1, 2}, {3, 4}는 서로소 관계이지만, {1, 2}, {2, 3}은 2라는 공통된 원소가 존재하므로 서로소 관계가 아니다. # 서로소 집합 자료구조 (Union Find 자료구조) 서로소 집합 자료구조(Union Find 자료구조)는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조에는 두 가지 연산이 존재하는데, 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 합집합(Union) 연산과 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 찾기(Find) 연산이 그것이다. # 서로소 집합 자료구조의 동작 과정 1. 기본 동작 과정 (..

# 벨만 포드 알고리즘 (Bellman-Ford Algorithm) 1. 벨만 포드 알고리즘 개요 벨만 포드 알고리즘(Bellman-Ford Algorithm)은 다익스트라 알고리즘과 거의 유사하다. 다만, 다익스트라 알고리즘과 달리 벨만 포드 알고리즘은 음의 값을 가지는 간선을 포함하여 알고리즘을 수행할 수 있다는 점이 큰 차이점이다. 위와 같이 5번 노드에서 2번 노드로 가는 간선의 비용이 -2인 그래프가 있다. 이 경우, 음의 간선이 존재하지만 얼마든지 오른쪽 테이블처럼 최소 비용을 계산해낼 수 있다. 그러나 음의 간선의 순환이 포함되어 있는 경우 최소 비용을 계산하는데 어려움이 생길 수 있다. 위 그래프는 음의 간선 비용이 -4인데 이 값이 상당히 작기 때문에 '3번 노드 -> 5번 노드 -> 2..

# 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 1. 플로이드 워셜 알고리즘 개요 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 최단 경로를 구하는 또 하나의 대표적 알고리즘이다. 다만, 다익스트라 알고리즘이 '한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우'에 사용한다면, 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 경우'에 사용한다. 플로이드 워셜은 다익스트라처럼 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행하지만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 없다. 그리고 2차원 테이블에 모든 노드의 최단 거리 정보를 저장하며, 이를 점화식을 통해 갱신한다는 점에..

# 최단 경로 알고리즘 (Shortest Path Algorithm) 최단 경로 알고리즘(Shortest Path Algorithm)이란 가장 짧은 경로를 찾는 알고리즘을 말한다. 최단 경로를 찾는 것은 여러가지 상황이 존재할 수 있는데, 대표적으로 (1) 한 지점에서 다른 한 지점까지의 최단 경로를 찾는 상황 (2) 한 지점에서 다른 모든 지점까지의 최단 경로를 찾는 상황 (3) 모든 지점에서 다른 모든 지점까지의 최단 경로를 찾는 상황을 생각해 볼 수 있다. 최단 경로 알고리즘은 일반적으로 그래프 자료구조를 기반으로 해 진행된다. 각 지점은 노드(Node)로 나타내고, 지점 사이를 연결하는 도로는 간선(Edge)으로 표현한다. 예를 들어, 노드는 도시, 마을, 국가 등으로, 간선은 도로, 통로 등으로..

# 다이나믹 프로그래밍 (Dynamic Programming) 현대에서 컴퓨터를 사용해도 해결하기 어려운 문제는 최적의 해를 구하는데 매우 많은 시간을 요하거나 메모리 공간을 매우 많이 요구하는 문제들이다. 그런데 어떠한 문제는 메모리 공간을 조금 더 사용하면 연산 속도를 비약적으로 상승시킬 수 있는 방법이 있다. 메모리를 적절히 사용하여 수행 시간 효율을 비약적으로 상승시키는 방법을 다이나믹 프로그래밍(Dynamic Programming)이라고 하며 동적 계획법이라고도 부른다. 다이나믹 프로그래밍은 1. 큰 문제를 작게 나누고, 2. 같은 문제라면 한 번 씩만 풀어 문제를 효율적으로 해결하는 알고리즘이다. 즉, 다이나믹 프로그래밍은 다음의 두 조건을 갖췄을 때만 사용가능하다. 1. 최적 부분 구조 (O..