삼성 SDS 대학생 알고리즘 특강 3일차 - 자료구조

이진 트리의 표현

 

연속 구조- 일차원 배열을 이용한 구현

 

부모: i/2

왼쪽 자식: i*2

오른쪽 자식: i*2 +1

 

 

힙

힙 조건 예시: 각 노드의 키 값은 자식 노드의 키 값보다 더 크다.

일차원 배열로 구현.

일반적으로 그룹을 정렬(Heap Sort) 하거나 최소/최대 값을 찾을 때 사용.

최소 힙: 부모노드의 키 값이 자식노드의 키 값보다 항상 작다.

최대 힙: 부모노드의 키 값이 자식노드의 키 값보다 항상 크다.

 

힙의 삽입 연산

1. 트리의 가장 마지막 위치에 노드 삽입
2. 추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인
3. 만족하지 않는다면 부모와 자식의 키 값을 바꾼다.
4. 조건에 만족하거나 추가된 노드가 루트에 도달할 때까지 2 ~ 3 반복

 

완전 이진 트리의 리프 노드부터 루트 노드까지 연산을 함.

노드가 N개 일 때 수행 시간 O(log N)

 

 

힙의 삭제 연산

1. 힙의 삭제연산은 항상 루트 노드를 삭제.
2. 트리의 가장 마지막 노드를 루트 자리로 삽입.
3. 바꾼 위치의 노드가 힙 조건을 만족하는지 확인.
4. 만족하지 않는다면 왼쪽 자식과 오른쪽 자식 중 적합한 노드의 키 값을 바꾼다
5. 조건을 만족하거나 리프 노드에 도달할 때까지 3~4를 반복한다.

 

완전 이진 트리의 루트 노드부터 리프 노드까지 연산을 함.

노드가 N개 일 때 수행 시간 O(log N)

 

 

 

1927: 최소 힙

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        MinHeap mh = new MinHeap();

        for(int i=0; i<N; i++){
            int input = Integer.parseInt(br.readLine());
            if(input == 0){
                System.out.println(mh.delete());
            } else {
                mh.insert(input);
            }
        }
    }
}

class MinHeap {
    List<Integer> list;

    public MinHeap() {
        list = new ArrayList<>();
        list.add(0);
    }

    public void insert(int val) {
        //1. leaf 마지막에 삽입
        list.add(val);
        //2. 부모와 비교 후 조건에 맞지 않으면 Swap
        //3. 조건이 만족되거나 root까지 반복
        int current = list.size() - 1;
        int parent = current / 2;
        while (true) {
            if (parent == 0 || list.get(parent) <= list.get(current)) {
                break;
            }

            int temp = list.get(parent);
            list.set(parent, list.get(current));
            list.set(current, temp);

            current = parent;
            parent = current / 2;
        }
    }

    public int delete() {
        //리스트에 0번째 인덱스 값만 있는 경우
        if (list.size() == 1) {
            return 0;
        }
        //1. Root에 leaf 마지막 데이터 가져옴
        int top = list.get(1);
        list.set(1, list.get(list.size() - 1));
        list.remove(list.size() - 1);

        //2. 자식과 비교 후 조건이 맞지 않으면 swap
        //3. 조건이 만족되거나 leaf까지 반복
        int currentPos = 1;
        while (true) {
            int leftPos = currentPos * 2;
            int rightPos = currentPos * 2 + 1;
            //왼쪽 자식 먼저 확인
            if (leftPos >= list.size()) {
                break;
            }

            int minValue = list.get(leftPos);
            int minPos = leftPos;

            //오른쪽 자식 확인
            if (rightPos < list.size() && minValue > list.get(rightPos)) {
                minValue = list.get(rightPos);
                minPos = rightPos;
            }

            //Swap
            if (list.get(currentPos) > minValue) {
                int temp = list.get(currentPos);
                list.set(currentPos, minValue);
                list.set(minPos, temp);
                currentPos = minPos;
            } else {
                break;
            }
        }
        return top;
    }
}

 

 

1202: 보석 도둑

우선순위 큐

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int K;
    static Bosuk[] jewelry;
    static int[] bag;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());


         N = Integer.parseInt(st.nextToken());
         K = Integer.parseInt(st.nextToken());
         jewelry = new Bosuk[N];
         bag = new int[K];
         for(int i=0; i<N; i++){
             st = new StringTokenizer(br.readLine());
             int M = Integer.parseInt(st.nextToken());
             int V = Integer.parseInt(st.nextToken());

             jewelry[i] = new Bosuk(M,V);
         }

        for(int i=0; i<K; i++){
            st = new StringTokenizer(br.readLine());
            int C = Integer.parseInt(st.nextToken());
            bag[i] = C;
        }

        //가방 오름차순 정렬
        Arrays.sort(bag);

        //보석무게 오름차순 정렬
        Arrays.sort(jewelry, new Comparator<Bosuk>() {
            @Override
            public int compare(Bosuk o1, Bosuk o2) {
                return o1.weight - o2.weight;
            }
        });

        //보석 가격이 높은 값 기준 힙
        PriorityQueue<Bosuk> pq = new PriorityQueue<>(new Comparator<Bosuk>() {
            @Override
            public int compare(Bosuk o1, Bosuk o2) {
                return o2.price - o1.price;
            }
        });

        int jIndex = 0;
        long result = 0;
        //1.남은 가방 중 제일 작은 가방을 선택. <- 정렬
        for(int i=0; i<bag.length; i++){
            //2.선택된 가방에 넣을 수 있는 남은 보석 중 가장 비싼 보석을 선택. <- 힙을 사용.
            while(jIndex < N && jewelry[jIndex].weight <= bag[i]){
                pq.add(jewelry[jIndex++]);
            }
            if(!pq.isEmpty()){
                result +=pq.poll().price;
            }
        }
        System.out.println(result);
    }
}

class Bosuk {
    int weight;
    int price;

    public Bosuk(int weight, int price) {
        this.weight = weight;
        this.price = price;
    }
}

 

 

 

 

 

그림을 그려 케이스 설정

2042: 구간 합 구하기

인덱스트리

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N, M, K;
    static long[] nums;
    static long[] tree;

    static int command, param1;
    static long param2;

    static int S;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("src/DAY03/P2042/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        nums = new long[N];

        for (int i = 0; i < N; i++) {
            nums[i] = Long.parseLong(br.readLine());
        }

        S = 1;
        while (S < N) {
            S *= 2;
        }
        tree = new long[S * 2];
    }

    static void initBU() {
        // Leaf에 값 반영
        for (int i = 0; i < N; i++) {
            tree[S + i] = nums[i];
        }
        // 내부노드 채움
        for (int i = S - 1; i > 0; i--) {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }
    }

    static long query(int left, int right, int node, int queryLeft, int queryRight) {
        // 연관이 없음 -> 결과에 영향이 없는 값 return
        if (queryRight < left || right < queryLeft) {
            return 0;
        }
        // 판단 가능 -> 현재 노드 값 return
        else if (queryLeft <= left && right <= queryRight) {
            return tree[node];
        }
        // 판단불가, 자식에게 위임, 자식에서 올라온 합을 return
        else {
            int mid = (left + right) / 2;
            long resultLeft = query(left, mid, node * 2, queryLeft, queryRight);
            long resultRight = query(mid + 1, right, node * 2 + 1, queryLeft, queryRight);
            return resultLeft + resultRight;
        }
    }

    static void update(int left, int right, int node, int target, long diff) {
        //연관없음
        if (target < left || right < target) {
            return;
        }
        //연관 있음 -> 현재 노드에 diff 반영 -> 자식에게 diff전달
        else {
            tree[node] += diff;
            if (left != right) {
                int mid = (left + right) / 2;
                update(left, mid, node * 2, target, diff);
                update(mid + 1, right, node * 2 + 1, target, diff);
            }
        }
    }

    static long queryBU(int queryLeft, int queryRight) {
        // Leaf 에서 left, right 설정
        int left = S + queryLeft - 1;
        int right = S + queryRight - 1;
        long sum = 0;
        while (left <= right) {
            // 좌측 노드가 홀수이면 현재 노드 값 사용하고 한칸 옆으로
            if (left % 2 == 1) {
                sum += tree[left++];
            }
            // 우측 노드가 짝수이면 현재 노드 값 사용하고 한칸 옆으로
            if (right % 2 == 0) {
                sum += tree[right--];
            }
            // 좌측,우측 모두 부모로 이동
            left /= 2;
            right /= 2;
        }
        return sum;
    }

    static void updateBU(int target, long value) {
        //Leaf에서 target을 찾음
        int node = S + target - 1;
        //value 반영
        tree[node] = value;
        //Root에 도달할 때 까지 부모에 값 반영
        node /= 2;
        while (node > 0) {
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
            node /= 2;
        }
    }
}

 

 

2243: 사탕상자

인덱스 트리

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static int A, B, C;
    static int MAX = 1000000;
    static int[] tree;
    static int S;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        S = 1;
        while (S < MAX) {
            S *= 2;
        }
        tree = new int[2 * S];
        N = Integer.parseInt(br.readLine());

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            if (A == 2) {
                B = Integer.parseInt(st.nextToken());
                C = Integer.parseInt(st.nextToken());
                update(1, S, 1, B, C);
            } else if (A == 1) {
                B = Integer.parseInt(st.nextToken());
                int index = query(1, S, 1, B);
                update(1, S, 1, index, -1);
                System.out.println(index);
            }
        }
    }

    static int query(int left, int right, int node, int count) {
        // 1. Leaf 에 도착했을때 -> 사탕 번호 반환
        if (left == right) {
            return left;
        } else {
            int mid = (left + right) / 2;
            // 2. 왼쪽 >= count -> 왼쪽으로 이동
            if (tree[node * 2] >= count) {
                return query(left, mid, node * 2, count);
            }
            // 3. 왼쪽 < count -> 오른쪽으로 이동
            else {
                count -= tree[node * 2];
                return query(mid + 1, right, node * 2 + 1, count);
            }
        }
    }

    static void update(int left, int right, int node, int index, long diff) {
        if (left <= index && index <= right) {
            tree[node] += diff;
            if (left != right) {
                int mid = (left + right) / 2;
                update(left, mid, node * 2, index, diff);
                update(mid + 1, right, node * 2 + 1, index, diff);
            }
        }
    }
}

 

Indexed Tree.pdf

0.98MB