ABOUT ME

    -

    Today
    -
    Yesterday
    -
    Total
    -
    • 자료구조 & 알고리즘 시작
      취업용 CS/자료구조 & 알고리즘 2025. 9. 22. 11:23

      1. 자료구조 (Data Structure)

      👉 자료구조는 데이터를 효율적으로 저장하고 관리하는 방법입니다.
      대표적으로 아래가 있고, 코딩테스트 & 면접에서 반드시 나옵니다.

      • 배열(Array)
        • 장점: 인덱스로 O(1) 접근 가능
        • 더보기
          배열은 연속된 메모리 공간에 원소들이 순서대로 저장됨
          arr = [10, 20, 30, 40]
          인덱스 값 메모리 주소
          0 10 1000
          1 20 1004
          2 30 1008
          3 40 1012

          👉 정수(int)가 4바이트라고 가정하면,

          • arr[0] = 주소 1000
          • arr[1] = 1000 + (1 * 4)
          • arr[2] = 1000 + (2 * 4)
            이렇게 계산 가능

          즉, 인덱스만 알면 곧바로 메모리 주소를 산출할 수 있기 때문에 접근 속도가 일정해져서 O(1) 이라고 하는 거야.

          📌 다른 자료구조와 비교

          • 배열: 인덱스 계산으로 바로 접근 → O(1)
          • 연결 리스트: 앞에서부터 하나하나 따라가야 함 → O(N)


          📌 시간 복잡도 정리

          • 배열(Array)
            • 인덱스로 접근: O(1)
            • 특정 값 찾기: O(N) (검색은 하나하나 봐야 함)
            • 중간에 삽입/삭제: O(N) (뒤를 다 밀어야 함)
          • 연결리스트(Linked List)
            • 인덱스로 접근: O(N)
            • 앞 삽입/삭제: O(1)


        • 단점: 삽입/삭제 O(N)
      • 연결 리스트(Linked List)
        • 노드(node)와 포인터로 구성
        • 장점: 삽입/삭제 O(1)
        • 단점: 임의 접근 불가 (탐색 O(N))
      • 스택(Stack)
        • LIFO 구조 (Last In, First Out)
        • 예: 함수 호출(콜스택), 괄호 검사
        • 더보기

          📌 문제: 괄호 문자열 검사

          • 입력: "(()())" 같은 문자열
          • 조건: 여는 괄호 (와 닫는 괄호 )가 짝이 맞는지 확인
          • 출력: 올바르면 True, 아니면 False

          📌 왜 스택(Stack)으로 푸나?

          • 스택은 LIFO (Last In, First Out) 구조
          • 여는 괄호 (가 나오면 스택에 push
          • 닫는 괄호 )가 나오면 스택에서 pop
            • 만약 pop할 게 없으면 → 잘못된 문자열
          • 문자열이 끝났을 때 스택이 비어있으면 → 올바른 괄호 문자열

          📌 동작 예시

          문자열: "(()())"

          1. ( → push → stack = [(]
          2. ( → push → stack = [(, (]
          3. ) → pop → stack = [(]
          4. ( → push → stack = [(, (]
          5. ) → pop → stack = [(]
          6. ) → pop → stack = []

          👉 끝났을 때 스택이 비어있음 → 올바른 괄호 ✅

           

          문자열: "(()"

          1. ( → push → stack = [(]
          2. ( → push → stack = [(, (]
          3. ) → pop → stack = [(]
            👉 문자열 끝났는데 stack = [(] (안 비어있음) → False ❌

          문자열: ")("

          1. ) → pop 하려 했는데 stack 비어있음 → False ❌

          📌 코드 예제 (Python)

          def is_valid_parentheses(s: str) -> bool:
              stack = []
              for ch in s:
                  if ch == "(":
                      stack.append(ch)   # push
                  elif ch == ")":
                      if not stack:      # 비었는데 pop하려 함
                          return False
                      stack.pop()        # pop
              return not stack  # 끝나고 스택이 비었으면 True

           

          📌 시간 복잡도

          • 문자열 길이 N만큼 검사 → O(N)
          • 각 연산(push/pop)은 O(1)
            👉 전체 O(N)
      • 큐(Queue)
        • FIFO 구조 (First In, First Out)
        • 예: 프로세스 스케줄링, 버퍼
        • 더보기

          📌 버퍼(Buffer)란?

          • 데이터를 잠시 저장하는 임시 저장 공간
          • CPU ↔ I/O 장치, 네트워크 송수신, 영상/음성 스트리밍 등에서 사용됨
          • 역할:
            1. 속도 차이 완충
              • CPU는 매우 빠른데, 디스크나 네트워크는 느림
              • 버퍼가 중간에서 데이터를 모았다가 한 번에 처리 → 속도 차이 해결
            2. 데이터 전송 효율화
              • 작은 단위로 계속 주고받으면 비효율 → 버퍼에 모아서 전송
            3. 비동기 처리 가능
              • CPU는 버퍼에 데이터만 던져놓고 다른 일 수행, 나중에 I/O 장치가 알아서 소비

          📌 큐(Queue)는 왜 쓰나?

          버퍼의 동작 방식은 대부분 FIFO(First In First Out) 구조야.
          즉, 먼저 들어온 데이터가 먼저 나가야 순서 보장이 됨.

          예시:

          1. 키보드 입력 버퍼
            • 사용자가 A, B, C 입력 → OS의 입력 버퍼 큐에 저장
            • 프로그램이 하나씩 꺼내 처리 → A → B → C 순서 보장
          2. 네트워크 패킷 버퍼
            • 패킷이 도착하면 수신 버퍼(큐)에 쌓임
            • CPU가 순서대로 처리
          3. 동영상 스트리밍 버퍼
            • 영상 데이터를 큐에 쌓아두고, 플레이어가 순서대로 소비
            • 네트워크 끊김에도 잠시 재생이 이어지는 이유

          📌 프로세스 스케줄링과 큐/버퍼

          • Ready Queue: 실행 대기 중인 프로세스들이 FIFO 구조로 줄 서 있음
          • I/O Buffer Queue: 디스크/프린터/네트워크 등 장치 요청 처리 대기

          👉 결국, 운영체제는 프로세스/데이터를 임시로 모아두고 순서대로 처리하기 위해 큐를 이용하는 거야.

           

          ✅ 정리:

          • 버퍼 = 임시 저장 공간 (속도 차이 완충, 비동기 처리)
          • 큐 = 버퍼 안에서 “데이터를 꺼내는 규칙(FIFO)”을 구현하는 자료구조
          • OS는 CPU, I/O, 네트워크에서 순서를 보장하기 위해 큐 기반 버퍼를 활용
        • 더보기

          📌 프로세스 스케줄링과 큐

          운영체제(OS)는 CPU를 여러 프로세스가 번갈아 사용하도록 스케줄링함.
          이때 프로세스들은 보통 큐(queue) 구조에 저장돼서 관리돼.

           

          1. 프로세스 상태 전이와 큐

          프로세스는 크게 3가지 상태를 가짐:

          • Ready 상태: CPU를 기다림 → Ready Queue에 들어감
          • Running 상태: CPU 점유 중
          • Waiting(Blocked) 상태: I/O 작업 기다림 → Device Queue에 들어감

          👉 즉, CPU를 당장 못 쓰는 프로세스들은 큐에 쌓였다가 순서대로 꺼내짐

           

          2. Ready Queue (준비 큐)

          • CPU를 기다리는 프로세스들이 줄 서는 곳
          • 스케줄러가 이 큐에서 프로세스를 꺼내 CPU에 할당
          • 큐 자료구조이기 때문에, 어떤 스케줄링 알고리즘을 쓰느냐에 따라 꺼내는 방식이 달라짐

          3. 스케줄링 알고리즘과 큐 활용

          • FCFS (First Come First Serve)
            • 선입선출(Queue의 기본)
            • Ready Queue에서 먼저 들어온 프로세스를 먼저 실행
            • 예: 프린터 줄 서기
          • SJF (Shortest Job First)
            • Ready Queue 안에서 “CPU burst time”이 짧은 프로세스를 우선 선택
            • 큐는 쓰지만, 꺼낼 때 정렬/우선순위 고려
          • Priority Scheduling
            • Ready Queue에서 우선순위가 높은 프로세스를 먼저 꺼냄
            • 구현 시 일반 큐 대신 우선순위 큐(Priority Queue, Heap) 사용
          • Round Robin (RR)
            • Ready Queue에서 정해진 시간(타임 퀀텀) 동안만 실행
            • 시간이 지나면 다시 큐 맨 뒤로 보내고, 다음 프로세스 실행
            • → 공정성을 보장하는 대표적인 방식
            • 이 경우 큐는 원형 큐(Circular Queue) 구조로 구현됨

          4. Device Queue (입출력 큐)

          • 프로세스가 I/O 요청을 하면 CPU에서 빠져나와 Device Queue에 들어감
          • I/O가 끝나면 다시 Ready Queue로 이동

          ✅ 정리

          • 큐는 프로세스들이 CPU/I-O를 기다릴 때 줄 서는 자료구조
          • FCFS, Round Robin 같은 알고리즘은 일반 큐 / 원형 큐를 기반으로 동작
          • Priority Scheduling 같은 건 우선순위 큐(힙) 사용
      • 덱(Deque)
        • 양쪽에서 삽입/삭제 가능 → sliding window 문제에서 자주 사용
        • 더보기

          📌 Sliding Window란?

          • 배열이나 문자열 같은 선형 자료구조에서 일정 구간(윈도우)의 값을 효율적으로 계산하는 방법.
          • “윈도우” = 연속된 부분 구간(subarray).
          • 이 윈도우를 한 칸씩 밀면서(slide) 결과를 업데이트.

          👉 핵심: O(N²) 반복문을 O(N)~O(N log N)으로 최적화 가능.

           

          📌 예시 1: 최대 합 구간

          배열: [2, 1, 5, 1, 3, 2]
          문제: 길이 3인 구간의 합 중 최댓값은?

          나이브 접근 (O(N*K))

          • [2,1,5] → 8
          • [1,5,1] → 7
          • [5,1,3] → 9
          • [1,3,2] → 6
            👉 답 = 9

          하지만 매번 합을 새로 구하면 O(N*K).

          슬라이딩 윈도우 (O(N))

          1. 처음 [2,1,5] 합 = 8
          2. 한 칸 밀면서: 앞 값 빼고, 새 값 더함
            • [1,5,1] → 8 - 2 + 1 = 7
            • [5,1,3] → 7 - 1 + 3 = 9
            • [1,3,2] → 9 - 5 + 2 = 6
              👉 최댓값 = 9

          코드 (Python):

          def max_subarray_sum(arr, k):
              window_sum = sum(arr[:k])
              max_sum = window_sum
              for i in range(k, len(arr)):
                  window_sum += arr[i] - arr[i-k]
                  max_sum = max(max_sum, window_sum)
              return max_sum

          print(max_subarray_sum([2,1,5,1,3,2], 3))  # 9

           

          📌 예시 2: 문자열 부분 문제

          문제: 문자열 "abcabcbb"에서 가장 긴 중복 없는 부분 문자열의 길이는?

          • 슬라이딩 윈도우로 시작-끝 포인터를 조절하면서 검사.
          • 해시셋/해시맵과 같이 쓰임.
            👉 코딩테스트에서 자주 등장!

          📌 예시 3: Deque + Sliding Window

          문제: 배열에서 “윈도우 내 최댓값”을 구해라.

          • 단순 O(N*K)로 풀면 시간 초과
          • → Deque(덱)을 이용해 윈도우 내 최댓값을 관리 → O(N)

          📌 정리

          • Sliding Window = 일정 구간을 계속 밀면서 효율적으로 결과 갱신
          • 코테에서 자주 쓰이는 유형:
            1. 고정 길이 부분합 / 평균
            2. 조건 만족하는 최소/최대 길이 부분 배열
            3. 문자열 처리 (중복 없는 부분 문자열, 아나그램 검사 등)
            4. 덱과 결합 → 구간 최댓값, 최솟값

          👉 이걸 응용하면 코테 문제에서 **“연속된 부분”**이라는 단어가 나오면 거의 항상 sliding window를 떠올려야 해.

      • 해시테이블(Hash Table)
        • Key → Hash Function → Index에 저장
        • 평균 O(1), 최악 O(N)
        • 예: 파이썬 dict, 자바 HashMap
      • 트리(Tree)
        • 계층 구조.
        • Binary Search Tree(BST): 왼쪽 < 루트 < 오른쪽
        • Heap: 최대/최소 우선순위 관리 (우선순위 큐)
        • 더보기

          📌 1. 우선순위 큐(Priority Queue)란?

          • 일반 큐(Queue): FIFO (First In First Out)
            → 먼저 들어온 데이터가 먼저 나감.
          • 우선순위 큐: “우선순위가 높은 데이터가 먼저 나감”
            → 줄을 서더라도 VIP가 있으면 VIP 먼저 처리됨.

          예시:

          • 병원 응급실 환자 대기
          • 운영체제의 Priority Scheduling (우선순위 높은 프로세스 먼저 CPU 할당)

          📌 2. Heap이 필요한 이유

          우선순위 큐를 구현하려면 우선순위에 따라 **가장 큰 값(최대) 또는 가장 작은 값(최소)**을 빠르게 꺼낼 수 있어야 함.

          • 배열로 구현 → 꺼낼 때 O(N) (최댓값 찾으려면 다 뒤져야 함)
          • 정렬된 배열 → 삽입 O(N) (매번 정렬 유지해야 함)

          👉 그래서 나온 자료구조가 Heap

           

          📌 3. Heap 구조

          • 완전 이진 트리(Complete Binary Tree) 기반
          • 부모 노드와 자식 노드 사이의 힙 속성(Heap Property) 유지

          (1) Max-Heap (최대 힙)

          • 부모 노드 ≥ 자식 노드
          • 루트(root)에 항상 최댓값 존재

          (2) Min-Heap (최소 힙)

          • 부모 노드 ≤ 자식 노드
          • 루트(root)에 항상 최솟값 존재

          📌 4. Heap으로 Priority Queue 구현

          • 삽입(insert): 새로운 원소를 힙에 추가한 뒤 위로 올리며(heapify-up) 정렬 유지
          • 삭제(delete): 루트(최댓값/최솟값)를 꺼낸 뒤 마지막 원소를 루트에 올리고, 아래로 내려가며(heapify-down) 정렬 유지

          ⏱ 시간 복잡도:

          • 삽입: O(log N)
          • 삭제(최대/최소 꺼내기): O(log N)
          • 조회(루트 값 확인): O(1)

          👉 그래서 우선순위 큐 = Heap으로 구현하는 게 효율적임.

           

          📌 5. 코드 예시 (Python)

          import heapq

          # 기본: Min-Heap
          min_heap = []
          heapq.heappush(min_heap, 5)
          heapq.heappush(min_heap, 2)
          heapq.heappush(min_heap, 8)

          print(heapq.heappop(min_heap))  # 2 (가장 작은 값)
          print(heapq.heappop(min_heap))  # 5

          # Max-Heap은 음수로 저장하는 방식
          max_heap = []
          heapq.heappush(max_heap, -5)
          heapq.heappush(max_heap, -2)
          heapq.heappush(max_heap, -8)

          print(-heapq.heappop(max_heap))  # 8 (가장 큰 값)
          print(-heapq.heappop(max_heap))  # 5

           

          📌 정리

          • Priority Queue = “우선순위가 높은 원소를 먼저 꺼내는 큐”
          • Heap은 이를 효율적으로 구현하는 자료구조
            • Max-Heap: 최댓값을 빠르게 꺼냄
            • Min-Heap: 최솟값을 빠르게 꺼냄
          • 운영체제 스케줄링, 다익스트라(Dijkstra) 최단경로, 이벤트 처리 등에서 활용

           

      • 그래프(Graph)
        • 정점(V) + 간선(E)
        • 표현법: 인접 행렬, 인접 리스트
        • 탐색법: BFS, DFS

       

      2. 알고리즘 (Algorithm)

      👉 알고리즘은 문제를 해결하는 절차적 방법입니다.

      • 정렬 알고리즘
        • QuickSort: 평균 O(N log N), 최악 O(N²)
        • MergeSort: 항상 O(N log N), 안정적
        • HeapSort: O(N log N), 힙 기반
      • 탐색 알고리즘
        • 이진 탐색(Binary Search): 정렬된 배열에서 O(log N)
        • BFS: 최단거리 탐색
        • DFS: 깊이 우선 탐색
      • 문제 해결 패턴
        • 그리디(Greedy): 매 순간 최적 선택 (예: 거스름돈 문제, Kruskal)
        • 분할정복(Divide & Conquer): 큰 문제 → 작은 문제로 쪼갬 (MergeSort, QuickSort)
        • 동적 계획법(DP): 부분 문제의 답을 저장하며 푸는 방식 (피보나치, Knapsack)
      • 그래프 알고리즘
        • Dijkstra: 단일 출발 최단경로
        • Floyd-Warshall: 모든 쌍 최단경로
        • MST(최소 신장 트리): Kruskal, Prim

       

      3. 예제 (쉬운 코테 수준)

      👉 스택/큐 기본 문제
      괄호 문자열이 올바른지 확인하는 문제

       

      def is_valid_parentheses(s: str) -> bool:
          stack = []
          for ch in s:
              if ch == "(":
                  stack.append(ch)
              elif ch == ")":
                  if not stack:
                      return False
                  stack.pop()
          return not stack

      print(is_valid_parentheses("(()())"))  # True
      print(is_valid_parentheses("(()"))     # False

       

      👉 이진 탐색 예제
      정렬된 리스트에서 target 찾기

       

      def binary_search(arr, target):
          left, right = 0, len(arr) - 1
          while left <= right:
              mid = (left + right) // 2
              if arr[mid] == target:
                  return mid
              elif arr[mid] < target:
                  left = mid + 1
              else:
                  right = mid - 1
          return -1

      print(binary_search([1,3,5,7,9], 7))  # 3
      print(binary_search([1,3,5,7,9], 2))  # -1

       

       

      • 자료구조·알고리즘 틀 내 진도: 약 20% 완료
        • ✅ 자료구조 개요 (10%)
        • ✅ 알고리즘 개요 (10%)
        • ⏳ 심화(트리/힙/그래프 구현, DP/그리디 문제 풀이 등) 남음
      • 전체 CS 틀 내 진도:
        • 자료구조·알고리즘(30%) 중 20% 달성 → 전체 CS 대비 약 6%

       

       

      '취업용 CS > 자료구조 & 알고리즘' 카테고리의 다른 글

      자료구조 심화  (0) 2025.09.22
      여는 글  (1) 2025.09.22

      관련글 관련글 더보기

    Designed by Tistory.

    티스토리툴바