서로소 집합 (Disjoint-set) 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들 (교집합 X) 집합에 속한 하나의 특정 멤버를 통해 각 집합을 구분 (대표자) 연결 리스트 또는 트리로 서로소 집합을 표현 Make-Set(x) p[x] 175 */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class MST1_KruskalTest { static class Edge implements Comparable{ int from, to, weight..

그래프 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:M 관계를 가지는 원소를 표현하는데 용이 정점 (Vertex) : 그래프의 구성요소로 하나의 연결점 간선 (Edge) : 두 정점을 연결하는 선 차수 (Degree) : 정점에 연결된 간서의 수 양방향 그래프 (최대 V * (V-1) / 2 개의 간선) 단반향 그래프 (최대 V * (V-1) 개의 간선) 인접 행렬 두 정점을 연결하는 간선의 유무를 행렬로 표현 V x V 정방 행렬 행번호와 열 번호는 그래프의 정점에 대응 두 정점이 인접되어 있으면(또는 가중치) 1 그렇지 않으면 0으로 표현 무향 그래프 : i번째 행의 합 = i번째 열의 합 = Vi의 차수 유향 그래프 : 행 i의 합 = Vi의 진출 차수, 열 i의 합 = Vi의 진입 차수 희..

완전 검색 순열(Permutation) 서로 다른 n개 중 r개를 선택하는 과정에서 순서가 의미가 있는 경우 - nPr 예 ) 5개의 도시 중 출발지와 도착지가 같은 최소 비용 거리 반복문 // {1, 2, 3}을 포함한 모든 순열 생성 : 3P3 // 동작 과정 1. 1~3 수 선택 시도, 2. 중복 수 필터링, 3. 다음 자릿수 선택 - 선택 이후 1,2,3 반복 for i from 1 to 3 // 처음 수 선택 for j from 1 to 3 // 두번째 수 선택 if j != i then // 첫번째와 두번째가 다르다면 for k from 1 to 3 // 세번 째 수 선택 if k != i and k != j then // 세번째 수가 첫번째, 두번째와 다른 경우 print i,j,k // 세..

https://www.acmicpc.net/problem/10266 10266번: 시계 사진들 상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시계 바 www.acmicpc.net 알고리즘 처음엔 정렬해서 KMP 알고리즘으로 비교하려고 했다. 하지만 바늘의 수가 20만까지 주어지기 때문에 시간초과가 난다. 다른 블로그를 참조해서 배열에 담아 비교하는 방법을 터득했다. 주어지는 정수는 0부터 36만까지이므로 arr을 텍스트로 (36*2인 72만 크기)로 만들고 arr2를 찾을 패턴인 (36만)으로 생성해서 입력받는 값을 배열에 담는다. 예시를 봐보자. 문제의 예제 입력 1번을 ..

https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 알고리즘 s = a^n을 만족하는 가장 큰 n을 찾는다는 것은 문자열의 패턴의 최대 갯수를 찾으라는 문제다. 주의해야 할 점은 문자열의 최대 길이는 백만글자 미만이다. 인덱스별 탐색을 하려면 O(n^2)으로 시간초과가 날 것이다. 즉, 문자열 비교를 효율적으로 탐색하기 위해 KMP 알고리즘을 사용해야 한다. KMP 알고리즘이란? https://sasca37.ti..

KMP 알고리즘 KMP는 알고리즘을 설계한 Knuth-Morris-Pratt의 앞글자를 하나씩 따서 만든 알고리즘으로 문자열 검색을 효율적으로 할 수 있는 알고리즘이다. (ctrl + f 해서 찾는 검색 알고리즘이 KMP 알고리즘) 전체 텍스트의 길이를 N, 찾고자하는 문자열을 M이라 할 때 각 인덱스 별 비교를 하면 시간 복잡도는 O(NM)이지만, KMP 알고리즘을 적용하면 O(N+M)으로 찾을 수 있다. 실패 함수 KMP 알고리즘의 원리는 실패함수를 이용하는 것이다. 실패 함수란 문자 매칭에 실패했을 때 전체 비교인 O(NM)을 효율적으로 처리하기 위해 건너 뛸 자리를 구하기 위한 함수이다. 즉, 텍스트와 패턴이 불일치 상황에서 접두사 / 접미사가 일치한 최대 길이를 구하여 다음에 건너 뛸 자리를 결..

객체 지향 OOP is A PIE Abstraction (추상화) : 현실 객체를 추상화해서 클래스를 구성 Polymorphism(다형성) : 하나의 객체를 여러 가지 타입으로 참조 (메서드 다형성, 타입 다형성) Inheritance(상속) : 부모 클래스를 물려받아 자식이 재정의 Encapsulation(캡슐화) : 데이터를 외부에 직접 노출시키지 않고 메서드를 이용해 보호 Type Primitive Type (기본형) 미리 정해진 크기의 Memory Size로 표현 변수 자체에 값 저장 long 보다 더 큰 값을 표현하고 싶을 땐 무한대에 가까운 BigInteger를 사용한다. Reference Type(참조형) 크기가 미리 정해질 수 없는 데이터의 표현 변수에는 실제 값을 참조할 수 있는 주소만 ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 알고리즘 부분합의 짧은 길이를 출력하는 문제로 이중 반복문을 사용하면 시간초과가 발생하며, 투포인터를 사용해야하는 문제이다. start, end를 0으로 초기화한 후, end++를 해가며 sum의 값을 더한다. sum이 S보다 크면 길이를 측정하고, start를 end 전까지로 이동한다. 풀이 import java.io.*; import java.util.StringTokenizer..