Coding Diary

1. 개념 하나의 배열을 크기가 같은 2개의 배열로 분할한다. 분할은 분할 대상의 배열 길이가 2이상이면 계속 반복하다 분할 대상 배열 길이가 1이하가 되면 반복을 멈춘다. 분할된 배열을 병합하는데, 정렬을 하면서 병합을 진행한다. 병합을 진행할 때는 병합 대상이 되는 2개의 배열 각각에 포인터를 두고, 포인터가 가리키는 원소 중 더 작은 것을 병합 결과 배열에 놓고, 병합 결과 배열에 놓인 원소의 포인터는 증가시킨다. 2. 특징 분할 정복 방법이 적용된다. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 각각을 해결할 때는 재귀적으로 함수 호출을 진행하여 해결한다. 만약 배열로 데이터를 다루면 제자리 정렬이 아니다. 병합된 내용을 담을 추가 메모..

1. 개념 배열에서 피봇을 하나 정한다. 맨 왼쪽에서 시작해서 배열을 살피는 화살표가 하나 있고, 맨 오른쪽에서 시작해서 배열을 살피는 화살표가 하나 있다. 왼쪽 시작 화살표를 옮겨가며 피봇보다 크거나 같은 원소를 찾는다. 오른쪽 시작 화살표를 옮겨가며 피봇보다 작은 원소를 찾는다. - a 만약 왼쪽 시작 화살표가 원소를 하나 찾고, 오른쪽 시작 화살표가 원소를 하나 찾으면 둘을 교환한다. 교환 후 왼쪽 시작 화살표는 아까 찾은 거 이후 부터 다시 피봇보다 크거나 같은 원소를 찾고, 오른쪽 시작 화살표는 아까 찾은 거 이후 부터 다시 피봇보다 작은 원소를 찾는다. - b-1 만약 왼쪽 시작 화살표와 오른쪽 시작 화살표가 만나면 만난 위치에 있는 원소와 피봇을 교환한다. 교환된 피봇은 확정된다. - b-2..

1. 개념 배열의 원소를 하나씩 살피면서, 살피는 원소와 살피는 원소 앞에 있는 원소를 비교해서 만약 앞에 있는 원소보다 작다면 살피는 원소를 앞으로 보낸다. 더 이상 앞으로 보낼 수 없을 때까지 반복한다.(오름차순 기준) 2. 특징 1) 장점 안정한 정렬 방법(정렬하면서 같은 원소가 있어도 위치가 변하지 않는다) 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다. 대부분위 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다. 2) 단점 비교적 많은 레코드들의 이동을 포함한다. 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다. 3. 시간복잡도 1) 최선(다 정렬되어 들어올 경우) 비교횟수 target이 target 바로 전 것과 비교되고 ..

1. 개념 일반적인 큐의 구조를 가짐. 하지만 먼저 들어온 것이 먼저 나가는 구조가 아님. 들어올 때 우선순위에 맞게 정렬이 되어 들어오고, 들어온 것들 중 정해놓은 우선순위가 가장 높은 것이 먼저 나가는 구조. 나가고 나서 우선순위에 맞게 다시 정렬이 됨. 2. 특징 값을 비교해야 하므로 null을 허용하지 않음 값을 비교해야 하므로 우선순위 큐에 삽입될 객체들은 Comparable Interface에 있는 compareTo 메서드가 구현되어 있는 객체여야 함. 내부 구조는 이진트리 힙으로 되어 있음 값이 들어올 때 마다 일단 이진트리 맨 마지막에 값을 넣음 그리고 부모 노드와 비교해가며 우선순위에 맞게 정렬을 진행함 값이 나갈 때는 트리의 루트를 이진트리 맨 마지막 노드와 바꿈 맨 마지막을 나가게 하..

1. 개념 한 쪽에서는(맨 뒤) 넣을 수만 있고, 다른 한 쪽에서는(맨 앞) 지울 수만 있는 자료구조 2. 특징 선입선출 방식이다. 즉 먼저 들어온 게 먼저 나간다 3. 자바에서 구현 Queue의 인터페이스가 있고, 이 인터페이스를 구현한 클래스를 사용해야 한다. 그 클래스에는 LinkedList ArrayDeque PriorityQueue 가 있다. 4. 연산 1) offer Enqueue 수행. 큐가 꽉 차 있으면 false 리턴 2) add Enqueue 수행. 큐가 꽉 차 있으면 예외 발생 3) poll Dequeue 수행. 큐가 비어 있으면 null 리턴 4) remove Dequeue 수행. 큐가 비어 있으면 예외 발생 5) clear 한 번에 모든 요소 제거 6) peek 큐의 첫 번째 데이..

1. 개념 날짜를 표현하는 클래스 2. 생성 Date now = new Date(); //현재 날짜 생성 Date d = new Date(2020, 1, 1); // 2020년 1월 1일 날자 생성 3. 메서드 equals() 두 날짜가 같은 날자면 true 리턴 before() 호출한 것이 전달된 것보다 이전이면 true Date d1 = new Date(2020, 1, 1); Date d2 = new Date(2019, 2, 2); d1.before(de); // false 리턴 after() 호출한 것이 전달된 것보다 나중이면 true

1. 개념 문자열이 특정 구분자로 연결되어 있을 경우, 구분자를 기준으로 부분 문자열을 분리하기 위해 사용하는 java.util 패키지에 있는 클래스 2. 방법 StringTokenizer st = new StringTokenizer("문자열", "구분자") 3. 특징 구분자에 공백을 주면 문자 하나씩 구분된다 4. 메서드 countTokens() 꺼내지 않고 남아 있는 토큰의 수 hasMoreTokens() 남아 있는 토큰이 있는지 여부 nextToken() 토큰을 하나씩 꺼내옴 5. split와 stringTokenizer의 차이 split stringTokenizer 위치 String 클래스에 있는 메서드 java.util 패키지에 있는 클래스 구분 방법 정규표현식으로 문자열 구분 문자 또는 문자열..

1. 스트림 1) 개념 데이터가 입출력되는 곳 2) 종류 구분 바이트 기반 스트림 문자 기반 스트림 입력 스트림 출력 스트림 입력 스트림 출력 스트림 최상위 클래스 InputStream OutputStream Reader Writer 하위 클래스 XXXInputStream XXXOutputStream XXXReader XXXWriter 입력 스트림 프로그램이 데이터를 입력받음 출력 스트림 프로그램이 데이터를 보냄 바이트 기반 스트림 그림, 멀티미디어, 문자 등 모든 종류의 데이터를 받고 보낼 수 있음 문자 기반 스트림 문자만 받고 보낼 수 있도록 특화 3) 특징 java.io 패키지에서 사용 가능 2. Reader 1) 개념 문자 기반 입력 스트림의 최상위 클래스로 추상 클래스. 모든 문자 기반 입력 스..

1. 개념 T타입의 객체를 감싸는 래퍼 클래스 2. 특징 최종 연산의 결과를 그냥 반환하는 게 아니라 Optional 객체에 담아서 반환을 하면 반환된 결과가 null인지 매번 if문으로 체크하는 대신 Optional에 정의된 메서드를 통해서 간단히 처리 가능 널 체크를 위한 if문 없이도 NullPointerException이 발생하지 않는 보다 간결하고 안전한 코드를 작성하는 것이 가능 3. Optional 객체 생성하기 1) of 값이 null이면 NullPointerException을 발생시킴 들어갈 값이 null 아닌 것이 확실할 때 사용 2) ofNullable 값이 null이어도 NullPointerException을 발생시키지 않음 들어갈 값이 null인 것이 확실하지 않을 때 사용 3) ..

1. 개념 배열의 원소를 순서대로 살피면서, 살피는 원소 아래에 있는 모든 원소를 확인해서 만약 더 작은 것이 있다면 현재 살피는 원소와 해당 원소를 바꾼다. 2. 특징 제자리 정렬 알고리즘의 하나(입력 배열 이외에 추가 메모리를 요구하지 않음) 1) 장점 구현이 쉽다 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 2) 단점 안정 정렬이 아니다(값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.) 정렬 규칙이 다수이거나 특정 순서를 유지해야 할 때 문제가 될 수 있다. 시간복잡도 상 효율이 좋지 않음 3) 단점 보완 방법 이중 선택 정렬 한 번의 탐색에서 최솟값과 최댓값을 같이 찾는 방법이다. 탐색 횟수가 절반으로 줄어들게 된다. 탐색을 응용하여 개선 한 번의 탐..