[자료구조] 자료구조 기본 개념

알고리즘의 기본 개념

 

공간 복잡도 (Space Complexity)	프로그램이 실행되는 동안 필요한 메모리의 총량. → 변수, 배열, 재귀 스택 등의 크기로 결정됨	예: 크기 N의 배열을 사용하는 프로그램은 O(N) 공간이 필요함.
시간 복잡도 (Time Complexity)	프로그램이 완료될 때까지 걸리는 연산 횟수나 시간을 나타냄	예: 배열의 모든 원소를 더하는 프로그램은 O(N) 시간이 걸림.

 

알고리즘의 5가지 조건

입력(Input)	외부에서 제공되는 자료가 최소 하나 이상 있어야 함	예: 덧셈 프로그램은 두 수 a, b를 입력받음 → a=3, b=5
출력(Output)	알고리즘 수행 결과로 최소 하나 이상의 결과가 나와야 함	예: 3 + 5 = 8 출력
명백성 (명확성, Definiteness)	각 단계의 의미가 명확하고 모호하지 않아야 함	✅ “두 수를 더한다”는 명확함 ❌ “적당히 계산한다”는 모호함
유한성(Finiteness)	알고리즘은 유한한 단계 후 반드시 종료되어야 함	예: 덧셈 알고리즘은 입력 두 개를 더하고 한 번에 종료됨. 반면 “1을 계속 더한다”는 무한 루프 → ❌
유효성(Effectiveness)	각 단계는 실제로 수행 가능하고 간단한 연산으로 이루어져야 함	예: “두 수를 더한다”는 수행 가능하지만, “무한정 큰 수를 동시에 계산한다”는 불가능

스택 표기법의 기본 개념

구분이름연산자 위치예시 (A, B, +)설명

중위 표기법 (Infix)	일반적인 수학식	피연산자 사이	A + B	우리가 평소에 쓰는 형태
전위 표기법 (Prefix)	연산자가 앞에	+ A B	계산 순서를 명확히 하기 위함
후위 표기법 (Postfix)	연산자가 뒤에	A B +	스택 계산에 자주 사용됨 (컴파일러/계산기 원리)

---

예시 트리

        +
       / \
      *   E
     / \
    A   B

 

전위, 중위, 후위 결과

전위 (Root → L → R)	+ → * → A → B → E	+ * A B E
중위 (L → Root → R)	A → * → B → + → E	A * B + E
후위 (L → R → Root)	A → B → * → E → +	A B * E +

예상 문제 1)
다음 이진 트리에 대해 후위 순회(Postorder Traversal) 결과를 구하시오.

          -
         / \
        *   +
       / \ / \
      A  B C  D
      
      
      
   A. A B * C D + -   : 후위 /정답
   B. A B C D + * -   
   C. - * A B + C D   : 전위
   D. A B * - C D +
   E. A * B - C + D   : 중위

 

예상문제 2)
다음 이진 트리에 대해 중위 순회(Inorder Traversal) 결과를 구하시오.


            /
           / \
          -   E
         / \
        *   D
       / \
      A   B

	A. A * B - D / E    : 중위  / 정답
	B. / - * A B D E    : 전위
	C. A B * - D / E
	D. A * B D - E /
	E. A B * D - E /    : 후위

 

예상 문제 3)
후위식 3 4 5 * + 의 값을 구하시오.
(후위식은 왼쪽에서 차례로 스택에 넣으면 됨)

L R ROOT


스택을 이용한 풀이

스택 :
[3] , [3,4], [3,4,5], [3,4,5, *], [3, 20], [3, 20, +], [23]

정답 23

 

예상 문제 4)
전위식 + 3 * 4 5 의 값을 구하시오.
(전위식은 오른쪽에서 차례로 스택에 넣으면 됨)

ROOT L R

스택
[5], [5, 4], [5, 4, *], [20], [20, 3], [20, 3, +], [23]

 

 

큐 (Queue)

정의	먼저 들어온 데이터가 먼저 나가는 구조 (FIFO, First In First Out)
비유	줄 서서 입장하는 구조 — 먼저 줄 선 사람이 먼저 들어감
방향	한쪽 끝에서 삽입(rear), 다른 쪽 끝에서 삭제(front)
대표 함수	enqueue() 삽입, dequeue() 삭제

 

데크 (Deque, Double-Ended Queue)

정의	양쪽에서 삽입과 삭제가 모두 가능한 큐
이름 의미	Double-Ended Queue (→ Deque)
활용 예시	회전 큐, 슬라이딩 윈도우, 회전식 데이터 처리