풀소유

수학에서 오일러 피 함수 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) 안정성 동일한 값에 대해 상대적인 순서가 변할 수 있다. 동일한 값에 대해 상대적인 순서가 유지된다. 공간 복잡도 재귀 호출에 따른 스택 공간을 고려해야 한다. 입력 배열 크기에 비례하는 공간이 필요. 따라서 메모리 사용량이 ..

자바에서 내부 클래스는 다른 클래스 내에 정의된 클래스를 말한다. 내부 클래스는 특정 클래스에 종속되어 있으며, 외부 클래스의 멤버에 접근할 수 있다. 내부 클래스는 코드의 구조화, 은닉성, 캡슐화를 강화하는 데 사용될 수 있다. 장점 내부 클래스에서 외부 클래스의 멤버들을 쉽게 접근할 수 있다. 사용이 제한된 클래스를 내부에 둠으로써 코드의 복잡성을 줄일 수 있다. 종류 인스턴스 클래스(Instance Class) 외부 클래스의 멤버변수 선언위치에 선언하며, 외부 클래스의 인스턴스멤버처럼 다루어진다. 주로 외부 클래스의 인스턴스 멤버들과 관련된 작업에 사용될 목적으로 선언된다. public class OuterClass { private int outerField; public class InnerCl..

쓰레드 동기화란?쓰레드 동기화는 여러 쓰레드가 공유 자원에 접근할 때 발생할 수 있는 데이터 불일치와 같은 문제를 해결하는 기술이다. 이를 통해 프로그램이 예측 가능하고 안전하게 실행될 수 있도록 한다. synchronized 키워드자바에서는 synchronized 키워드를 사용하여 메소드나 블록을 동기화할 수 있다. 이를 통해 특정 코드 영역에는 하나의 쓰레드만 접근할 수 있도록 보장할 수 있다.// 메소드 동기화public synchronized void synchronizedMethod() { // 동기화가 필요한 코드}// 블록 동기화public void someMethod() { // 비동기화 코드 synchronized (lockObject) { // 동기화가 필요..

얼마 전, 모두 알만한 회사에 코딩테스트를 봤다. 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)로 설정한다. 동적 ..