two pointer technique배열이나 리스트와 같은 선형 구조에서 두 개의 점(포인터)를 이용하여 원하는 조건을 만족하는 부분 구조를 효율적으로 찾아내는 알고리즘 기법특정 합을 만족하는 두 수를 찾거나 부분 배열의 최소 길이를 찾는 문제 등에 활용같은 방향으로 이동보통 right 포인터가 먼저 조건을 만족할 때까지 이동하고 조건을 만족하는 상태에서 left 포인터를 이동시키면서 조건을 유지할 수 있는 최소, 최대 범위를 찾음연속된 부분 구조를 찾는 문제에 적용public static int solution(int[] arr, int x) { int count = 0; int sum = 0; int left = 0; int right = 0; while(left x) { sum -..

해시데이터의 추가와 삭제를 효율적으로 수행할 수 있는 방법String 기반으로 정보를 기록하고 관리할 때 사용1. 전화번호부와 같음2. key가 String인 경우가 대부분3. put / get / getOrDefault해시법 (hashing)데이터를 저장할 위치(인덱스)를 간단한 연산으로 구현하는 것표에 정리한 값을 해시 값(hash value)이라고하며, 데이터에 접근할 때 사용해시 테이블의 요소 = 버킷인덱스012345678키 값56142029343751-해시 값56522716-해시값 = 각 요소의 값을 배열의 사이즈로 나눈 나머지 변경인덱스012345678키 값1-3729--145134-키 값2--20--56--더보기기존의 배열에 값을 추가하는 방법1. 이진검색법으로 삽입할 위치 조사2. 그 위치..

트리 비선형구조 그래프는 사이클이 있고, 트리는 사이클이 존재하지 않음 계층 관계를 나타내는 자료구조 트리는 저장위치를 찾아서 저장해야 하고, 삭제시 트리의 일부를 재구성해야하므로 링크드 리스트보다 추가/삭제 시간이 더 걸리는 대신 배열이나 링크드 리스트에 비해 검색과 정렬 기능이 더 뛰어남 용어 노드(node) 마디 A, B, C, D, E, F, G 간선(edge) 가지, 링크 루트(root) 트리의 가장 윗부분에 위치하는 노드 A 리프(leaf) 단말 노드(terminal node) 바깥 노드(external node) 트리의 가장 아랫부분(가장 마지막)에 위치하는 노드 D, E, F, G 간 노드(non-terminal node) 안쪽 노드 루트 포함, 리프가 아닌 노드 A, B, C 자식(chi..

리스트 - 데이터를 순서대로 나열해 놓은 자료구조 선형 리스트 배열로 선형 리스트 구현시 다음 노드 꺼내기 순서대로 데이터가 저장되어 있기 때문에 1만큼 큰 인덱스를 갖는 요소에 접근 노드의 삽입, 삭제 삽입, 삭제 시 다음의 모든 요소를 하나씩 뒤로 밀거나 앞으로 당겨야 함 선형 리스트 장점 1. 구조가 간단 2. 데이터를 읽어오는데 걸리는 시간이 가장 빠름 선형 리스트 단점 1. 쌓이는 데이터의 크기를 미리 알아야 함 2. 밀거나 당겨야 하기 때문에 효율이 좋지 않음 연결 리스트 - 포인터 연속된 노드의 결정체 자신과 같은 자료형의 인스턴스를 가리킴, 자기 참조(self-referential)형 클래스형 변수인 data는 데이터 그 자체가아니라 데이터에 대한 참조 꼬리 노드의 뒤쪽 포인터 값을 nul..

셸 정렬 단순 삽입 정렬의 장점은 살리고, 단점을 보완하여 좀 더 빠르게 정렬 장점: 정렬을 마쳤거나 마친 상태에 가까우면 속도가 빨라짐 단점: 삽입할 위치가 멀리 떨어져 있으면 이동해야 하는 횟수가 많아짐 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬 수행 ▶ 그룹을 합치면서 정렬 반복(이동 횟수 줄임) i = 8일 때 j = 4-4 = 0인데 조건으로 j >= 0이 가능하게 만들어줌으로써 구간이 [4] ~ [12]까지로 바뀌고 계속 반복 실행 static void shellSort(int[] a, int n) { //n = 배열의 길이 for(int term = n/2; term > 0; term /= 2) { //{8, 1, 4, 2, 7, 6, 3, 5} 일 때 h = 8, 4,..

재귀 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 함 이게 안되면 디바이드 앤 컨커, 다이나믹 프로그래밍 다 안됨 재귀호출: 자기 자신과 똑같은 메서드를 호출 선언적 프로그래밍(declarative programming) = 목적만 설정해 주면 중간 과정은 컴퓨터가 알아서 함 : 언제 종료하고, 이 문제를 어떤 식으로 정의 할 수 있는가 명시 직접(direct) 재귀: 자신과 같은 메서드 호출 간접(indirect) 재귀: 메서드 a가 메서드 b를 호출, 다시 메서드 b가 메서드 a를 호출 재귀함수를 짜는 법 1. 종료 조건 2. 문제의 정의 팩토리얼 음이 아닌 정수의 팩토리얼 1. 0! = 1 2. n > 0 이면 n! = n * (n-1)! ..

스택 (stack)데이터를 일시적으로 저장하기 위한 자료구조후입선출, LIFO(Last In First Out)메서드를 호출하고 실행할 때 프로그램 내부에서 스택 사용arr[0] = bottomarr[n-1] = top스택 만들기필드 & 생성자package chap04_1;public class IntStack { private int max; //스택 용량, 배열 길이 private int ptr; //스택 포인터, 현재 쌓여 있는 데이터의 수(인덱스가 아님) private int[] stk; //스택 본체 //실제로는 본체를 참조하는 배열 변수로 배열 본체는 생성자에서 생성함 //실행 시 예외: stack이 비어있음 public class EmptyIntStackException extends R..

유클리드 호제법 (Euclidean algorithm)두 개의 수가 있을 때, 최대공약수를 구하는 알고리즘소인수분해를 하면 효율적이지 않고, 두 수가 크면 시간 복잡도는 계속 증가하므로 유클리드 호제법 알고리즘을 사용하면 문제를 쉽게 해결 가능함GCD(a, b) = GCD(b, r)r : a mod b (a에서 b를 나눈 나머지)조건: 0 ≤ r a, b 를 서로 나눌 때, r=0 이 되면 그 때 b가 최대공약수나머지가 0이 되는 시점까지 계속해서 동일한 연산을 진행해야 하는데 몇번을 통해서 가능한지 알 수 없기 때문에 재귀형태로 구현해야 함최대공약수 GCDGreat Common Divisor: 가장 큰 공통된 약수1. 반복문int GCD(int a, int b) { while(b != 0) { ..

검색 알고리즘 검색과 키 검색을 할 때 특정 항목에 주목하게 되는데 이를 key라고 함 key: 데이터의 일부 배열에서 검색 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘 선택해야 함 다음의 알고리즘 활용 1. 선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색 2. 이진 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 빠른 검색 3. 해시법: 추가, 삭제가 자주 일어나는 데이터 모임에서 빠른 검색 1) 체인법: 같은 해시 값의 데이터를 선형 리스트로 연결 2) 오픈 주소법: 데이터를 위한 해시 값이 충돌할 때 재해시 배열 검색의 종료 조건 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 = 검색 실패 검색할 값과 같은 요소를 발견할 경우 = 검색 성공 배열의 요솟수가 n개일 때 조건 ..

기본 자료구조data structure데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법데이터 단위: 데이터를 구성하는 한 덩어리배열배열의 자료형 구분각 요소의 자료형 = int, a[0]은 int형자료형 = int[5], a는 int[5]형int a = new int[5]; 선언하면 배열 a는 a[0], a[1], a[2], a[3], a[4]로 총 5개의 int형 저장 공간을 차지함배열의 구성 요소는 자동으로 0으로 초기화됨그림 추가배열의 복제배열의 이름.clone();package chap02_1;import java.util.Arrays;public class CloneArray { public static void main(Str..

기본 알고리즘 문제를 해결하기 위한 것으로 명확하게 정의, 순서가 있는 유한개의 규칙으로 이루어진 집합 용어 순차적(concatenation) 구조 - 여러 문장(프로세스)이 순차적으로 실행되는 구조 선택(select) 구조 - 평가 결과에 따라 흐름을 변경하는 if문 매개변수 - 메서드를 정의할 때 실인수 - 메서드를 호출할 때 연산자(operator) - +, -, 등의 연산 기호 피연산자(operand) - 연산의 대상이 되는 것 최댓값 구하기 package chap01_1; import java.util.Scanner; public class max { public static void main(String[] args) { Scanner scan = new Scanner(System.in); S..