250122 - 데이터 구조와 알고리즘

답변에 포함해야 할 키워드

• 스택(Stack), 큐(Queue): 선입선출/후입선출 원칙
• 해시맵(HashMap): 키-값 쌍으로 데이터를 저장하는 구조
• 트리(Tree), 그래프(Graph): 계층적 데이터 구조와 네트워크 데이터 구조
• 시간 복잡도(Big-O): 알고리즘의 효율성 측정
• 정렬 알고리즘: 퀵 정렬, 병합 정렬 등의 시간 복잡도 비교

1. Object의 특성에 따라 사용할 수 있는 데이터 구조에는 어떤 것이 있는지 설명해주세요.
2. 스택(Stack)과 큐(Queue)의 차이점과 실제로 사용되는 사례를 설명해주세요
3. 연결 리스트(Linked List)의 구조와 사용 사례를 설명해주세요
4. 해시맵(HashMap)과 트리(Tree)의 차이점은 무엇이며, 각각 언제 사용하면 좋을지 설명해주세요
5. 트리(Tree)와 그래프(Graph)의 차이점을 설명하고, 각각의 장단점을 이야기해주세요

1. Object와 데이터 구조

Object의 특성에 따라 사용할 수 있는 데이터 구조에는 어떤 것이 있는지 설명해주세요.

Object

• 프로그래밍에서 상태(데이터)와 행동(메서드)을 캡슐화하는 기본 단위
• 객체는 클래스의 인스턴스로 속성과 메서드를 가질 수 있음
• 캡슐화, 추상화, 상속, 다형성

Object의 특성

1. 캡슐화(Encapsulation) : 데이터를 객체 내부에 숨기고, 데이터에 접근하기 위해 메서드 제공
2. 추상화(Abstraction) : 객체의 내부 동작을 숨기고 필요한 기능만 외부에 노출
3. 상속(Inheritance) : 기존 클래스의 속성과 메서드를 상속받아 새로운 클래스 정의
4. 다형성(Polymorphism) : 동일한 인터페이스나 상속 구조에서 서로 다른 클래스들이 동일한 메서드 호출에 대해 서로 다른 동작을 함

새로운 자료 타입 추가에 대한 유연성이 필요할때는 객체, 새로운 동작에 대한 유연성이 필요하면 자료구조

Object의 특성과 적합한 데이터 구조

1. 캡슐화
   • 클래스(class) : 데이터와 메서드를 하나로 묶어 관리, 접근제한자를 사용해 내부 데이터의 무분별한 접근 방지
   • 구조체(struct) : 값 타입의 데이터 캡슐화에 사용, 간단한 데이터 모델링에 적합
2. 추상화
   • 인터페이스(interface) : 객체의 동작을 정의하고, 구현 세부사항을 감춤
   • 추상클래스(Abstract class) : 공통 속성과 메서드를 정의하고, 일부 구현은 서브클래스에서 처리하도록 위임
3. 상속
   • 클래스 계층 구조 : 부모 클래스와 자식 클래스 관계를 통해 재사용성과 확장성을 높임
4. 다형성
   • 인터페이와 클래스 계층 구조 : 인터페이스를 구현하거나 상속을 통해 메서드 오버라이딩을 활용

Object의 특성에 따라 사용할 수 있는 데이터 구조에는 어떤 것이 있는지 설명해주세요.

• Object의 특성에 따라 사용할 수 있는 데이터구조는 4가지 주요 특성인 캡슐화, 추상화, 상속, 다형성에 따라 구분할 수 있습니다.
• 캡슐화는 데이터를 객체 내부에 숨겨 외부로부터 데이터를 보호하는 특성입니다. 이 특성을 반영하기 위해 클래스와 구조체를 사용하고 접근제한자를 통해 내부 데이터에 대한 접근을 제어할 수 있습니다. (사용자의 정보를 다루는 User클래스는 name과 같은 데이터를 캡슐화하고 getter, setter를 통해 데이터에 접근할 수 있게 설계함)
• 추상화는 객체의 내부 동작을 숨기고 필요한 기능만 외부에 노출하는 특성입니다. 이를 구현하기 위해 추상클래스나 인터페이스를 활용할 수 있습니다. (Shape라는 추상클래스에서 draw()라는 메서드를 정의하고 이를 상속받은 Circle, Rectangle클래스가 각각 다른 방식으로 구현함)
• 상속은 기존 클래스의 속성과 메서드를 재사용하거나 확장하는 방식으로 클래스간 계층 구조를 형성하여 부모-자식 관계를 통해 재사용성을 극대화하여 구현할 수 있습니다.
• 다형성은 동일한 메서드 호출이 객체에 따라 다른 방식으로 동작하는 특성으로 이를 구현하기 위해 클래스 계층 구조와 인터페이스를 활용할 수 있습니다.

2. 스택과 큐

스택(Stack)과 큐(Queue)의 차이점과 실제로 사용되는 사례를 설명해주세요

스택(stack)

• 후입선출(Last In First Out, LIFO) 방식으로 동작하는 데이터 구조
• 가장 마지막에 추가된 데이터가 가장 먼저 제거됨
• 장점 : 구조가 단순하고 구현이 쉬움
• 단점 : 데이터의 순서 변경 불가, 중간 데이터에 직접 접근 불가
• 마지막에 추가된 데이터를 먼저 처리할 때
• 사용 사례 : 구조적 문제 해결
  • 함수 호출 스택 : 함수가 호출될 때 스택에 저장, 끝나면 스택에서 제거
  • Undo/Redo : 텍스트 편집기나 이미지 편집 프로그램에서 이전 작업 추적
  • 웹 브라우저 뒤로가기/앞으로 가기 : 방문 페이지 URL을 스택에 저장

큐(queue)

• 선입선출(First In First Out, FIFO) 방식으로 동작하는 데이터 구조
• 가장 먼저 추가된 데이터가 가장 먼저 제거됨
• 장점 : 데이터 처리 순서 유지 가능
• 단점 : 데이터 순서 변경 불가, 중간 데이터에 직접 접근 불가
• 먼저 추가된 데이터를 먼저 처리할 때
• 사용 사례 : 데이터 흐름 관리, 공정한 작업 관리
  • 작업 스케줄링 : 운영체제의 프로세스 스케줄러의 작업을 처리할 때 사용
  • 네트워크 패킷 처리 : 네트워크 장비가 들어오는 데이터 패킷을 처리하는 순서 관리
  • 프린터 대기열 : 프린터가 순서대로 작업을 처리할 수 있도록 대기열에 저장

3. 연결리스트

연결 리스트(Linked List)의 구조와 사용 사례를 설명해주세요

연결리스트(Linked List)

• 노드라고 불리는 요소들이 포인터(다음 노드 주소)를 통해 서로 연결된 형태의 자료구조
• 데이터가 메모리에 연속적으로 저장되지 않아도 작동
• 유연한 메모리 사용과 삽입/삭제 작업에서 효율성 제공

연결리스트 종류

• 단일 연결 리스트 (다음 노드 주소 포함)
• 이중 연결 리스트 (이전 노드와 다음 노드 주소 포함)
• 원형 연결 리스트 (마지막노드가 첫번째 노드를 가리킴)

장점

1. 동적 메모리 사용 : 고정 크기가 아닌 필요에 따라 메모리를 동적으로 할당 및 해제
2. 크기 제한 없음
3. 삽입/삭제가 빠름 : 특정 위치에 삽입하거나 삭제할 때 원소 이동 없이 포인터만 수정하면 됨 O(1)

단점

1. 탐색 성능 : 특정 데이터 검색 시 처음부터 순차적으로 탐색해야 함 O(n)

실제 사용 사례

1. 동적 데이터 관리 : 데이터의 크기가 유동적인 경우
2. CPU 프로세스 스케줄링 : 원형 연결 리스트
3. Undo/Redo 기능 구현
4. 스택이나 큐 구현

구조

• 노드(Node) : 연결리스트에서 기본적인 저장 단위
  • 데이터 : 노드가 저장할 실제 값
  • 포인터 : 다음 노드를 가리키는 포인터
• 헤드 : 시작점을 가리키는 포인터

4. 해시맵 ,트리

해시맵(HashMap)과 트리(Tree)의 차이점은 무엇이며, 각각 언제 사용하면 좋을지 설명해주세요

해시맵(HashMap)

• 키와 값의 쌍을 저장하는 자료구조
• 데이터를 저장할 때 해시 함수를 사용해 키를 해시값으로 변환하고 이 값을 기반으로 데이터를 배열의 인덱스 위치에 저장
• 키를 통해 빠르게 접근 가능
• 배열, 연결리스트, 트리
• 장점 : 데이터 조회가 빠름, 키를 통해 직접적인 접근 가능
• 단점 : 서로 다른 키가 동일한 해시값을 가질 경우 충돌 발생, 메모리 오버헤드 발생, 정렬 불가
• 빠른 검색이 필요한 경우, 키-값을 저장하고 빠르게 접근해야 하는 상황에서 많이 사용

트리(Tree)

• 계층적 구조를 가진 자료구조
• 노드와 간선으로 구성
• 각 노드는 부모-자식 관계 형성
• 이진 트리, 이진 탐색 트리, 힙
• 장점 : 계층 구조 표현할때 매우 적합, 이진탐색 트리와 같은 구조에서는 정렬된 데이터 관리가 가능
• 단점 : 각 노드마다 자식 노드의 주소를 저장해야 하므로 메모리 오버헤드 발생, 복잡한 구현

사용 사례

• 해시맵 : 빠른 조회가 필요할 때, 정렬이 필요 없을때, 중복 제거 / 캐시 시스템
• 트리 : 정렬된 데이터 관리, 계층적 데이터 관리

해시맵(HashMap)과 트리(Tree)의 차이점은 무엇이며, 각각 언제 사용하면 좋을지 설명해주세요

해시맵과 트리는 구조에서 차이가 있습니다.

• 해시맵은 키와 값의 쌍을 저장하는 자료구조로 키를 통해 데이터에 빠르게 접근할 수 있어 데이터 조회가 빠릅니다. 정렬된 순서를 저장하지 않으므로 순서가 중요하지 않고 빠른 삽입/삭제와 검색이 필요한 경우에 자주 사용됩니다.
• 트리는 계층적 구조를 가진 자료구조로 계층 구조를 표현할 때 사용됩니다. 이진탐색 트리와 같은 구조에서는 정렬된 데이터 관리가 가능하기 때문에 정렬된 데이터를 관리하거나 계층적 데이터를 관리할 때 사용됩니다.

5. 트리, 그래프

해시맵(HashMap)과 트리(Tree)의 차이점은 무엇이며, 각각 언제 사용하면 좋을지 설명해주세요

그래프(Graph)

• 노드와 간선으로 구성된 자료구조
• 트리와 달리 비계층적이고 순환이 있을 수 있음
• 방향그래프와 비방향 그래프로 나뉨
• 방향성을 가질 수 있음(방향이 없는 간선도 존재)
• 순환이 있을 수 있음
• 비연결성일수도 있고, 연결성일수도 있음
• 방향 그래프, 비방향그래프, 가중그래프, 비가중그래프
• 장점 : 트리처럼 계층적이지 않아 유연함, 비 연속적인 데이터 표현 가능
• 단점 : 탐색이 복잡함, 간선이 많은 경우 많은 메모리 사용

사용사례

• 트리 : 계층적 데이터를 다룰 때(디렉터리 구조, 조직도), 효율적인 탐색이 필요할 때
• 그래프 : 복잡한 관계를 표현할 때(네트워크), 경로 탐색이 필요할 때

---