풀소유

수학에서 오일러 피 함수 P[N] 의 정의는 1부터 N가지 범위에서 N과 서로소(공약수가 1뿐인 관계)인 자연수의 개수를 뜻한다. 오일러 피 함수 구현 public class EulerPhiFunction { public static void main(String[] args) { int n = 10; // 원하는 정수 n 값 입력 int result = eulerPhi(n); System.out.println("Euler's Phi function for " + n + " is: " + result); } // 오일러 피 함수 구현 public static int eulerPhi(int n) { int result = n; for (int i = 2; i * i 1) { result -= result ..

기수 정렬은 비교 기반 정렬 알고리즘이 아닌, 자릿수를 이용하여 정렬하는 안정적인 정렬 알고리즘 중 하나이다. 주로 정수나 문자열과 같이 각 자리의 의미가 있는 데이터를 정렬할 때 사용된다. 가장 낮은 자리수부터 정렬하고 한 자릿수가 정렬되면 다음 자릿수로 이동하여 같은 과정을 반복한다.시간 복잡도는 O(k*n)으로 정수나 문자열의 자리수 * 배열의 크기이다. 우선순위 큐를 이용한 방법 import java.util.PriorityQueue; public class RadixSortWithPriorityQueue { public static void radixSort(int[] arr) { // 가장 큰 자리수의 수 찾기 int maxDigit = getMaxDigit(arr); // 각 자리수에 대해 ..

차이점 퀵정렬과 병합 정렬은 비슷한 듯 다른 알고리즘을 가지고 있다. 퀵 정렬 병합 정렬 동작 방식 분할 정복(Divide and Conquer) 방식을 사용. 배열을 피벗(pivot)을 기준으로 두 개의 부분 배열로 분할하고, 각 부분 배열을 재귀적으로 정렬 분할 정복(Divide and Conquer) 방식을 사용. 배열을 나눠 정렬하고 병합하는 방식 평균 및 최악 시간 복잡도 평균 O(n logn) 최악의 경우(피벗이 최솟값이거나 최대값) O(n^2) 항상 O(n log n) 안정성 동일한 값에 대해 상대적인 순서가 변할 수 있다. 동일한 값에 대해 상대적인 순서가 유지된다. 공간 복잡도 재귀 호출에 따른 스택 공간을 고려해야 한다. 입력 배열 크기에 비례하는 공간이 필요. 따라서 메모리 사용량이 ..

얼마 전, 모두 알만한 회사에 코딩테스트를 봤다. 120분에 1문제를 풀면 되는 테스트로 난이도가 꽤 있을 거라 생각하고 준비했지만 결국 풀지 못했다. 테스트가 끝나고 나서도 하루 종일 어떻게 풀어야 할지 고민했던 거 같다. 다음 날 저녁, 불현듯 어떻게 풀어야 할지 떠오르면서 아쉬움이 밀려와 잠을 설쳤다. 아침에 눈뜨자마자 노트북을 열고 다시 문제를 풀어보았다. 생각해 보면 그렇게 어려운 문제도 아니었는데 긴장했었나 싶다. 아쉬운 마음에 블로그에 코드라고 남겨본다. 어제 실패했으니 내일의 성공 확률은 더 높아졌을 거라 생각한다. import java.util.*; public class Solution { public int solution(String[] tickets, int roll, String..

Trie(트라이)는 문자열 검색에 효과적인 자료 구조로, 특히 사전 검색이나 자동 완성 기능 등에 자주 사용된다. 이 자료 구조는 각 노드가 문자 하나를 나타내며, 각 노드 사이의 연결은 문자열의 일부를 나타낸다. Trie는 문자열 검색에 뛰어난 성능을 보이는데, 검색 시간은 문자열의 길이에 선형적으로 비례한다. 즉, O(문자열의 길이) 의 시간 복잡도를 갖는다. class TrieNode { Map children; boolean isEndOfWord; public TrieNode() { children = new HashMa(); } } class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } public void ins..

카탈란 수는 다양한 수학적 문제와 컴퓨터 과학 알고리즘에서 자주 나타나는 수이다. Cn = C0 * Cn-1 + C1 * Cn-2 + .... + Cn-1 * C0이라는 공식을 가지고 있다. 대표적인 문제 몇가지이다. 오일러의 삼각형(n+2의 도형을 삼각형으로 분할하는 경우의 수) 알파벳에 괄호 넣기(n+1개의 문자사이에 괄호 넣는 경우의 수) 연쇄행렬곱셈 문제(곱셈의 순서가 가질 수 있는 경우의 수) Dyck 경로 (n*n개의 격자에서 절반을 갈 수 없을 때 경우의 수) 프로그래머스 올바른 괄호의 개수 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12929 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개..

크루스칼 알고리즘은 그리디 알고리즘의 일종으로, 최소한의 비용으로 모든 정점을 연결하는 최소 신장 트리를 찾는 데 사용된다. 이 알고리즘은 간선들을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않으면서 간선을 추가하여 최소 신장 트리를 만들어 간다. 동작 순서 초기화: 에지 리스트와 유니온-파인드가 필요하다. 가중치 기준 정렬: 가중치가 작은 에지부터 연결을 시도하기 때문에 가중치를 기준으로 오름차순 정렬한다. 연결 시도: 가중치가 작은 에지부터 순회하며 이미 연결된 정점이 아닌 정점들을 연결한다. 이 때 유니온-파인드 알고리즘이 필요하다. import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; publ..

플로이드-와샬 알고리즘은 모든 정점 간의 최단 경로를 찾는 알고리즘으로, 음의 가중치를 가진 그래프에서도 사용할 수 있습니다. 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루지는 것이 이 알고리즘의 핵심 아이디어이다. (S -> E까지의 최단 거리는 S -> K -> E의 최단 거리와 같다.) 이 원리로 다음과 같은 점화식을 도출할 수 있다. D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 해당 알고리즘은 3중 for 문으로 이루어져 있어 O(V^3)에 시간복잡도를 가지고 있다. 알고리즘 동작 순서 초기화: 최단 거리를 저장하는 2차원 배열을 초기화한다. 초기에는 직접적인 간선이 존재하면 해당 가중치를, 그렇지 않으면 무한대(INF)로 설정한다. 동적 ..

벨만-포드 알고리즘은 모든 정점 간의 최단 경로를 찾기 위한 알고리즘 중 하나이다. 다익스트라 알고리즘이 간선의 가중치가 음수일 때 제대로 동작하지 않는 경우가 있지만, 벨만-포드 알고리즘은 음의 가중치를 가진 그래프에서도 사용할 수 있다. 알고리즘의 기본 아이디어는 각 정점에 대해 현재까지 발견한 최단 경로의 추정치를 저장하고, 이를 반복적으로 업데이트하여 최종적으로 최단 경로를 찾아내는 것이다. 그리고 마지막에 음의 사이클이 있는지를 확인하여 음의 사이클이 있다면 최단 경로를 정의할 수 없다는 것을 알 수 있다. 시간 복잡도는 O(VE)이다. 알고리즘 동작 원리 초기화: 시작 정점을 제외한 모든 정점에 대한 최단 거리를 무한대로 초기화하고, 시작 정점의 최단 거리를 0으로 설정한다. 모든 에지를 확인..

다익스트라 알고리즘은 그래프에서 출발 노드와 모든 노드 간의 최단 거리를 찾는 데 사용되는 효율적인 알고리즘 중 하나이다. 이 알고리즘은 양의 가중치를 가진 간선으로 이루어진 그래프에서 사용할 수 있다. 시간 복잡도는 O(ElogV)이다. 알고리즘 동작 원리 시작점 설정: 최단 경로를 찾을 시작점을 선택한다. 거리 초기화: 시작점을 제외한 모든 정점까지의 거리를 무한대로 설정하고, 시작점의 거리를 0으로 설정한다. 우선순위 큐 초기화: 우선순위 큐를 사용하여 현재까지의 최단 거리를 가진 정점을 방문한다. 시작점을 우선순위 큐에 삽입한다. 최단 경로 갱신: 우선순위 큐에서 가장 최단 거리를 가진 정점을 추출하고, 해당 정점과 이웃한 정점들의 거리를 갱신한다. 새로운 거리가 더 짧으면 해당 정점의 거리를 갱..