자료구조(Data Structure)

자료구조는 데이터를 효율적으로 저장하고 관리하는 방식입니다.
대량의 데이터를 다룰 때 삽입, 삭제, 검색, 정렬, 순회 같은 기본 연산을 효율적으로 처리하도록 도와줍니다.
자료구조는 크게 두 가지로 나누어집니다:

  • 선형 자료구조: 배열, 연결 리스트, 스택, 큐처럼 데이터를 순서대로 나열하는 구조
  • 비선형 자료구조: 트리, 그래프처럼 계층적이거나 복잡한 관계를 표현하는 구조

자료구조 특징

  1. 효율성
    문제에 적절한 자료구조를 사용하면 속도와 자원 효율이 향상됩니다.
  2. 추상화
    복잡한 내부 구조는 숨기고 핵심적인 기능만을 표현함으로써 사용자는 사용법에 집중할 수 있습니다.
  3. 재사용성
    범용적으로 설계된 자료구조는 여러 프로젝트에서 재사용이 가능하여 유지보수에도 유리합니다.

알고리즘(Algorithms)

알고리즘은 문제를 해결하기 위한 단계적인 절차입니다.
입력을 받아 원하는 출력을 만들어내는 과정을 의미하며,
좋은 알고리즘은 빠르게 실행되면서도 적은 자원을 사용합니다.

자료형(Data Type)

자료형은 데이터의 종류와 형식을 정의한 것입니다.
예를 들어, 정수형(Int), 실수형(Float), 문자열(String) 등은 기초 자료형(Primitive Type)에 해당합니다.
이 외에도 여러 데이터를 묶은 구조체, 클래스 같은 복합 자료형(Composite Type)도 존재합니다.

추상 자료형(Abstruct Data Types, ADT)

추상 자료형은 데이터의 구조와 이를 처리하는 연산만 정의하고, 구체적인 구현은 숨기는 개념입니다.
사용자는 내부 구현을 몰라도 되고, 기능(인터페이스)만 알면 됩니다.

대표적인 ADT 예시: 스택, 큐, 리스트, 트리
정보 은닉과 모듈화를 통해 재사용성과 유지보수성이 뛰어납니다.
수학적으로 정의된 개념으로, 실제 구현(배열, 연결 리스트 등)과는 분리되어 있습니다.
➡️ 즉, ADT는 ‘무엇을 할 수 있는가’에 집중하고, 구현 방식은 자유롭게 선택할 수 있는 설계 방식입니다.

추상화(Abstraction)

추상화는 불필요한 세부 사항을 숨기고, 핵심 기능에 집중하는 것입니다.
복잡한 시스템을 단순하게 바라보게 해 주며, 유지보수성과 이해도를 높입니다.

프로그램

프로그램 = 자료구조 + 알고리즘
소프트웨어는 결국 데이터를 어떻게 구조화(자료구조)하고,
그 데이터를 어떻게 처리할지(알고리즘) 결정하는 것이 핵심입니다.

시간복잡도

시간 복잡도는 알고리즘이 실행될 때 주요 연산이 얼마나 반복되는지를 정량적으로 나타낸 값입니다.
연산에는 산술, 대입, 비교, 이동 연산 등이 포함되며,
이를 통해 알고리즘 간 성능 비교가 가능합니다.

순환(Recursion)

어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법입니다.
주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 분할 정복이 있습니다.
순환 호출시에는 호출이 일어날 때마다 호출하는 함수의 상태를 기억해야 하므로 여분의 기억장소가 필요합니다.
순환은 이해하기 쉽지만 비효율적인 경우가 많습니다.

활성 레코드(Activation Record)

프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일합니다.
복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수(parameter)와 지역변수를 스택으로부터 할당받는데 이러한 공간을 활성 레코드라고 합니다. 호출된 함수가 자기 자신이라면 자기 자신의 시작 위치로 점프하게 됩니다. 호출된 함수가 끝나게 되면 시스템 스택에서 복귀주소를 추출하여 호출한 함수로 되돌아갑니다.

꼬리 순환(Tail Recursion)

순환 호출이 끝에서 이루어지는 순환을 꼬리 순환이라고 하는데 이를 반복 알고리즘으로 쉽게 바꾸어 쓸 수 있습니다.

  • 반복이 빠른 예시
    • 팩토리얼(순환, 반복 둘다 시간복잡도는 O(n)이지만 순환에서는 여분의 기억공간이 필요하고 함수를 호출하기 위해 함수의 매개변수들을 스택에 저장하는 사전 작업이 필요하다.)
  • 순환이 빠른 예시
    • 거듭제곱(logn)

Reference

  • https://bnzn2426.tistory.com/115
  • https://developer-haru.tistory.com/70
  • https://wikidocs.net/224929
  • https://velog.io/@ghldjfldj/자료구조-자료구조란

Leave a comment