풀소유

자바에서 내부 클래스는 다른 클래스 내에 정의된 클래스를 말한다. 내부 클래스는 특정 클래스에 종속되어 있으며, 외부 클래스의 멤버에 접근할 수 있다. 내부 클래스는 코드의 구조화, 은닉성, 캡슐화를 강화하는 데 사용될 수 있다. 장점 내부 클래스에서 외부 클래스의 멤버들을 쉽게 접근할 수 있다. 사용이 제한된 클래스를 내부에 둠으로써 코드의 복잡성을 줄일 수 있다. 종류 인스턴스 클래스(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)로 설정한다. 동적 ..

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

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

위상 정렬(Topological Sorting)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 시간 복잡도는 O(노드의 수:V + 에지 수:E)이다. DFS를 이용하는 방법과 BFS를 이용하는 방법이 있다. 위상 정렬 수행 과정진입 차수가 0인 노드를 큐에 저장한다.큐에서 데이터를 poll 해 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다.감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer 한다.큐가 빌 때까지 1~3을 반복한다. import java.util.*; public class topologicalSort { public static List topologicalSort(..