[알고리즘] 코딩 테스트 합격자 되기 - 해시, 트리

코딩 테스트 합격자 되기 자바편

책 제목 : 코딩 테스트 합격자 되기 자바편

지은이 : 김희성

 

해시

개념 : 데이터를 찾기위해서 처음부터 순차적으로 탐색하지 않고 해시함수를 사용하여 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료 구조이다.

 

해시 특징

해시는 단방향으로 동작하며 키를 통해서 값을 찾을 수 있지만 값을 통해서 키를 찾을 수 없다.

해시테이블 : 해시의 키와 대응한 값이 저장되있는 공간

버킷 : 해시 테이블의 각 데이터

 

해시 예제 문제

문제 설명 : 구매를 원하는 항목(wantList)과 그 항목에 해당되는 numbers가 있는데 마트에 할인 항목 리스트 14개중 차례대로 10개씩 1일 한번 할인 행사를 한다. 따라서 구매항목과 할인 항목이 일치하는 횟수를 체크하는 문제다.

구매항목의 총합은 10개이며 할인항목은 1일이 지나면 앞 배열부터 인덱스가 1씩 증가한다.

 

예제 문제

import java.io.IOException;
import java.util.ArrayDeque;
import java.util.HashMap;

public class Main {
    public static void main(String[] args){

        // 원하는 항목
        String[] wantList = {"banana", "apple", "rice", "pork", "pot"};

        // 각 항목별 요구하는 수
        int[] numbers = {3, 2, 2, 2, 1};

        // 할인 항목 리스트
        String[] discountList = {"chicken", "apple", "apple", "banana", "rice", "apple", "pork", "banana", "pork", "rice", "pot", "banana", "apple", "banana"};

        // 원하는 항목 맵형태 저장용 자료 구조 생성
        HashMap<String, Integer> wantsMap = new HashMap<>();

        // 일치 하는 횟수가 정답
        int answer = 0;

        // 맵 형태로 변환 저장
        for (int i = 0; i < wantList.length; i++) {
            wantsMap.put(wantList[i], numbers[i]);
        }

	// 할인 목록 14개중 0번 인덱스부터 10개씩 할인 행사를 진행한다. ( 총 4번 진행한다고 보면 된다 )
        for (int i = 0; i < discountList.length - 9; i++) {
            HashMap<String, Integer> discount10dMap = new HashMap<>();
            
		// 10개 항목을 맵에 담는다.
            for (int j = i; j < 10 + i; j++) {
                discount10dMap.put(discountList[j], discount10dMap.getOrDefault(discountList[j], 0) + 1);
            }

		// 원하는 항목과 같은 맵 형태인지 비교한다.
            if (wantsMap.equals(discount10dMap)) {
                answer++;
            }
        }

        System.out.println(answer);
    }
}

 

트리

개념 :  트리는 데이터를 저장하고 탐색하기에 유용한 구조를 갖고 인데 뿌리인 root를 거꾸로 뒤집어서 상단에 놓고 하위에 노드에 데이터를 쭉 저장하는 형태이다. 루트는 0레벨이면 바로 밑에 자식 노드는 1레벨 그 자식의 자식 노드는 2레벨...형태로 구조가 형성 되어있다.

같은 레벨의 노드는 형제라고 한다. 부모, 자식, 형제 그리고 자식이 없는 노드를 리프(leaf) 노드라고 한다.

주로 코딩테스트에 사용되는 트리는 이진트리(binary tree)이다. 차수가 2를 넘지않는 트리를 말한다. 차수는 간선이 최대 2개뿐인 트리다.

간선은 노드와 노드간에 연결을 해주는 선을 말한다. 다시 말해 이진트리란 노드에 연결된 노드는 최대 2개라는 의미이다.

 

트리 표현 방법

 

1. 배열(선형구조)로 트리(계층구조) 표현하기

루트 인덱스를 1로 설정시 부모노드의 좌측은 부모노드 인덱스 * 2로 표현하고 우측은 부모노드 인덱스 * 2 + 1 로 표현하여 배열에 저장한다.

루트 인덱스를 0으로 설정 시 부모노드의 좌측은 부모노드 인덱스 * 2 + 1로 표현하고 우측은 부모노드 인덱스 * 2 + 2 로 표현하여 배열에 저장한다.

 

2. 이진트리 3가지 순회 방법으로 표현

전위 순회 : 현재 노드를 부모 노드를 생가했을 때 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 방문한다.

중위 순회 : 현재 노드를 부모 노드로 생각했을때 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서로 방문한다.

후위 순회 : 현재노드를 부모 노드로 생각했을때 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드 순서로 방문한다.

 

3. 포인터로 표현하기 

노드를 만들고 포인터를 통해서 관리하기 때문에 배열처럼 빈 인덱스에 메모리 공간 낭비를 하지 않는다.

 

4. 인접 리스트로 표현하기

정점의 번호(수)만큼 리스트를 만들고 리스트는 해당 정점에서 연결된 노드의 번호가 된다.

1~10번 노드가 있으면 각 노드별로 자식 노드를 부모 노드의 인덱스에 자식 리스트로 저장한다.

 

5. 이진 탐색 트리

데이터 크기를 따져서 크기나 작으면 왼쪽 크기가 같거나 크면 우측으로 배치하여 정렬하는 방법

탐색시 찾으려는 값이 같으면 종료하고 작으면 좌측 크면 우측으로 이동하여 노드를 탐색한다.

 

 

예제 문제

import java.util.*;

public class Main {

    static HashMap<Integer, HashMap<String,Integer>> courseMap = new HashMap<>();

    public static void main(String[] args) {
        System.out.println(solution(new int[]{1, 2, 3, 4, 5, 6, 7})[0]);
        System.out.println(solution(new int[]{1, 2, 3, 4, 5, 6, 7})[1]);
        System.out.println(solution(new int[]{1, 2, 3, 4, 5, 6, 7})[2]);
    }


    static String[] solution(int[] nodes) {
        String[] result = new String[3];
		
        // 이진트리 전위
        result[0] = preOrder(nodes, 0);
        // 중위
        result[1] = inOrder(nodes, 0);
        // 후위
        result[2] = postOrder(nodes, 0);

        return result;
    }

	// 재귀 호출시 코드는 간단한데 처음보면 눈에 익지않아서 이해가 잘 가지 않는다.
    // 1번째로 인덱스 값이 배열의 범위를 벗어나는지 체크를한다.
    // 벗어나면 이진트리의 마지막 계층을 지났다는 의미로 간주되며 해당 재귀 호출의 끝을 의미한다.
    // 전위 연산을 예로 들면 [1,2,3,4,5,6,7]이라는 배열 값을 기준으로 예를 든다.
    // preOrder메서드 진입시 재귀호출을 멈춰줄 idx >= node.length는 잠시 무시하고
    // node[idx]의 부분을 먼저 찍는다.
    // 1. node[0]값은 1이며 그 다음 다시 자신을 호출하는 idx * 2 + 1 인덱스를 인자로 넘긴다.
    // 2. 다시한번 1번째 조건은 무시하고 node[0 * 2 + 1]의 값인 2가 출력된다.
    // 3. 현재까지 "1 2"가 출력 되었다.
    // 4. 다시 preOrder함수를 1 * 2 + 1 인자로 넘기며 호출한다.
    // 5. node[1 * 2 + 1]의 값을 출력하고 다시 3 * 2 + 1 인자를 넘기고 자신을 호출한다. "1 2 4"
    // 6. 1번째 조건인 인덱스 범위를 벗어나서 멈춘다.
    // 7. 5번으로 돌아가서 마지막 preOrder함수에 1 * 2 + 2 인자를 넘기고 호출한다. "1 2 4 5"
    // 같은 방식으로 계속 탐색을 진행하면서 최종 출력을 하면 "1 2 4 5 3 6 7"이 된다.
    
    static String preOrder(int[] nodes, int idx) {
        if (idx >= nodes.length) {
            return "";
        }

        return nodes[idx] + " " + preOrder(nodes, idx * 2 + 1) + preOrder(nodes, idx * 2 + 2);
    }

	// 중위
    static String inOrder(int[] nodes, int idx) {
        if (idx >= nodes.length) {
            return "";
        }

        return inOrder(nodes, idx * 2 + 1) + nodes[idx] + " " + inOrder(nodes, idx * 2 + 2);
    }
	
    // 후위
    static String postOrder(int[] nodes, int idx) {
        if (idx >= nodes.length) {
            return "";
        }

        return postOrder(nodes, idx * 2 + 1) + postOrder(nodes, idx * 2 + 2) + nodes[idx] + " ";
    }
}

 

 

아래는 어떤방식으로 호출되는지 순서에 따라서 그림을 그린 부분이다.

 

이진트리 전위

 

이진트리 전위

이런 방식으로 쭉 재귀호출을 통해서 진행하게된다.