[URECA] Day 18 | 알고리즘 | 비선형 자료구조

비선형 자료구조란?

정의: 비선형 자료 구조는 데이터가 선형적으로 배치되지 않고,

계층적 또는 비계층적으로 연결된 구조

필요성: 복잡한 관계를 표현하고, 효율적인 데이터 검색 및 관리 가능

종류: 트리, 그래프

 

트리

 

⭐⭐⭐ 용어 ⭐⭐⭐
노드: 데이터의 단위(정점)
루트: 트리의 최상위 노드(첫 노드)
리프: 자식 노드가 없는 노드(끝 노드)
서브트리: 특정 노드를 루트로 하는 하위 트리
높이: 트리의 루트에서 가장 깊은 리프까지의 경로 길이(전체 깊이)
깊이: 특정 노드가 루트에서 얼마나 떨어져 있는지를 나타냅니다
간선: 부모 노드와 자식 노드를 연결,트리는 사이클이 없고, 항상 연결되어 있어야 함. 노드 수가 n이면 간선의 수는 항상 n-1

예시:
1. 파일 시스템: 컴퓨터의 파일 시스템은 트리 구조로 표현됨
정점: 폴더와 파일
간선: 폴더가 포함하는 파일이나 하위 폴더 간의 관계
설명: 최상위 폴더(루트)가 있고, 그 아래에 여러 하위 폴더가 있으며, 각 하위 폴더는 또 다른 파일이나 폴더를 포함할 수 있음

2. 조직도: 회사의 조직 구조
정점: 직원
간선: 상사와 부하 직원 간의 관계
설명: CEO가 루트 노드가 되고, 각 부서의 관리자와 그 아래의 직원들이 자식 노드로 연결됨

3. 가족 트리: 개인의 가족 관계를 나타내는 가족 트리
정점: 가족 구성원 (부모, 자식, 조부모 등)
간선: 부모와 자식 간의 관계
설명: 한 사람을 루트로 하고, 그 사람의 부모, 자식, 조부모 등을 나열하여 가족 관계를 시각화

4. 우선 순위 큐: 우선 순위 큐를 구현할 때 사용하는 힙(Heap) 구조
정점: 요소
간선: 부모 노드와 자식 노드 간의 관계
설명: 최소 힙 또는 최대 힙 구조에서 각 요소는 부모 노드와 자식 노드로 연결되어 우선 순위를 유지

 

 

이진트리 순회 코드

/*
 * https://www.acmicpc.net/problem/1991
*/

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class C01_BOJ1991_트리순회 {
    // 이진 트리를 저장할 맵 선언
    static Map<Character, Character[]> tree = new HashMap<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();// 노드 개수 입력
        scanner.nextLine(); // 개행 문자 제거

        // 트리 구조 입력 받기
        for (int i = 0; i < n; i++) {
            String input = scanner.nextLine();
            char parent = input.charAt(0); // 부모 노드
            char leftChild = input.charAt(2); // 왼쪽 자식 노드
            char rightChild = input.charAt(4); // 오른쪽 자식 노드
            
            // 왼쪽 자식이 '.'가 아닌 경우에만 추가
            if (leftChild != '.') {
                tree.putIfAbsent(parent, new Character[2]);// 덮어쓰기 방지되는 put. 자식 노드를 두 개 넣을 수 있어야 하니 length가 2인 배열생성
                tree.get(parent)[0] = leftChild; // 왼쪽 자식 저장
            }
            // 오른쪽 자식이 '.'가 아닌 경우에만 추가
            if (rightChild != '.') {
                tree.putIfAbsent(parent, new Character[2]);
                tree.get(parent)[1] = rightChild; // 오른쪽 자식 저장
            }
        }//size n인 map 생성 완료

        // 전위 순회 출력 (루트) (왼쪽 자식) (오른쪽 자식)
        preOrder('A');
        System.out.println(); // 줄 바꿈

        // 중위 순회 출력 (왼쪽 자식) (루트) (오른쪽 자식)
        inOrder('A');
        System.out.println(); // 줄 바꿈

        // 후위 순회 출력 (왼쪽 자식) (오른쪽 자식) (루트)
        postOrder('A');
        System.out.println(); // 줄 바꿈
    }

    // 전위 순회 메서드
    static void preOrder(char node) {
        if (node == '.') return; // 리프 노드일 경우 종료
        System.out.print(node); // 현재 노드 출력
        if (tree.containsKey(node)) {
            Character[] children = tree.get(node);
            if (children[0] != null) preOrder(children[0]); // 왼쪽 자식으로 재귀 호출
            if (children[1] != null) preOrder(children[1]); // 오른쪽 자식으로 재귀 호출
        }
    }

    // 중위 순회 메서드
    static void inOrder(char node) {
        if (node == '.') return; // 리프 노드일 경우 종료
        if (tree.containsKey(node)) {
            Character[] children = tree.get(node);
            if (children[0] != null) inOrder(children[0]); // 왼쪽 자식으로 재귀 호출
        }
        System.out.print(node); // 현재 노드 출력
        if (tree.containsKey(node)) {
            Character[] children = tree.get(node);
            if (children[1] != null) inOrder(children[1]); // 오른쪽 자식으로 재귀 호출
        }
    }

    // 후위 순회 메서드
    static void postOrder(char node) {
        if (node == '.') return; // 리프 노드일 경우 종료
        if (tree.containsKey(node)) {
            Character[] children = tree.get(node);
            if (children[0] != null) postOrder(children[0]); // 왼쪽 자식으로 재귀 호출
            if (children[1] != null) postOrder(children[1]); // 오른쪽 자식으로 재귀 호출
        }
        System.out.print(node); // 현재 노드 출력
    }
}

 

트리구조에서 노드 탐색을 위한 효율적 방법

이진검색 (분할정복)

어떤 노드를 찾기 위해 모든 노드를 순회해야 한다면(완전탐색) O(n)이 된다. 이것을 O(log n)으로 만들 수 있는 방법이 이진 검색이다.

조건:
모든 노드가 정렬되어 있어야 함

 

 

트리가 아닌 1차원 배열로 이진검색 이해

public class BinarySearch {

    // 이진 검색 메서드
    public static int binarySearch(int[] arr, int target) {
        int low = 0;              // 검색 시작 인덱스
        int high = arr.length - 1; // 검색 종료 인덱스

        while (low <= high) {
            int mid = (low + high) / 2; // 중간 인덱스 계산

            // 중간값과 타겟 비교
            if (arr[mid] == target) {
                return mid; // 타겟을 찾았을 경우 인덱스 반환
            } else if (arr[mid] < target) {
                low = mid + 1; // 타겟이 중간값보다 클 경우 왼쪽 범위를 무시
            } else {
                high = mid - 1; // 타겟이 중간값보다 작을 경우 오른쪽 범위를 무시
            }
        }
        return -1; // 타겟이 배열에 없을 경우 -1 반환
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15}; // 정렬된 배열
        int target = 7; // 찾고자 하는 값

        int result = binarySearch(sortedArray, target); // 이진 검색 호출

        if (result != -1) {
            System.out.println("타겟 " + target + "은(는) 인덱스 " + result + "에 있습니다.");
        } else {
            System.out.println("타겟 " + target + "은(는) 배열에 없습니다.");
        }
    }
}

java.util.Arrays.binarySearch()사용하기

import java.util.Arrays;

public class BinarySearchExample {

    public static void main(String[] args) {
        // 정렬된 배열 생성
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15};

        // 찾고자 하는 값
        int target = 7;

        // 이진 검색을 통해 값의 인덱스 찾기
        int result = Arrays.binarySearch(sortedArray, target);

        // 결과 출력
        if (result >= 0) {
            System.out.println("타겟 " + target + "은(는) 인덱스 " + result + "에 있습니다.");
        } else {
            System.out.println("타겟 " + target + "은(는) 배열에 없습니다.");
        }

        // 찾고자 하는 값이 배열에 없는 경우
        target = 4;
        result = Arrays.binarySearch(sortedArray, target);

        // 결과 출력
        if (result >= 0) {
            System.out.println("타겟 " + target + "은(는) 인덱스 " + result + "에 있습니다.");
        } else {
            System.out.println("타겟 " + target + "은(는) 배열에 없습니다.");
            //값이 발견되면 해당 값의 인덱스를 반환, 값이 발견되지 않으면 음수의 인덱스(-(삽입 위치 + 1))를 반환
        }
    }
}

 

문제 풀이

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


import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 첫 번째 줄: 수의 개수
        int n = scanner.nextInt();
        int[] arr = new int[n];

        // 배열 입력 받기
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        // 배열을 정렬
        Arrays.sort(arr);

        // 두 번째 줄: 찾고자 하는 수의 개수
        int m = scanner.nextInt();
        
        // 결과를 저장할 StringBuilder
        StringBuilder result = new StringBuilder();

        // 각각의 수에 대해 이진 검색 수행
        for (int i = 0; i < m; i++) {
            int target = scanner.nextInt(); // 찾고자 하는 수

            // 이진 검색을 통해 인덱스 찾기
            int index = Arrays.binarySearch(arr, target);

            // 결과를 확인하고 StringBuilder에 추가
            if (index >= 0) {
                result.append("1\n"); // 수가 존재하면 1 추가
            } else {
                result.append("0\n"); // 수가 존재하지 않으면 0 추가
            }
        }

        // 결과 출력
        System.out.print(result.toString());

        scanner.close(); // 스캐너 닫기
    }
}

 

트리구조에서 이진검색되는 API : java.util.TreeSet

편향 트리가 되면 O(log n)을 유지할 수 없고  O(n)이 되버리기 때문에 균형을 맞추기 위한 Red-Black Tree 라는 알고리즘으로 구현되어 있다

규칙
1. 삽입된 노드의 부모가 RED이며 삼촌 노드도 RED인 경우
조치: 부모와 삼촌을 BLACK으로 바꾸고 조부모를 RED로 바꿉니다. (칼라 반전만으로 해결)
2. 삽입된 노드가 부모의 오른쪽 자식이고, 부모가 할아버지의 왼쪽 자식이며, 삼촌이 BLACK인 경우
조치: 부모를 기준으로 왼쪽으로 회전한 후, 삽입된 노드와 부모의 색상을 조정합니다.
3. 삽입된 노드가 부모의 왼쪽 자식이고, 부모가 할아버지의 왼쪽 자식이며, 삼촌이 BLACK인 경우
조치: 부모와 할아버지의 색을 바꾼 후, 할아버지를 기준으로 오른쪽으로 회전합니다.
4. 삽입된 노드가 부모의 오른쪽 자식이고, 부모가 할아버지의 오른쪽 자식이며, 삼촌이 BLACK인 경우
조치: 부모와 할아버지의 색을 바꾼 후, 할아버지를 기준으로 왼쪽으로 회전합니다.
5. 삽입된 노드가 부모의 왼쪽 자식이고, 부모가 할아버지의 오른쪽 자식이며, 삼촌이 BLACK인 경우
조치: 부모를 기준으로 오른쪽으로 회전한 후, 삽입된 노드와 부모의 색상을 조정합니다.

 

import java.util.TreeSet;

public class TreeSetExample {

    public static void main(String[] args) {
        // TreeSet 생성
        TreeSet<Integer> treeSet = new TreeSet<>();

        // 요소 추가
        treeSet.add(5);   // 5 추가
        treeSet.add(3);   // 3 추가
        treeSet.add(8);   // 8 추가
        treeSet.add(1);   // 1 추가
        treeSet.add(7);   // 7 추가
        treeSet.add(25);
        treeSet.add(34);
        treeSet.add(2);
        treeSet.add(11);
        treeSet.add(17);
        

        // 요소 출력 (자동으로 정렬됨)
        System.out.println("TreeSet의 요소: " + treeSet); // 출력: [1, 3, 5, 7, 8]

        // 특정 요소 검색
        int searchElement = 5;
        if (treeSet.contains(searchElement)) {
            System.out.println(searchElement + "은(는) TreeSet에 존재합니다.");
        } else {
            System.out.println(searchElement + "은(는) TreeSet에 존재하지 않습니다.");
        }

        // 최소값과 최대값 찾기
        int minElement = treeSet.first(); // 최소값
        int maxElement = treeSet.last();  // 최대값
        System.out.println("최소값: " + minElement); // 출력: 1
        System.out.println("최대값: " + maxElement); // 출력: 8

        // 요소 삭제
        treeSet.remove(3); // 3 삭제
        System.out.println("3을 삭제한 후 TreeSet의 요소: " + treeSet); // 출력: [1, 5, 7, 8]

        // 부분 집합 (서브셋) 생성
        TreeSet<Integer> subSet = (TreeSet<Integer>) treeSet.subSet(5, true, 8, true);
        System.out.println("부분 집합: " + subSet); // 출력: [5, 7, 8]
    }
}

 

 

TreeSet VS. HashSet

TreeSet은 이진 탐색 트리를 기반으로 구현된 자료구조로, 정렬된 순서로 요소를 저장.
요소를 추가할 때 자동으로 정렬되며, 검색, 삽입, 삭제가 O(log n) 

HashSet은 해시 테이블을 기반으로 하며, 요소의 순서를 보장하지 않음. 
삽입, 삭제, 검색의 평균 시간 복잡도는 O(1)그러나 정렬하려면 별도의 작업이 필요하며, 이로 인해 성능 차이가 발생할 수 있음

 

import java.util.*;

public class SetPerformanceComparison {

    public static void main(String[] args) {
        // 데이터 개수
        int n = 100000;

        // TreeSet 성능 측정
        long startTime = System.nanoTime();
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            treeSet.add((int) (Math.random() * n));
        }
        long endTime = System.nanoTime();
        System.out.println("TreeSet 삽입 시간: " + (endTime - startTime) + " ns");

        // HashSet 성능 측정
        startTime = System.nanoTime();
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            hashSet.add((int) (Math.random() * n));
        }
        // HashSet을 ArrayList로 변환 후 정렬
        List<Integer> hashList = new ArrayList<>(hashSet);
        Collections.sort(hashList);
        endTime = System.nanoTime();
        System.out.println("HashSet 삽입 및 정렬 시간: " + (endTime - startTime) + " ns");
    }
}

 

프로그래머스 PCCE문제

 

프로그래머스 입문문제

 

노트북 렉 걸려서 줌 또 나가짐.. 10분 넘게 노트북 작동잘안됨.. 에효 😮‍💨 <- 한숨쉬는 이모지

프로그래머스 문제들이 엄청 밀렸다.. 

하지만 오늘 또 조퇴를 써야한다..

부지런히.. 따라가자.. 주말을 최대한 이용하고 (금토 1박 2일로 일정이 있어.. 이렇게 바쁘게될 줄 몰랐드아)

수업 끝나면 침대에 눕지말고 하나하나 도장깨보자..