본문 바로가기
카테고리 없음

[코딩테스트] - 자료구조, 시간복잡도

Victor_developer 2024. 7. 7. 15:54

 

자료구조는 데이터를 저장하고 관리하는 방식을 말합니다. 이는 데이터를 체계적으로 저장하여 메모리를 효율적으로 사용하고, 빠르고 안정적으로 데이터를 처리할 수 있도록 도와줍니다.

 

선형 자료구조 (Linear Data Structures)

선형 자료구조는 데이터가 연속적으로 나열된 형태를 가지며, 각 데이터 요소가 순차적으로 연결된 구조를 의미합니다. 데이터 요소들 간의 관계가 1:1입니다.

  1. 배열 (Array)
    • 연속된 메모리 공간에 데이터 저장
    • 고정된 크기
    • 인덱스를 통한 빠른 접근
  2. 동적 배열 (Dynamic Array)
    • 크기가 가변적인 배열
    • 필요 시 크기를 동적으로 조절
    • 추가 및 삭제가 용이
  3. 연결 리스트 (Linked List)
    • 노드가 데이터와 포인터를 포함
    • 크기가 가변적
    • 삽입 및 삭제가 용이
  4. 큐 (Queue)
    • FIFO (First In, First Out) 원칙
    • 삽입은 뒤에서, 삭제는 앞에서 수행
  5. 스택 (Stack)
    • LIFO (Last In, First Out) 원칙
    • 삽입과 삭제가 한쪽 끝에서만 일어남
  6. 해시 테이블 (Hash Table)
    • 키-값 쌍을 저장
    • 해시 함수를 통해 빠른 접근
    • 충돌 관리 기법 필요

비선형 자료구조 (Non-Linear Data Structures)

비선형 자료구조는 데이터 요소들이 계층적 또는 네트워크 형태로 연결된 구조를 의미합니다. 데이터 요소들 간의 관계가 1:다 또는 다:다입니다.

 

  1. 트리 (Tree)
    • 계층적 구조
    • 루트 노드에서 시작하여 자식 노드로 분기
    • 이진 트리, AVL 트리, 이진 탐색 트리 등 다양한 형태
  2. 그래프 (Graph)
    • 노드(정점)와 간선(엣지)으로 구성
    • 방향 그래프와 무방향 그래프 존재
    • 최단 경로 탐색, 네트워크 모델링 등에 사용

자료구조를 배우는 것은 알고리즘을 이해하고 효율적으로 구현하는 데 필수적입니다. 다양한 자료구조의 특성과 장단점을 이해하고, 문제에 적합한 자료구조를 선택할 수 있는 능력은 코딩 테스트뿐만 아니라 실제 소프트웨어 개발에서도 매우 중요합니다.

 

 

알고리즘 (Algorithm)

알고리즘은 문제를 해결하기 위한 정해진 일련의 절차나 방법입니다. 알고리즘은 다양한 문제를 해결하기 위해 자주 사용되며, 그 유형에 따라 패턴화된 방법들이 있습니다.

알고리즘의 정의

  • 문제 해결 방법: 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법
  • 패턴화된 알고리즘: 자주 쓰이는 문제 해결 방법은 패턴화되어 있습니다.

자주 쓰이는 알고리즘 패턴

  1. BFS (Breadth-First Search)
    • 너비 우선 탐색
    • 큐를 사용하여 가까운 노드부터 탐색
    • 최단 경로 찾기 등에 사용
  2. DFS (Depth-First Search)
    • 깊이 우선 탐색
    • 스택을 사용하여 깊이 있는 노드부터 탐색
    • 경로 찾기, 사이클 검출 등에 사용
  3. 이진 탐색 (Binary Search)
    • 정렬된 배열에서 탐색을 수행
    • 절반씩 탐색 범위를 줄여나감
    • O(log n)의 시간 복잡도
  4. 다익스트라 알고리즘 (Dijkstra's Algorithm)
    • 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘
    • 우선순위 큐를 사용하여 구현
    • 네트워크 경로 찾기 등에 사용

 

알고리즘의 다양성

한 문제를 해결할 수 있는 알고리즘은 다양하며, 각 문제에 적합한 알고리즘을 선택하고 평가할 수 있어야 합니다.

알고리즘 선택

  • 문제의 특성 파악: 문제의 특성에 따라 가장 적합한 알고리즘을 선택
    • 예: 짧은 경로를 찾는 문제에서는 BFS나 다익스트라 알고리즘을 선택
  • 시간 및 공간 복잡도 고려: 알고리즘의 효율성을 평가
    • 예: 데이터가 큰 경우 시간 복잡도가 낮은 알고리즘을 선택

알고리즘 평가

  • 시간 복잡도: 알고리즘이 문제를 해결하는 데 걸리는 시간
    • 예: O(n), O(log n), O(n^2) 등
  • 공간 복잡도: 알고리즘이 문제를 해결하는 데 사용하는 메모리 공간
    • 예: O(1), O(n), O(n^2) 등
  • 정확성: 알고리즘이 정확한 결과를 도출하는지 여부
  • 단순성: 알고리즘의 구현이 얼마나 쉬운지 여부
  • 확장성: 알고리즘이 더 큰 문제나 다양한 문제에 얼마나 잘 적용되는지 여부

 

알고리즘 평가 기준

알고리즘을 평가하는 주요 기준은 다음과 같습니다:

  1. 시간 복잡도 (Time Complexity)
    • 알고리즘이 문제를 해결하는 데 걸리는 시간을 나타냅니다.
    • 주로 빅오 표기법(O-notation)을 사용하여 표현합니다.
    • 예: O(1), O(log n), O(n), O(n^2) 등.
  2. 공간 복잡도 (Space Complexity)
    • 알고리즘이 문제를 해결하는 데 사용하는 메모리 공간을 나타냅니다.
    • 주로 빅오 표기법으로 표현합니다.
    • 예: O(1), O(n), O(n^2) 등.
  3. 구현 복잡도 (Implementation Complexity)
    • 알고리즘의 구현이 얼마나 쉬운지를 평가합니다.
    • 코드의 길이, 가독성, 유지보수 용이성 등을 고려합니다.

시간 복잡도의 중요성

  • 코딩 테스트나 실제 소프트웨어 개발에서는 실행 시간을 줄이는 것이 매우 중요합니다.
  • 많은 데이터나 복잡한 연산을 다루는 경우, 시간 복잡도가 낮은 알고리즘을 사용하는 것이 성능 향상에 큰 도움이 됩니다.

시간 복잡도와 공간 복잡도의 Trade-off

  • 시간 복잡도와 공간 복잡도는 보통 상호 간에 trade-off 관계가 있습니다.
  • Trade-off 예시:
    • 실행 시간을 줄이기 위해 더 많은 메모리를 사용하는 경우.
    • 메모리 사용을 줄이기 위해 실행 시간이 늘어나는 경우.

 

코딩 테스트에서의 전략

  1. 시간 복잡도 줄이기
    • 메모리를 사용해서 실행 시간을 줄이는 방법을 고려합니다.
    • 예: 메모이제이션(Memoization), 캐싱(Caching) 기법을 사용하여 중복 계산을 피하는 방법.
  2. 미리 계산된 시간 복잡도 고려
    • 문제 조건에 맞춰 적절한 알고리즘을 선택합니다.
    • 예: 입력 데이터의 크기에 따라 O(n log n) 또는 O(n^2) 알고리즘 중에서 선택.
  3. 구현의 용이성
    • 구현이 복잡하지 않으면서도 성능이 좋은 알고리즘을 선택하는 것이 중요합니다.
    • 코드의 가독성과 유지보수성을 고려하여 구현 복잡도가 낮은 알고리즘을 선택합니다.

 

메모리와 저장소에 대한 이해

데이터를 저장하고 관리하는 두 가지 주요 메모리 유형과 그 작동 방식을 설명하겠습니다.

1. 하드 디스크 (Hard Disk)

  • 역할: 데이터를 영구적으로 저장하는 장치입니다.
  • 특징:
    • 대용량 데이터를 저장할 수 있습니다.
    • 전원이 꺼져도 데이터가 유지됩니다.
    • 읽기/쓰기 속도가 상대적으로 느립니다.
  • 사용 예:
    • 운영체제, 응용 프로그램, 문서 파일 등을 저장.
    • 코드를 작성하고 저장 버튼을 누르면 코드가 하드 디스크에 저장됩니다.

2. 램 메모리 (RAM, Random Access Memory)

  • 역할: 데이터를 일시적으로 저장하여 CPU가 빠르게 접근할 수 있도록 합니다.
  • 특징:
    • 읽기/쓰기 속도가 매우 빠릅니다.
    • 전원이 꺼지면 데이터가 사라집니다.
    • 컴퓨터가 실행 중인 프로그램과 데이터를 저장합니다.
  • 사용 예:
    • 프로그램 실행 시 필요한 데이터를 저장.
    • 코드를 실행하면 해당 코드와 관련 데이터가 램 메모리에 로드되어 CPU가 빠르게 접근할 수 있습니다.

RAM 메모리와 이진수 표현

트랜지스터와 비트

  • RAM 메모리: 전기 신호를 저장할 수 있는 트랜지스터라는 작은 반도체 소자로 이루어져 있습니다.
  • 트랜지스터: 전기가 ON이면 1, OFF면 0을 나타냅니다.
  • 비트 (Bit): 1비트는 두 가지의 상태(0 또는 1)를 표현할 수 있습니다.

비트와 데이터 표현

  • 1비트: 두 가지 상태 (0, 1) 표현 가능.
  • 2비트: 4가지 상태 (00, 01, 10, 11) 표현 가능.
  • 8비트: 256가지 상태 (2의 8승) 표현 가능.
  • 바이트 (Byte): 8비트는 1바이트(Byte)라고 하며, 이는 256가지 상태를 표현할 수 있습니다.

데이터 크기 단위

  1. 비트 (bit): 가장 작은 데이터 단위.
  2. 바이트 (Byte): 8비트 = 1바이트.
  3. 킬로바이트 (KB): 1024바이트 = 1KB.
  4. 메가바이트 (MB): 1024KB = 1MB.
  5. 기가바이트 (GB): 1024MB = 1GB.
  6. 테라바이트 (TB): 1024GB = 1TB.

16진법

  • 16진법: 이진법으로 표현하기 힘든 큰 숫자를 더 쉽게 표현하기 위해 사용됩니다.
  • 16진수: 0~9와 A, B, C, D, E, F로 표현. (A=10, B=11, ..., F=15)

예시: 노트북의 RAM 메모리

  • 8GB RAM:
    • 8GB는 8 × 1024MB = 8192MB.
    • 1MB는 1024KB = 1048576바이트.
    • 따라서, 8GB RAM은 8192 × 1048576바이트 = 8589934592바이트.

메모리 사용 예시

  • 1MB 메모리:
    • 1MB는 1024KB.
    • 1KB는 1024바이트.
    • 1바이트는 8비트.
    • 따라서, 1MB는 1024 × 1024바이트 = 1048576바이트 = 8388608비트.

자바 (Java)의 데이터 타입 크기

  1. byte:
    • 크기: 1 바이트 (8비트)
    • 값 범위: -128 ~ 127
  2. short:
    • 크기: 2 바이트 (16비트)
    • 값 범위: -32,768 ~ 32,767
  3. int:
    • 크기: 4 바이트 (32비트)
    • 값 범위: -2,147,483,648 ~ 2,147,483,647
  4. long:
    • 크기: 8 바이트 (64비트)
    • 값 범위: -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
  5. float:
    • 크기: 4 바이트 (32비트)
    • 값 범위: 1.4E-45 ~ 3.4E+38
  6. double:
    • 크기: 8 바이트 (64비트)
    • 값 범위: 4.9E-324 ~ 1.7E+308

티스토리툴바