데일리썽

문제 제목 : 블랙잭

난이도 : 하

문제 유형 : 배열, 완전 탐색

추천 풀이 시간 : 20분 (못하면 2배 40분)

https://www.acmicpc.net/problem/2798

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                for (int k = j + 1; k < arr.length; k++) {
                    int sum = arr[i] + arr[j] + arr[k];
                    if (sum <= m) {
                        result = Math.max(result, sum);
                    }
                }
            }
        }
        
        System.out.println(result);
    }
}

문제 제목 : 음계

난이도 : 하

문제 유형 : 배열, 구현

추천 풀이 시간 : 15분 (못하면 2배 30분)

https://www.acmicpc.net/problem/2920

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[8];
        Scanner sc = new Scanner(System.in);
        
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        
        Boolean asc = true;
        Boolean desc = true;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] < arr[i + 1]) {
                desc = false;
            } else if (arr[i] > arr[i + 1]) {
                asc = false;
            }
        }
        
        if (asc) {
            System.out.println("ascending");
        } else if (desc) {
            System.out.println("descending");
        } else {
            System.out.println("mixed");
        }
    }
}

1. 선택 정렬 (selection sort)

아래 순서를 반복하며 정렬하는 알고리즘

• 주어진 데이터 중 최소값을 찾음
• 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
• 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

import java.util.*;

public class SelectionSort {
    public static void selectionSort() {
        int[] arr = new int[5];
        int size = arr.length;

        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < 5; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println("정렬 전 : " + arr);

        for (int i = 0; i < size - 1; i++) {
       	    int minIndex = i;
       	    for (int j = i + 1; j < size; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }

        System.out.println("정렬 후 : " + arr);
    }
}

2. 알고리즘 분석

반복문이 두개 : O(n^2)

1. 삽입 정렬 (insertion sort)

삽입 정렬은 두 번쨰 인덱스부터 시작

해당 인덱스(key 값) 앞에 있는 데이터부터 비교해서 key 값이 더 작으면 데이터 값을 뒤 인덱스로 복사

이용 Key 값이 더 큰 데이터를 만날떄까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

• [5, 3]
  -> [3, 5]
• [5, 3, 2]
  -> [3, 5, 2]
  -> [3, 2, 5] -> [2, 3, 5]
• [5, 3, 2, 4]
  -> [3, 5, 2, 4]
  -> [3, 2, 5, 4] -> [2, 3, 5, 4]
  -> [2, 3, 4, 5] -> [2, 3, 4, 5]

import java.util.*;

public class InsertionSort {
    public static void insertionSort() {
    	int[] arr = new int[5];
        int size = arr.length;

        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < 5; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println("정렬 전 : " + arr);

        for (int i = 0; i < size - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }
            }
        }

        System.out.println("정렬 후 : " + arr);
	}
}

2. 알고리즘 분석

반복문이 두개 : O(n^2)

완전 정렬이 되어 있는 경우 : O(n)

1. 정렬 (sorting) 이란?

정렬 (sorting) : 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것

정렬은 프로그램 작성시 빈번하게 필요로 함

2. 버블 정렬 (bubble sort)

두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘

• [5, 2] -> [2, 5]
• [5, 4, 2] -> [4, 5, 2] -> [4, 2, 5]
  -> [2, 4, 5]
• [5, 2, 3, 1] -> [2, 5, 3, 1] -> [2, 3, 5, 1] -> [2, 3, 1, 5]
  -> [2, 3, 1, 5] -> [2, 1, 3, 5]
  -> [1, 2, 3, 5]

import java.util.*;

public class BubbleSort {
    public static void bubbleSort() {
        int[] arr = new int[5];
        int size = arr.length;

        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < 5; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println("정렬 전 : " + arr);

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        System.out.println("정렬 후 : " + arr);
    }
}

3. 알고리즘 분석

반복문이 두개 : O(n^2)

완전 정렬이 되어 있는 경우 : O(n)

1. 힙 (Heap)

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree)
  • 완전 이진 트리 : 노드를 삽일할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

힙 사용 이유

• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
• 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)
• 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용

2. 힙 (Heap) 구조

• 힙은 최대값을 구하기 위한 구조 (최대힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소힙, Min Heap) 로 분류
• 힙은 다음과 같은 조건을 가지고 있는 자료구조임
  • 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대힙의 경우)
  • 최소힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같다.
  • 완전 이진 트리 형태를 가짐

3. 힙과 이진 탐색 트리의 공통점과 차이점

공통점

• 이진 트리임

차이점

• 힙은 각 노드의 값이 자식 노드보다 크거나 같음 (최대힙의 경우)
• 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고 그 다음 부모 노드 그 다음 오른쪽 자식 노드 값이 가장 큼
• 힙은 이진 탐색 트리의 조건이 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
• 힙의 왼쪽 밑 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음

이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해

4. 힙 (Heap) 구현

• 배열 이용해서 데이터를 힙 구조에 삽입, 삭제
• root 노드 인덱스 번호를 1로 지정하면 수월함
  • 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 / 2
  • 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
  • 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1

public class Heap {
    private ArrayList<Integer> heap;
    
    public init() {
    	heap = new ArrayList<Integer>();
        heap.add(0); // 0번째 인덱스 사용 안함
    }
    
    public Boolean moveUp(Integer index) {
    	if (index <= 1) {
            return false;
        }
        Integer parentIndex = index / 2;
        if (heap.get(index) > heap.get(parentIndex)) {
            return true;
        } else {
            return false;
        }
    }
    
    public Boolean insert(Integer data) {
    	if (heap.size() == 0) {
            init();
            return true;
        }
        
        heap.add(data);
        
        Integer index = heap.size() - 1;
        while (this.moveUp(index)) {
            Integer parentIndex = index / 2;
            Integer parentData = heap.get(parentIndex); // 부모 노드의 값
            heap.set(parentIndex, data);
            heap.set(index, parentData);
            index = parentIndex;
        }
        return true;
    }
    
    public Boolean moveDown(Integer index) {
    	Integer leftChildIndex = index * 2;
        Integer rightChildIndex = index * 2 + 1;
        
        if (leftChildIndex >= heap.size()) { // 1. 왼쪽 자식 노드도 없을 때
            return false;
        } else if (rightChildIndex >= heap.size()) {  // 2. 오른쪽 자식 노드만 없을 때
            if (heap.get(index) < heap.get(leftChildIndex)) {
            	return true;
            } else {
            	return false;
            }
        } else { // 3. 왼쪽, 오른쪽 자식 노드 모두 있을 때
            if (heap.get(leftChildIndex) > heap.get(rightChildIndex)) {
                if (heap.get(index) < heap.get(leftChildIndex)) {
                    return true;
                } else {
                    return false;
                }
            } else {
            	if (heap.get(index) < heap.get(rightChildIndex)) {
                    return true;
                } else {
                    return false;
                }
            }
        }
    }
    
    public Integer pop() {
    	if (heap.size() <= 1) {
        	return null;
        }
        
        Integer popData = heap.get(1);
        heap.set(1, heap.get(heap.size() - 1);
        heap.remove(heap.size() - 1);
        
        Integer index = 1;
        
        while (this.moveDown(index)) {
            Integer leftChildIndex = index * 2;
            Integer rightChildIndex = index * 2 + 1;
            
            if (rightChildIndex >= heap.size()) { // 2. 오른쪽 자식 노드만 없을 때
            	if (heap.get(index) < heap.get(leftChildIndex)) {
                    Integer leftChildData = heap.get(leftChildIndex);
                    heap.set(leftChildIndex, heap.get(index));
                    heap.set(index, leftChildData);
                }
            } else { // 3. 왼쪽, 오른쪽 자식 노드 모두 있을 때
            	if (heap.get(leftChildIndex) > heap.get(rightChildIndex)) {
                    if (heap.get(index) < heap.get(leftChildIndex)) {
                        Integer leftChildData = heap.get(leftChildIndex);
                        heap.set(leftChildIndex, heap.get(index));
                        heap.set(index, leftChildData);
                    }
            	} else {
                    if (heap.get(index) < heap.get(rightChildIndex)) {
                        Integer rightChildData = heap.get(rightChildIndex);
                        heap.set(rightChildIndex, heap.get(index));
                        heap.set(index, rightChildData);
                    }
                }
            }
        }
        return popData;
    }
    
	public 
}

5. 힙 (Heap) 시간 복잡도

• O(logn)

1. 트리 (Tree) 구조

트리 : Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조

실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨

2. 알아둘 용어

• Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
• Root Node : 트리 맨 위에 있는 노드
• Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 길이를 나타냄
• Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
• Child Node : 어떤 노드의 상위 레벨에 연결된 노드 
• Leaf Node (Terminal Node) : Child Node가 하나도 없는 노드
• Sibling (Brother Node) : 동일한 Parent Node를 가진 노드
• Depth : 트리에서 Node가 가질 수 있는 최대 Level

3. 이진 트리와 이진 탐색 트리 (Binary Search Tree)

• 이진 트리 : 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리 (Binary Search Tree, BST) : 이진 트리에서 다음과 같은 추가적인 조건이 있는 트리
  • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음!

4. 자료 구조 이진 탐색 트리의 장점과 주요 용도

주요 용도 : 데이터 검색 (탐색)

장점 : 탐색 속도를 개선할 수 있음

단점 : 

이진트리와 정렬된 배열간의 탐색 비교

5. 링크드 리스트 구현하기

public class Node {
    private Integer value;
    public Node left;
    public Node right;
    
    public Node(Integer value) {
    	this.value = value;
        this.left = null;
        this.right = null;
    }
    
    public Node(Integer value, Node right) {
    	this.value = value;
        this.right = right;
    }
    
     public Integer getValue() {
        return this.data;
    }
}

public class NodeMgmt() {
	private Node head; //root Node
    
    public void init(Integer value) {
    	head = new Node(value);
    }
    
    public void insert(Integer value) {
        Node node = head;
        while(true) {
            if (value < node.getValue()) {
                if (node.left != null) {
                    node = node.left;
                } else {
                    node.left = new Node(value);
                    break;
                }
            } else {
            	if (node.right != null) {
                	node = node.right;
                } else {
                	node.right = new Node(value);
                    break;
                }
            }
        }
    }
    
    public Boolean search(Integer value) {
    	Node node = head;
        while (node) {
            if (node.getValue() == value) {
            	return true;
            } else if (value < node.getValue()) {
            	node = node.left;
            } else {
            	node = node.right;
            }
        }
        return false;
    }
    
    public Boolean delete(Integer value) {
    	Boolean searched = false;
    	Node node = head;
        Node parent = head;
        while (node) {
        	if (node.getValue() == value) {
            	searched = true;
                break;
            } else if (value < node.getValue()) {
            	parent = node;
            	node = node.left;
            } else {
            	parent = node;
                node = node.right;
            }
        }
        
        if (searched == false) {
        	return false;
        }
        
        // 1. 삭제할 Node가 Leaf Node인 경우
        if (node.left == null && node.right == null) {
        	if (value < parent.getValue()) {
            	parent.left = null;
            } else {
            	parent.right = null;
            }
        }
        
        // 2. 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
        if (node.left != null && node.right == null) {
        	if (value < parent.getValue()) {
            	parent.left = node.left;
            } else {
            	parent.right = node.left;
            }
        } else if (node.left == null && node.right != null) {
        	if (value < parent.getValue()) {
            	parent.left = node.right;
            } else {
            	parent.right = node.right;
            }
        }
        
        // 3. 삭제할 Node가 Child Node를 두 개 가지고 있을 경우
        if (node.left != null && node.right != null) {
        	if (value < parent.getValue()) {
            	Node changeNode = node.right;
                Node changeNodeParent = node.right;
                while (changeNode.left != null) {
                	changeNodeParent = changeNode;
                	changeNode = changeNode.left;
                }
                if (changeNode.right != null) {
                	changeNodeParent.left = changeNode.right;
                } else {
                	changeNodeParent.left = null;
                }
                parent.left = changeNode;
                changeNode.left = node.left;
                changeNode.right = node.right;
            } else {
            	Node changeNode = node.right;
                Node changeNodeParent = node.right;
                while (changeNode.left != null) {
                	changeNodeParent = changeNode;
                    changeNode = changeNode.left;
                }
                if (changeNode.right != null) {
                	changeNodeParent.left = changeNode.right;
                } else {
                	changeNodeParent.left = null;
                }
                parent.right = changeNode;
                changeNode.left = node.left;
                changeNode.right = node.right;
            }
        }
    	return true;
    }
    
    

}

6. 이진 탐색 트리의 시간 복잡도와 단점

6-1 시간 복잡도 (탐색시)

• depth (트리의 높이) 를 h라고 표기한다면, O(h)
• n개의 노드를 가진다면, h = log2n에 가까우므로, 시간 복잡도는 O(logn)
  • 빅오 표기법에서 logn에서의 log의 밑은 10이 아니라 2
  • 한번 실행시마다 50%의 실행할 수도 있는 명령을 제거한다는 의미, 즉 50%의 실행시간을 단축시킬 수 있음을 의미

6-2 이진 탐색 트리 단점

• 평균 시간 복잡도는 O(logn) 이지만 최악의 경우는 링크드 리스트 등과 동일한 성능을 보임 O(n)

대표적인 데이터 구조6 : 해쉬 테이블 (Hash Table)

1. 해쉬 구조

Hash Table : Key에 Value를 저장하는 데이터 구조

Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐

배열로 미리 해쉬 테이블 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)

2. 알아둘 용어

• 해쉬(Hash) : 임의 값을 고정 길이로 변환하는 것
• 해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수(Hashing Function) : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address) : Key를 해싱 함수로 연산해서 해쉬 값을 알아내고 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성 있게 찾을 수 있음
• 슬록(Slot) : 한 개의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음 

3. 해쉬 테이블의 장단점과 주요 용도

장점

• 데이터 저장/읽기 속도가 빠름 (검색 속도가 빠름)
• 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움

단점

• 일반적으로 저장공간이 좀더 많이 필요함
• 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함

용도

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번한 경우
• 캐쉬 구현시 (중복 확인이 쉽기 때문)

4. 예시

import java.util.HashMap;

public class HashMapEx {
	public static void main(String[] args) {
            HashMap<String, String> map = new HashMap<>();
            map.put("A", "apple");
            map.put("B", "banana");
            map.put("C", "carrot");

            System.out.println(map.get("A"));
            System.out.println(map.get("B"));
            System.out.println(map.get("C"));
	}
}

5. 충돌(Collision) 해결 알고리즘 (좋은 해쉬 함수 사용하기)

해쉬 테이블의 가장 큰 문제는 충돌의 경우이다. 이 문제를 충돌 또는 해쉬 충돌이라고 부른다.

- Chaining 기법

개방 해슁 또는 Open Hashing : 해쉬 테이블 저장공간 외의 공간을 활용하는 기법

충돌이 일어나면 링크드 리스트라는 자료 구조를 사용해서 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

- Linear Probing 기법

폐쇄 해슁 또는 Close Hashing : 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법

충돌이 일어나면 해당 해쉬 어드레스의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법

저장공간 활용도를 높이기 위한 기법

6. 빈번한 충돌을 개선하는 기법

해쉬 함수를 재정의  및 해쉬 테이블 저장공간을 확대

7. 유명한 해쉬 함수들

SHA(Secure Hash Algorithm, 안정한 해시 알고리즘) : 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능

SHA-1

SHA-256

8. 시간 복잡도

일반적인 경우(Collision 없는 경우)는 O(1)

최악의 경우(Collision이 모두 발생하는 경우) O(n)

해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 O(1) 이라고 말할 수 있음

검색에서 해쉬 테이블의 사용 예

16개의 배열에 데이터를 저장하고 검색할 때 O(n)

16개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고 검색할 때 O(1)