비둘기집 이론(Pigeonhole Principle) 비둘기집 이론 : n개의 비둘기집에 n+1마리의 비둘기를 나누어 넣는다면, 적어도 한 집에는 2마리가 들어간다는 이론 증명 - 모순 증명법(Contradiction) p : 비둘기집(x)이 n개, 비둘기(y)가 k마리라면 (k ≥ n + 1) q : 적어도 한 집에는 두 마리 이상이 들어간다 Contradiction : ￢(p→q) = p∧￢q 즉, p이고 q가 아니면 거짓이다를 증명하면 비둘기집 이론 성립. ￢q : 한 집에는 비둘기가 1마리 이하이다. 한 집에 비둘기가 한 마리 이하라면 총 비둘기 수 k는 k ≤ n이 된다. 이때 p의 조건에서 k ≥ n + 1이라는 조건이 있었고, 이는 true이기에 동시에 성립할 수 없음. 모순이 일어나므로, ..
HashSet을 이용한 집합연산 교집합 : .retainAll() 메소드 이용 HashSet s1 = new HashSet(Arrays.asList(1, 2, 3, 4, 5)); HashSet s2 = new HashSet(Arrays.asList(2, 4, 6, 8, 10)); s1.retainAll(s2); System.out.println(s1); // output : [2, 4] 합집합 : .addAll() 메소드 이용 HashSet s1 = new HashSet(Arrays.asList(1, 2, 3, 4, 5)); HashSet s2 = new HashSet(Arrays.asList(2, 4, 6, 8, 10)); s1.addAll(s2); System.out.println(s1); // ou..
백준 2110번 : 공유기 설치 등급 : Gold III 2473번: 세 용액 (acmicpc.net) 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 사용 알고리즘 : Two_Pointer 사용 자료구조 : Vector 시작값 하나를 고정하고, 나머지는 기존과 같은 투 포인터를 이용한 풀이. 이외에는 본래 투 포인터와 동일하다. #include #include #include using namespace std; #define INF 2e18 #define ll long long vec..
KMP 알고리즘 (Knuth-Morris-Pratt Algorithm) KMP 알고리즘 (수행시간 : O(N)) : 문자열 탐색에 있어 겹치는 부분을 미리 탐색해 불필요한 검색을 하지 않도록 점프시키는 알고리즘. 일반적인 문자열 탐색 알고리즘을 사용하는 경우, 글의 길이가 M, 패턴의 길이가 N이라고 하면 수행시간은 O(MN)이 된다. 이때 어떻게 하면 이러한 중복 문자열 탐색을 줄일 수 있을까 하여 나온 방법이 KMP 알고리즘이다. 수행 원리 문자열을 탐색할 때 겹치는 부분이 있는데, 일반적인 탐색의 경우 이를 무시하고 다시 처음부터 탐색을 진행하게 된다. KMP는 미리 탐색한 이러한 겹치는 문자열을 어떻게 활용할지를 고안하여 만들어낸 알고리즘이다. 우리는 접두사(Prefix)와 접미사(Suffix)의..
스트림(Stream) Stream : 배열, 컬렉션 등의 데이터를 하나씩 참조하여 함수형으로 처리하는 방법. 스트림의 요소 생성 : 스트림의 생성. - 배열의 경우 int arr1[] = new int[]{1, 2, 3}; IntStream st1 = Arrays.stream(arr1); String arr2[] = new String[]{"a", "b", "c"}; Stream st2 = Arrays.stream(arr2); - 컬렉션의 경우 HashSet set = new HashSet(); Stream st2 = set.stream(); - Builder : 스트림에 데이터를 추가하는 연산. 모든 연산이 끝난 이후 .build()를 입력하여 종료. Stream st = Stream.builder()..