xxheexx

이분탐색 (Binary Search) 전체 범위를 이분할하여 가운데의 값을 비교하여 두 영역 중 다른 영역으로 이동하여 탐색 시간복잡도 : O(logN) 탐색 전 리스트가 반드시 정렬되어 있어야함 -> 배열을 적게 탐색하는 경우 이분탐색 쓰지 않는 것이 나을수도 있음 순차 탐색 vs 이분 탐색 정렬이 안되어있다면 상황에 따라 순차탐색이 더 나을 수도 있다 java public class BinarySearch { static int[] arr = {1, 3, 5, 7, 8, 10, 20, 35, 99, 100}; public static void main(String[] args) { System.out.println("1. 순환 호출을 이용한 이진 탐색"); System.out.println(binar..

map 활용 시 많이 쓰이는 함수 getOrDefault(Object key, V DefaultValue) 찾는 key가 존재하면 해당 key에 매핑되어 있는 값을 반환하고 그렇지 않으면 디폴트 값 반환 import java.util.HashMap; public class MapGetOrDefaultEx { public static void main(String arg[]) { String [] alphabet = { "A", "B", "C" ,"A"}; HashMap hm = new HashMap(); for(String key : alphabet) hm.put(key, hm.getOrDefault(key, 0) + 1); System.out.println("결과 : " + hm); // 결과 : {A..

Sorting FIFO(First In, First Out) 구조 삽입과 삭제 연산이 서로 다른 한 군데 느린 알고리즘의 경우 시간복잡도가 O(N^2), 빠른경우 O(NlogN) 안정성이 보장되는 경우인지 판단해야함 안정성 보장 : 같은 키를 가진 데이터의 순서가 안 바뀜 1. 거품정렬 (Bubble Sort) 첫번째 원소부터 인접한 원소와 비교하며 자리를 바꾸며 맨 끝부터 정렬 가장 큰 값을 하나씩 뒤로 보내면서 뒤쪽부터 정렬 안정성 보장 O 시간 복잡도 : O(N^2) -> 비효율적 void bubble_sort(int list[], int n){ int i, j, temp; for(i=n-1; i>0; i--){ // 0 ~ (i-1)까지 반복 for(j=0; j

Brute Force 단순히 가능한 모든 경우 확인 테스트 케이스의 크기에 따라 소요 시간이 엄청나게 커질 수 있음 표본의 수와 시간복잡도 고려해 선택해야함 매직넘버 100,000,000 총 연산수가 약 1억회 이하 -> 충분히 완전탐색으로 접근 가능 대략적인 완전탐색 가능 기준으로 잡으면 유용 재귀함수 이용 Backtracking 완전탐색처럼 모든 경우를 탐색하나 중간 중간에 조건에 맞지 않는 케이스를 가지치기하여 탐색 시간 줄임 일반적으로 완전탐색에 비해 시간적으로 효율적 탐색 중 조건에 맞지 않는 경우 이전 과정으로 돌아가야하기 때문에 재귀 사용하는 경우 많음 조건을 어떻게 설정하고 틀렸을 시 어떤 시점으로 돌아가야할지 설계 잘해야함 예제 import java.io.*; import java.mat..

String 사용 빈도수 높은 method 리턴 타입 메소드 이름(매개 변수) 설명 char charAt(int index) 특정 위치의 문자를 리턴합니다. boolean equals(Object anObject) 두 문자열을 비교합니다. byte[] getBytes() byte[]로 리턴합니다. byte[] getBytes(Charset charset) 주어진 문자셋으로 인코딩한 byte[]로 리턴합니다. int indexOf(String str) 문자열 내에서 주어진 문자열의 위치를 리턴합니다. int length() 총 문자의 수를 리턴합니다. String replace(CharSequence target, CharSequence replacement) target 부분을 replacement로 대..

해시 (Hash) 임의의 데이터에 대해 고정된 길이의 데이터로 매핑 이론적으로 삭제 O(1), 삽입 O(1), 검색 O(1)의 시간복잡도 해시 테이블 내부의 값이 많아지면 해시충돌 현상 -> 기본 연산의 시간 길어짐 public class HelloWorld { public static void main(String[] args) { HashMap h1 = new HashMap(); HashMap h2 = new HashMap(); h1.put("aaa", "1111"); h1.put("bbb", "2222"); h1.put("ccc", "3333"); h1.putIfAbsent("aaa", "0000"); h1.putIfAbsent("ddd", "4444"); h2.putAll(h1); System.o..

스택(Stack) FILO (First In, Last Out) 구조 삽입과 삭제 연산이 동일한 한군데 삽입/삭제 연산 시간복잡도 O(1) 제일 상단의 원소 확인이 O(1) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 이전에 활용한 데이터를 역으로 추적하거나 처음 들어온 데이터보다 나중에 들어온 데이터가 빨리 나가야 할 때 사용 stack s; s.push(10); s.push(20); s.top();//20 s.pop(); //20 큐 (Queue) FIFO (Fisrt In, First Out) 구조 삽입과 삭제 연산이 서로 다른 한군데에서 발생 삽입/삭제 연산에 있어 시간복잡도 O(1) 제일 앞/뒤의 원소확인이 O(1) 맨 앞을 front, 맨 뒤를 rear 삽입연산을 enque..