워밍업클럽CS2기 1주차 발자국: 자료구조

자료구조

개요

• 자료구조와 알고리즘이란?

  • 자료구조

    • 데이터가 어떤 구조로 저장되고 어떻게 사용되는지 나타냄

      • ex) 변수, 배열

    • 자료구조에 따라 처리방법이 달라지고 코드가 단순해질 수 있음

  • 알고리즘

    • 어떤 문제를 해결하기 위한 확실한 방법

    • 자료구조 영향을 많이 받고 같은 자료구조라도 알고리즘이 달라질 수 있음

• 시간 복잡도

  • 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간

  • 일

    반적으로 성능의 척도는 알고리즘 속도로 평가됨

    • 알고리즘을 평가할 때는 코드에서 성능에 영향을 많이 주는 부분을 찾아 실행시간을 예측함 => 반복문

      • 최선의 경우: Big - 오메가

      • 최악의 경우: Big -O

      • 평균의 경우: Big- 세타

  • 빅 오 표기법

    • 입력이 늘어날 때 계산이 늘어가는 척도를 나타냄

자료구조

• 배열

  • 인덱스 참조는 길이에 상관없이 한 번에 가져오기 때문에 O(1) 성능

  • 읽기, 쓰기, 참조에서 좋은 성능을 보임

     

    • 크기 예측이 힘들어 메모리 낭비가 발생하기 때문에 데이터 삽입, 삭제 성능이 안좋음

• 연결리스트

  • 필요한 데이터만큼 노드를 만들어 저장하고 다른 노드를 연결함

  • 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근이 가능함

  • 저장하려는 데이터들을 메모리 공간에 분산해서 할당하고 이 데이터들을 서로 연결하는 노드를 활용하여 배열의 단점을 해결함

  • 배열과 연결리스트 비교

    • 배열은 시작주소만 알면 인덱스를 활용하여 뒤에 있는 데이터 접근이 쉬움

    • 연결리스트는 데이터들이 전부 떨어져있어 바로 접근할 수 없지만 배열 초기 크기를 몰라도 됨

    • 데이터 삽입 삭제가 자주 일어난다면 연결리스트, 참조가 자주 일어난다면 배열

• 스택

  • First In Last Out

  • 먼저 들어간 데이터가 나중에 나오는 규칙

  • 데이터 삽입과 제거를 무조건 첫번째 인덱스에 지정하면 연결리스트로 스택 구현 가능

• 큐

  • First In First out

  • 먼저 들어간 데이터가 먼저 나오는 규칙

  • FIFO 스케줄링

    • 운영체제가 프로세스 작업 요청을 들어온 순서대로 큐에 넣고 CPU가 순서대로 처리함

• 덱

  • 데이터 삽입과 제거를 head과 tail 두 군데서 자유롭게 할 수 있음

  • 덱을 이용하면 스택과 큐를 전부 구현 가능

• 해시테이블

  • 해시와 테이블이 합쳐진 구조로 메모리 낭비를 줄이기 위해 어떤 계산을 하는 함수인 해시함수로 테이블의 인덱스를 새로 만듦

  • 읽기, 삽입, 수정, 삭제 O(1) 성능

    • 장점: 빠른 데이터 읽기, 삽입, 삭제

    • 단점: 공간 효율성이 좋지 않음, 해시함수에 따라 메모리 사용이 달라 좋은 해시함수가 필요함