오일러 피 함수 (Euler phi function) 알고리즘 문제에서 주로 나오는 정수론 중 하나인 오일러 피 함수입니다. 오일러 피 함수란 다음과 같습니다. 쉽게 말해, 1부터 n까지 범위에서 n과 서로소인 자연수의 개수를 뜻합니다. 🎈 서로소란 공약수가 1뿐이 없는 두 정수를 의미합니다. 예를 들어, 1 ~ 10 까지 범위에서 10과 서로소인 자연수를 나열해보면 다음과 같습니다. 1 , 3, 7, 9 🔨 구현 다음과 같은 과정을 통해 오일러 피 함수를 프로그래밍 언어로 구현할 수 있습니다. 📌 1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화 📌 2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(=소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열 끝까지 탐색하며 P[i] = ..

문제 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 풀이 💡 제가 푼 방법보다 더 좋은 방법이 있을 수 있습니다. 이렇게 푸는게 항상 정답은 아니니 참고하셔야 합니다. 범위는 1 ~ 10¹⁴로 입력값을 담는 타입은 long을 이용해야 합니다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); long A = Long.parseLong(s..

소수 (Prime Number) 소수란 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 의미합니다. 알고리즘에서 소수를 구하는 문제가 간혹 나오곤 하기 때문에 어떤 식으로 소수를 구하는지 알아두면 좋습니다. 브루트 포스로 구하기 가장 간단한 방법으로 2부터 n-1까지 돌면서 약수가 있는지 확인하는 방법입니다. public static boolean isPrime(int n) { if(n < 2) return false; for (int i = 2; i < n ; i++) { if(n % i == 0) return false; } return true; } 하지만 위의 경우 O(N)의 시간복잡도를 가지므로, 큰 수 여러 개가 소수인지 파악할 땐, 효율적이지 못합니다. 위의 방식을 조금..

최단 경로 알고리즘 최단 경로 알고리즘이란 가중 그래프 상의 두 정점을 연결하는 가장 짧은 경로를 찾는 방법입니다. 이러한 최단 경로 알고리즘은 지도로 최단 경로를 찾거나 , 네트워크 구축 시 비용을 최소화하는 데 사용되곤 합니다. 다양한 사용처가 있는 만큼 알아두면 좋은 알고리즘입니다. 최단 경로 알고리즘 종류 📌 다익스트라 (Dijkstra) 에츠허르 다익스트라가 고안한 유명한 알고리즘입니다. 다익스트라 알고리즘은 그래프의 방향 유무와 상관없이 하나의 정점으로부터 다른 모든 정점으로의 최단 경로를 구할 수 있습니다. 다만, 간선에 음의 가중치가 존재하면 사용할 수 없기 때문에 음의 가중치를 이용해야 한다면 다익스트라 외의 다른 알고리즘을 사용하면 됩니다. 🔨 구현 그리디와 DP가 혼합된 형태이며, 인..

💡 이 게시글에선 기본 정렬 알고리즘에 대해 다룰 것 입니다. 시간 복잡도 O(n²) 정렬 시간이 정렬할 자료의 제곱에 비례해서 늘어납니다. 이러한 이유로 잘 사용되지 않는 정렬 방식들 입니다. 버블 정렬 (Bubble Sort) 1번째와 2번째 원소를 비교하여 정렬하고, 2번째와 3번째, ..., n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 반복하는 방식으로 두 개의 인접한 요소를 비교하며 정렬하는 것을 버블 정렬이라고 합니다. 쉽게 구현할 수 있지만 시간복잡도가 O(N^2)이기 때문에 잘 사용되지 않습니다. 동일 값에 대한 원래 순서를 보장하는 안정(Stable) 정렬입니다. public class Bubble { public static void sort(int[] arr) { for (i..

우선순위 큐 (Priority Queue) 일반적인 큐의 방식(First In, First Out)과 다르게, 데이터에 우선순위를 부여하고 우선순위가 높은 데이터가 먼저 나오는 자료형을 우선순위 큐라고 합니다. 우선순위 큐 구현 우선 순위 큐는 배열, 연결 리스트, 힙을 통해 구현할 수 있습니다. 자료구조별 시간복잡도는 다음과 같습니다. enqueue 연산 dequeue 연산 정렬된 배열 O(N) O(1) 정렬된 연결 리스트 O(N) O(1) 힙 O(logN) O(logN) 일반적으로 시간복잡도 때문에 우선순위 큐는 힙으로 구현하는 편입니다. 프로그래밍 언어로 구현 Java 자바에선 기본적으로 제공하고 있습니다. PriorityQueue pq = new PriorityQueue();

힙 (Heap) 힙(Heap)이란 여러 개의 값 중에서 가장 크거나 가장 작은 값을 빠르게 찾아내는 완전 이진트리를 의미합니다. 이러한 형태의 완전 이진트리 자료구조에 Heap이라는 이름이 붙은 이유는 해당 단어가 차곡차곡 쌓아 올린 것을 의미하는데, 자료구조의 형태와 흡사하기 때문에 붙여진 이름입니다. 힙 특징 힙의 특징은 다음과 같습니다. 항상 완전 이진 트리 상태를 유지 중복 값을 허용 반 정렬 상태 (모든 노드들이 힙 종류에 따라 자식 노드보단 크거나 작지만, 형제 노드 간의 우선순위는 보장하지 못하는 상태) 부모 노드의 값은 항상 자식 노드들의 값보다 크거나 작음 힙 종류 최소 힙 (Min Heap) 부모의 값이 항상 자식들의 값보다 작거나 같은 힙을 최소 힙이라 합니다. 최대 힙 (Max He..

Union-Find (합집합 찾기) 유니온 파인드는 여러 노드가 있을 때 특정한 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘입니다. Disjoint-Set 알고리즘이라고도 불리며, 크루스칼 알고리즘에서 해당 간선이 사이클을 형성하는지 체크하는 데 사용됩니다. 🎈 연산 종류 유니언 파인드는 위에서 언급했듯이 이름 그대로 union 과 find 연산으로 이루어져 있습니다. union 연산은 각 노드가 속한 집합을 1개로 합치는 연산으로, 노드 a,b가 a ∈ A , b ∈ B일 때 union(a,b) = A∪B 를 의미합니다. find 연산은 특정 노드 a에 관해 a가 속한 집합의 대표 노드(최상위 부모)를 반환..

신장 트리 (Spanning Tree) 신장 트리란 그래프에서 모든 정점이 최소한으로 연결되어 있는 그래프를 의미합니다. 신장 트리 특징 신장 트리의 특징은 다음과 같습니다. 하나의 그래프에 여러 신장 트리가 존재할 수 있다. 모든 정점들이 연결되어 있으며, 사이클이 존재하지 않는다. n개의 정점을 가진 신장 트리는 n-1개의 간선을 가지고 있다. 최소 비용 신장 트리 (MST) 최소 비용 신장 트리(Minimum Spanning Tree)란 신장 트리 중에 사용된 간선들의 가중치 합이 가장 작은 트리를 의미합니다. 쉽게 말해, 모든 노드들을 가장 적은 비용으로 연결시킨 그래프라고 생각하면 됩니다. 두 가지의 그리디 알고리즘으로 최소 비용 신장 트리를 구할 수 있습니다. 크루스칼 알고리즘 (Kruskal..

배낭 문제 (Knapsack Problem) 알고리즘 문제 중에 다음과 같은 문제들이 나올 때가 있습니다. 어떤 가방에 담을 수 있는 무게가 한정되어있을 경우, 가방에 담을 수 있는 아이템들의 가치의 최대 합은? 최대로 담을 수 있는 무게가 주어진 배낭과 무게와 가치를 지닌 물건들이 각각 한 개씩 주어졌을 때, 배낭에 담을 수 있는 최대 가치의 합을 찾는 문제를 배낭 문제라고 합니다. 이런 문제는 다음과 같은 유형으로 나눠집니다. 분할 가능한 배낭 문제 (Fractional Knapsack Problem) 분할 가능한 배낭 문제는 주어진 아이템들을 분할해서 배낭에 담을 수 있는 문제들을 뜻합니다. 분할이 가능하다면, 무게당 가치를 계산해서 배낭에 넣으면 되는데, 이는 그리디 알고리즘으로 풀 수 있습니다...

최장 증가 부분 수열 최장 증가 부분 수열(Longest Increasing Subsequence)이란 어떤 수열이 주어졌을 때, 해당 수열의 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 의미합니다. 예를 들어 다음과 같은 수열이 주어졌다고 가정해봅시다. 3, 1, 4, 5, 9, 2, 6, 5, 3, 5 그럼 해당 수열에서 수많은 부분 수열이 나올 수 있습니다. (3) (1) (4) .... (3,1) (3, 4) ... (3,1,4) (3,1,5) ... 이러한 부분 수열 중에 오름차순으로 정렬된 가장 긴 수열(LIS)은 다음과 같습니다. (1, 4, 5, 9) (1, 4, 5, 6) (1, 2, 3, 5) (3, 4, 5, 9) (3, 4, 5, 6) 최장 증가 부분 수열 길이 구하기 보통 알..

그래프 (Graph) 그래프는 정점(Vertex)와 간선(Edge)로 이루어진 순환(Cycle) 형태의 자료구조입니다. 트리도 노드와 간선으로 이루어져있는 일종의 그래프이며, 그래프와 트리의 차이점은 순환(Cycle)이 있느냐 없느냐의 차이입니다. 이 글에서는 정점과 노드를 같은 뜻으로 사용하도록 하겠습니다. 그래프의 구조 정점 (Vertext) : 각각의 노드들 간선 (Edge) : 노드와 노드를 연결하는 선 인접 정점 (Adjacent Vertext) : 간선 하나를 두고 바로 연결된 정점 정점의 차수 (Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 (In-degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out-degree) : 방향 그래프에서 ..