[묘공단] 3주 차 코딩 테스트 합격자 되기: 자바 (책 요약)

🎫 3주 차 학습 내용

07-1. 큐의 개념

큐의 사전적 의미는 '줄을 서다'라는 의미를 가지고 있습니다. 큐는 먼저 들어간 데이터가 먼저 나오는 자료구조입니다. 일명 선입선출, FIFO (First In First Out)이라고 합니다. 그리고 큐에서는 삽입하는 연산을 Enqueue(Add), 꺼내는 연산을 Dequeue(Poll)이라고 합니다. 

큐 설명 그림

- 큐의 특성을 활용하는 분야

대표적으로 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐가 활용됩니다.

• 작업 대기열 : 네트워크 통신을 할 때 다수의 클라이언트에서 서버에 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리합니다.
• 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어 키보드 입력이나 마우스 움직임을 처리할 때 큐를 활용할 수 있습니다.

 

- 큐 구현하기

큐를 간단하게 구현하는 방식은 크게 2가지 방식이 있습니다.

첫 번째는 Queue 인터페이스를 활용하는 방식

두 번째는 ArrayDeque 클래스를 활용하는 방식

 

Queue 인터페이스 사용하기

import java.util.Queue; //import

// 큐를 구현한 ArrayDeque 객체 생성
Queue<Integer> queue = new ArrayDeque<>();

// 큐에 데이터 추가
queue.add(1);
queue.add(2);
queue.add(3);

// 큐의 맨 앞 데이터를 제거하면서 반환
int first = queue.poll();
System.out.println(first);	// 1

// 큐에 데이터 추가
queue.add(5);

// 큐의 맨 앞 데이터를 제거하면서 반환
first = queue.poll();
System.out.println(first);	// 2

 

덱을 큐처럼 활용하기

ArrayDeque<Integer> queue = new ArrayDeque<>();

// 큐에 데이터 추가
queue.addLast(1);
queue.addLast(2);

// 큐의 맨 앞 데이터를 제거하면서 반환
int first = queue.pollFirst();
System.out.println(first);	// 1

// 큐에 데이터 추가
queue.addLast(4);

// 큐의 맨 앞 데이터를 제거하면서 반환
first = queue.pollFirst();
System.out.println(first);	// 2

 

07-3. 합격자가 되는 모의 테스트

👓 문제 16. 기능 개발

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        
        int[] day = new int[progresses.length];
        List<Integer> list = new ArrayList<>();
        
        for (int i = 0; i < progresses.length; i++) {
            day[i] = (100 - progresses[i]) / speeds[i];
            if ((100 - progresses[i]) % speeds[i] != 0) {
                day[i] += 1;
            }
        }
        
        int prev = day[0];
        int count = 1;
        for (int i = 1; i < day.length; i++) {
            if (prev < day[i]) {
                list.add(count);
                count = 1;
                prev = day[i];
            } else {
                count++;
            }
        }
        list.add(count);
        
        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        
        return answer;
    }
}

 

👓 문제 17. 카드 뭉치

import java.util.*;

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        int p1 = 0;
        int p2 = 0;
        
        // goal 배열의 값 하나씩 가져옴
        for (String curStr : goal) {
            // curStr이 cards1[p1] 또는 cards2[p2]에 포함하는지 확인
            if (p1 < cards1.length && curStr.equals(cards1[p1])) {
                p1 += 1; // cards1[p1]에 포함하는 경우 p1 +1 으로 값 증가시키기
            } else if (p2 < cards2.length && curStr.equals(cards2[p2])) {
                p2 += 1; // cards2[p2]에 포함하는 경우 p2 +1 으로 값 증가시키기
            } else {
                return "No"; // 둘 다 포함하지 않는 경우
            }
        }
        
        return "Yes";
    }
}

 

08-1. 해시의 개념

해시는 해시 함수를 사용해서 변환 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조입니다. 어떻게 탐색을 빠르게 만드냐면, 해시는 키(key)를 활용해 데이터 탐색을 빠르게 합니다.

ArrayList와 LinkedList의 한계를 극복하기 위해서 제시된 방법이라고 볼 수 있습니다.

 

해시 자세히 알아보기

해시 설명 그림

 

위 그림을 보면 내가 최종적으로 얻고자 하는 정보, 즉, 전화번호(521-8976)는 값이고, 값을 검색하기 위해 활용하는 정보는 키(key)입니다. 그리고 그 사이에 키를 이용해 해시값 또는 인덱스로 변환하는 해시 함수가 있습니다. 해시 함수는 이렇게 키를 일정한 해시값으로 변환시켜 값을 찾을 수 있게 해 줍니다.

 

- 해시의 특징

첫 번째, 해시는 단방향으로 동작합니다.

두 번째, 찾고자 하는 값을 O(1)으로 바로 찾을 수 있습니다. 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없습니다.

세 번째, 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 합니다.

 

해시의 특성을 활용하는 분야

해시의 특성으로 데이터를 저장하고 검색하거나, 보안이 필요한 때에 활용됩니다. 코딩 테스트에서는 특정 데이터를 탐색하는 횟수가 많을 경우 해시를 고려하면 좋습니다. 다음은 해시 활용 실제 사례입니다.

• 비밀번호 관리
• 데이터베이스 인덱싱
• 블록체인

 

08-2. 해시 함수

해시 함수를 구현할 때 고려할 내용

첫 번째, 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안 됩니다.

두 번째, 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 합니다.

* 충돌의 의미는 서로 다를 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미합니다.

 

자주 사용하는 해시 함수 알아보기

나눗셈법

나눗셈법은 가장 떠올리기 쉬운 단순한 해시 함수입니다. 나눗셈법은 키를 소수로 나눈 나머지를 활용합니다.

이처럼 나머지를 취하는 연산을 모듈러 연산이라고 하며 연산자는 %로 표시합니다.
예를 들어, 7 % 2 = 1입니다. 나눗셈법을 수식으로 작성하면 다음과 같습니다.

나눗셈법 수식

곱셈법

나눗셈법은 때에 따라 큰 소수를 사용해야 하는데 큰 소수를 구하기가 쉽지 않다는 단점이 있었습니다.

곱셈법은 나눗셈법과 비슷하게 모듈러 연산을 활용하지만 소수는 활용하지 않습니다.

곱셈법의 공식은 다음과 같습니다.

곱셈법 수식

문자열 해싱

지금까지 알아본 해시 함수는 키의 자료형이 숫자였습니다. 이번에는 키의 자료형이 문자열일 때도 사용할 수 있는 해시 함수인 문자열 해싱입니다. 문자열 해싱은 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱합니다.

08-3. 충돌 처리

체이닝으로 처리하기

체이닝은 해시 테이블에 데이터를 저장할 때 해싱한 값이 같은 경우 충돌을 해결하는 간단한 방법입니다.

체이닝은 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결합니다.

• 장점 : 체이닝은 충돌을 링크드리스트로 간단히 해결한다는 장점이 있습니다.
• 단점 :
  • 해시 테이블 공간 활용성이 떨어집니다.
  • 검색 성능이 떨어집니다.

 

개방 주소법으로 처리하기

개방 주소법은 체이닝에서 링크드리스트로 충돌값을 연결한 것과 다르게 빈 버킷을 찾아 충돌값을 삽입합니다.

이 방법은 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용합니다.

 

선형 탐사 방식

선형 탐사 방식은 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동합니다. 해시 함수로 나온 해시 값(index)에 이미 다른 값이 저장되어 있다면, 해당 해시값에서 고정된 폭만큼 옮겨 다음 빈칸을 찾아가는 방법입니다.

선형 탐사 방식 설명 그림

이중 해싱 방식

이중 해싱 방식은 말 그대로 해시 함수를 2개 사용합니다. 때에 따라 해시 함수를 N개로 늘리기도 합니다.

두 번째 해시 함수의 역할은 첫 번째 해시 함수로 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할을 합니다.

 

08-5. 합격자가 되는 모의 테스트

👓 문제 19. 완주하지 못한 선수

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String noneMatchPlayer = "";
        
        // 단어 순으로 배열을 정렬부터 한다.
        Arrays.sort(participant);
        Arrays.sort(completion);

        for (int i = 0; i < completion.length; i++) {
            // 앞에서부터 하나씩 비교를 해서 동일하면 넘어간다.
            if (participant[i].equals(completion[i])) {
                continue;
            // 동일하지 않으면 완주 못한 선수이므로 return한다.
            } else {
                return participant[i];
            }
        }
        
        // 위에 for문을 다 continue하면 마지막 남은 한 사람이 완주 못한 선수이다.
        return participant[participant.length-1];
    }
}

 

 

 

 

출처

https://goldenrabbit.co.kr/product/javapass/

[되기] 코딩 테스트 합격자 되기(자바 편) - 골든래빗

 

큐의 개념

https://coding-factory.tistory.com/602

 

해시의 개념

https://jroomstudio.tistory.com/10

https://dkswnkk.tistory.com/679

https://go-coding.tistory.com/30

 

해시 함수 공식

https://velog.io/@hyoeunla/HashHash-function