index.md

✅ 자료구조란 무엇인가요?

• 자료구조의 정의와 중요성: 자료구조는 데이터를 효율적으로 저장하고 관리하기 위한 방법이나 형식입니다. 자료구조를 사용하면 데이터의 접근, 수정, 삭제 등을 더 효율적으로 수행할 수 있습니다. 알고리즘과 함께 사용되며, 효율적인 데이터 처리를 통해 프로그램의 성능을 개선하는 데 중요합니다.

💡 자료구조 종류

선형 구조	비선형 구조
리스트	트리
스택	그래프
큐
덱

• 선형 구조: 데이터가 선형적으로 연결되어 있는 구조로, 각 요소가 하나의 이전 요소와 하나의 다음 요소를 가집니다.
• 비선형 구조: 데이터가 비선형적으로 연결되어 있는 구조로, 각 요소가 여러 개의 이전 요소와 다음 요소를 가질 수 있습니다.

✅ 배열과 링크드 리스트의 차이점

• 배열: 고정된 크기의 연속된 메모리 공간에 데이터를 저장합니다. 각 요소에 인덱스를 통해 직접 접근할 수 있어 빠른 검색이 가능합니다.

  • 장점:
    • 빠른 접근 속도(O(1)).
    • 메모리 사용이 연속적이어서 캐시 효율성이 높음.
  • 단점:
    • 크기를 변경할 수 없음.
    • 중간에 요소를 삽입/삭제할 경우 전체 요소를 이동해야 하므로 비효율적(O(n)).

• 링크드 리스트: 각 요소가 노드로 구성되어 있으며, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다.

  • 장점:
    • 크기가 가변적이며, 동적으로 메모리를 할당할 수 있음.
    • 삽입과 삭제가 용이함(O(1)).
  • 단점:
    • 요소에 직접 접근할 수 없어 탐색 속도가 느림(O(n)).
    • 추가적인 메모리 오버헤드가 발생함.

✅ 스택과 큐의 차이점

• 스택: LIFO(Last In First Out) 방식으로, 마지막에 들어온 요소가 가장 먼저 나가는 구조입니다.

  • 사용 사례: 함수 호출 시 사용되는 재귀 호출, 웹 브라우저의 뒤로 가기 기능.

• 큐: FIFO(First In First Out) 방식으로, 먼저 들어온 요소가 먼저 나가는 구조입니다.

  • 사용 사례: 프린터 작업 관리, 프로세스 스케줄링.

✅ 해시 테이블은 어떻게 작동하나요?

• 해시 함수: 입력 데이터를 해시값으로 변환하여 배열의 인덱스에 매핑합니다. 이 매핑을 통해 빠른 데이터 접근을 가능하게 합니다.

• 충돌 해결 방법:

  • 체이닝: 동일한 해시값을 갖는 데이터를 연결 리스트로 저장.
  • 오픈 어드레싱: 해시 충돌이 발생하면 다음 빈 인덱스를 찾아 데이터를 저장.

✅ 트리 자료구조의 종류

• 이진 트리: 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조입니다.
• 이진 탐색 트리: 이진 트리의 한 종류로, 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가집니다.
• AVL 트리: 자기 균형 이진 탐색 트리로, 각 노드의 자식 트리 높이 차이가 1 이하인 트리입니다.

✅ 그래프의 기본 개념과 표현 방법

• 그래프: 노드(정점)와 노드를 연결하는 간선으로 구성된 구조입니다.

• 표현 방법:

  • 인접 리스트: 각 노드에 연결된 노드들을 리스트로 표현. 메모리 효율적이고 느슨한 연결에 유리함.
  • 인접 행렬: 정점 간의 연결을 행렬로 표현. 메모리 사용이 많지만, 두 정점의 연결 여부를 O(1)로 확인 가능함.

✅ DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)의 차이점

• DFS: 한 방향으로 가능한 깊게 탐색한 후, 더 이상 진행할 수 없으면 마지막 분기로 돌아가는 방식.

  • 사용 사례: 미로 찾기, 게임에서의 경로 탐색.

• BFS: 시작 정점에서 인접한 모든 정점을 탐색한 후, 그 다음 깊이로 넘어가는 방식.

  • 사용 사례: 최단 경로 탐색, 소셜 네트워크에서의 친구 추천.

✅ 자료구조를 선택할 때 고려해야 할 요소

• 시간 복잡도: 특정 작업(삽입, 삭제, 검색 등)에 걸리는 시간.
• 공간 복잡도: 자료구조가 사용하는 메모리 양.
• 데이터의 특성: 데이터의 양, 형태, 변동성 등을 고려하여 선택.

✅ 정렬 알고리즘에 대해 설명해보세요.

• 버블 정렬: 인접한 요소를 비교하여 정렬. 단순하지만 비효율적(O(n^2)).
• 선택 정렬: 최소값을 찾아 맨 앞에 두는 방식. 비효율적(O(n^2)).
• 병합 정렬: 분할 정복 방식으로, 배열을 반으로 나눈 후 정렬하고 병합. O(n log n) 시간 복잡도.
• 퀵 정렬: 피벗을 기준으로 데이터를 나누어 정렬. 평균적으로 O(n log n)지만 최악의 경우 O(n^2).

✅ 자료구조와 알고리즘의 관계

• 자료구조: 데이터를 저장하고 관리하는 방식.
• 알고리즘: 데이터를 처리하고 조작하는 방법.

✅ 그래프와 트리의 차이

특성	그래프	트리
정의	정점과 간선으로 이루어진 데이터 구조	특수한 형태의 그래프
사이클	사이클이 존재할 수 있음	사이클이 없음
연결성	모든 정점이 연결되지 않을 수 있음	모든 정점이 연결됨 (연결 그래프)
루트	없음	하나의 루트 노드가 존재
자식 노드	노드 간의 관계가 정해지지 않음	각 노드는 최대 하나의 부모 노드와 여러 자식 노드를 가짐
깊이 우선 탐색/너비 우선 탐색	가능	가능
데이터 구조의 활용	다양한 문제 해결에 사용	계층적 관계 표현에 사용