[Algo] 기본 자료구조

seungyeon·2023년 3월 12일

자료구조/알고리즘

목록 보기

1/6

스택(FILO) : DFS 알고리즘에서 주로 사용

입구와 출구가 동일한 형태
먼저 들어 온 데이터가 나중에 나가는 형식
시간복잡도 :

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();

        s.push(5);
        s.push(2);
        s.push(3);
        s.push(7);
        s.pop(); //7
        s.push(1);
        s.push(4);
        s.pop(); //4

        //스택의 최상단 원소부터 출력
        while(!s.empty()){
            System.out.print(s.peek() + " "); //1 3 2 5
            s.pop();
        }
    }
}

큐(FIFO) : BFS 알고리즘

먼저 들어 온 데이터가 먼저 나가는 형식
입구와 출구가 모두 뚫려 있는 터널과 같은 형식
왼쪽으로 데이터가 들어옴 순서 : 5 2 3 7 삭제는 오른쪽부터
7 3 2 5

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();

        q.offer(5);
        q.offer(2);
        q.offer(3);
        q.offer(7);
        q.poll(); //5
        q.offer(1);
        q.offer(4);
        q.poll(); //2

        //먼저 들어온 원소부터 추출
        while(!q.empty()){
            System.out.print(q.poll() + " "); //3 7 1 4
        }
    }
}

우선순위 큐 : 가장 우선순위가 높은 데이터를 가장 먼저 삭제하는 자료구조

1) 리스트(list)
2) 힙(heap)

단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 (힙 정렬) : O(NlogN)

힙
: 완전이전트리 : 루트노드부터 시작해서 왼쪽 자식노드 > 오른쪽 자식노드 순으로 삽입되는 트리

트리

: 계층적인 구조를 표현할 때 사용할 수 있는 자료구조
루트노드 : 부모가 없는 최상위 노드
단말노드 : 자식이 없는 노드(가장 아래에 있는 노드)
크기 : 트리에 포함된 모든 노드의 개수
깊이 : 루트 노드부터의 거리
높이 : 깊이 중 최대값 (루트부터 맨끝노드까지의 가지 수)
차수 : 각 노드의 간선 개수(현재 자신 노드에서 자식방향 수)