일단 시작해보는 블로그

부분집합이란? 예를 들어, 집합 A = {a, b, c, d}가 있다고 하면, A의 부분집합인 B는 {}, {a}, {b}, ... {a,b}, ... {a, b, c}, ... {a,b,c,d}, 16(2^4)가지수로 표현될 수 있다. 비트마스크 연산을 이용한 부분집합의 프로그램으로의 구현 부분집합은 집합에서 각각 원소가 있다(1) 혹은 없다(0)의 경우의 수로 볼 수 있는데, 이러한 경우로 보면 '비트마스크 연산'을 이용해 표현할 수 있다. 구현과정을 두가지로 나눌 수 있다. 1. 부분집합을 이진수로 표현하기 2. 각각 이진수를 부분집합으로 변환해서 출력하기. (1이면 해당 원소 출력, 0이면 continue;) 1. 각 원소를 이진수로 표현 다음은 집합 A = {a, b, c, d}의 부분집합을 이..

이진 검색 트리 (Binary Search Tree) 임의의 이진검색트리의 노드 N은 다음 조건을 만족한다. - 노드 N의 왼쪽 서브 트리의 모든 키 값은 N보다 작다. - 노드 N의 오른쪽 서브 트리의 모든 키 값은 N보다 작다. - 같은 키 값을 갖는 노드는 없다. 이때, 이진검색트리를 중위순회(Inorder)하면 다음과 같이 키 값의 오름차순으로 노드를 얻을 수 있다. 1 - 4 - 5 - 6 - 7 - 9 - 11 - 12 - 13 - 14 - 15 - 18 이렇게 중위 순회를 하면 키 값을 오름차순으로 노드를 얻을 수 있다는 점과 구조가 단순하다는 점, 이진 검색과 비슷한 방식으로 검색이 가능하다는 점, 노드의 삽입이 쉽다는 점 등의 특징이 있어 폭넓게 사용된다. 이진검색트리 구현 package..

문제 요약 숫자(0-9), '+', '-' 버튼으로 이루어진 리모컨으로 원하는 채널로 이동 하고 싶다. 단, 숫자 누르는 버튼(0-9) 중, 고장난 버튼이 주어진다. input 값 : N, M, 고장난 숫자 버튼 output 값 : 버튼(숫자, +, - 버튼)을 총 몇번 눌러야하는지. 100번 -> N 현재 채널 : 100번 이동하려고 하는 채널 : N 고장난 숫자 버튼의 수 : M 고장난 숫자 버튼 : B1, B2, .... , Bn (M개) 해결 전략 1. 고장나지 않은 버튼을 이용해 숫자로 이동할 수 있는 채널(c)을 구한다. c를 구하면 길이를 반환하면 된다 -> 'len' -> 0-500000까지 for-loop로 하나씩 맞는지 확인한다. 2. 이동할 채널(C)와 원래 이동하려고 했던 채널(n)..

요약 Comparable : 기본적인 정렬 기준으로 정렬. default = 오름차순이지만 내림차순도 있으며, 사전순으로 숫자크기순 등등이 이에 해당된다. @Override compareTo(Object o) -> this, o 비교 -> 오름차순이면 뒤에있는 o가 더 커야하므로 this > o 일 때 맞는거니까 양수 return! Comparator : 기본적인 정렬 기준 이외의 기준으로 정렬하고자 할 때 사용. 그러니까 사전순이 아닌, 여러 조건이 있을 경우라던지, 문자열의 길이 순, 객체내에 접근해서 값을 비교해야한다던지 등등 일 때 사용한다. @Override compare(Object o1, Object o2) -> o1, o2비교 -> 오름차순이면 뒤에있는 o2가 더 커야하므로 o1 < o2 ..

Set Interface 1. 데이터 중복 No! 데이터를 중복해서 저장할 수 없다. 2. 저장 순서가 보장되지 않음. index로 관리하는 것이 아니기 때문 . 3. Iterator의 객체(반복자)를 통해 반복문을 돌릴 수 있다. 이것도 인덱스로 관리하는 것이 아니기 때문. 대표적으로 HashSet, TreeSet, LinkedHashSet 등이 있다. HashSet 전형적인 Set 인터페이스의 특성을 갖추고 있다. 데이터 중복x, 입력한 순서대로 저장되지 않는다. package hash; import java.util.HashSet; import java.util.Set; // HashSet은 순서가 따로 없고 중복되지 않는다. if 중복 -> false를 반환한다. public class HashS..

Iterator는 자바의 Collection framework에서 Collection에 저장되어 있는 요소들을 읽어오는 방법을 표준화한 것이다. List나 Set인터페이스를 구현하는 컬렉션은 iterator()가 컬렉션의 특징에 맞게 설계되어있다. Iterator는 인터페이스이다. public interface Iterator{ boolean hasNext(); Object next(); void remove(); } 1. boolean hasNext() : 읽어 올 요소가 남아있는지 확인하는 메소드 2. Object next() : 읽어 올 요소가 남아있는지 확인하는 메소드 3. void remove() : next()로 읽어 온 요소를 삭제한다. next()호출 후, remove()를 사용한다.

Hashset은 중복을 허용하지 않고 순서가 없다. 만약 중복을 허용하지 않는 순서가 있는 집합을 만들고 싶다면 LinkedHashSet을 사용하면 된다. package hash; import java.util.HashSet; import java.util.Iterator; public class HashSet_Union_Inter { public static void main(String[] args) { HashSet SetA = new HashSet(); // [1, 2, 3, 4, 5] HashSet SetB = new HashSet(); // [1, 2, 4, 5, 6] HashSet SetUnion = new HashSet(); // [1, 2, 3, 4, 5, 6] HashSet SetInt..

문자열로 정의한 정규표현식은 사용되기 전에 반드시 Pattern 클래스의 인스턴스로 컴파일 되어야한다. 컴파일된 패턴은 Matcher 객체를 만드는데 사용되며, Matcher 객체는 임의의 입력 문자열이 패턴에 부합되는지 여부를 판가름하는 기능을 담당한다. 또한, Pattern객체들은 비상태 유지 객체들이기 때문에 여러개의 Matcher 객체들이 공유할 수 있다. 목표> String str = "나는 123456788입니다."; 다음 문자열에서 숫자만 추출하고 싶어요! 1. Pattern p = Pattern.compile("([0-9])+"); 여기서 [0-9]라고 하면 숫자 한글자씩 나온다. ([]이거 자체가 범위를 쓸 수 있지만 한 글자를 의미하는 것이라서 그렇다.) 원하는 답(123456788)을..