자료구조와 알고리즘의 개념에 대해
- 자료구조 : 자료구조는 데이터를 조직, 관리 및 저장하는 방식입니다 데이터를 체계적으로 저장하고,
효율적으로 활용하기 위해서 자료구조를 사용합니다
단순구조 / 선형구조 / 비선형구조 / 파일구조 로 나누어 집니다
단순구조: 단순구조는 가장 기본적인 데이터 저장 형태로, 더 복잡한 구조의 기본 단위가 됩니다
// 정수 실수 문자 불리언
선형구조: 선형구조는 데이터가 일직선으로 나열되는 자료구조입니다
// 배열 연결리스트 스택 큐
비선형구조: 비선형구조는 데이터가 계층적 또는 그물 형태로 조직되는 자료구조입니다
//트리 그래프
파일구조: 데이터를 파일시스템에 저장하고 조직하는 방법을 의미합니다
// 순차파일 직접파일 인덱스파일 다단계 인덱스파일
- 알고리즘: 알고리즘은 특정 문제를 해결하기 위한 절차나 방법입니다
- 좋은 알고리즘의 조건
- 입력: 외부에서 제공되는 자료가 0개이상 존재해야한다
- 출력: 최소 1개이상의 결과를 가져야한다
- 명확성: 명확하고 애매함이 없는 명령어로 구성해야한다
- 유한성: 유한한 횟수와 시간을 거쳐 문제를 해결하고 종료되어야한다
- 유효성 : 각명령어들은 실행이 가능한 연산이여야 한다
- 효과성: 모든 연산은 유한한 시간내에서 정확하게 수행할 수 있을 정도로 충분히 단순해야한다
그래프와 트리의 차이점에 대해
- 그래프: 노드와 노드간을 연결하는 간선으로 구성된 자료구조이다 //네트워크형태
- 트리: 트리는 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 자료구조이다
간선의 방향성이 있고 트리는 두개의 노드 사이에 반드시 1개의 경로만을 가지며 사이클이 존재하지 않는다
최소연결트리라고 불리우며 부모-자식 관계가 성립하기에 계층형 모델이라고 불립니다
이진탐색트리에 대해 설명해주세요
이진탐색트리는 노드로 구성된 트리 자료구조로 각 노드는 두개의 자식노드를 가지는데
"왼쪽 자식노드" 는 부모 노드보다 작은 값을 가지고 "오른쪽 자식 노드"는 부모노드 보다
큰 값을 가집니다 이때 모든 원소는 유일한 키를 가집니다
탐색 - 최상위 루트 노드에서 시작, 현재노드의 값을 확인하고 찾고자하는 값이 노드와 같으면 탐색성공입니다
찾고자하는 값이 현재 노드보다 작다면 외쪽 크다면 오른쪽 서브트리로 이동합니다
리프노드에 도달할때까지 값을 찾지못한다면 탐색 실패입니다
삽입- 트리가 비어있다면 최상위에 삽입 합니다 탐색처럼 값이 작다면 왼쪽 아니라면 오른쪽 서브트리로 이동하면서
검색에 실패할때가지 이동하고 그자리에 노드를 삽입합니다 삽입의 시간복잡도는 O(h)입니다
삭제 - 삭제하려는 노드가 리프노드 인 경우 단순 삭제
하나의 자식노드를 가지는 경우 삭제할 노드를 그자식 노드로 대체
두개의 자식노드를 가지는경우 오른쪽서브트리에서 가장 작은 값
또는 왼쪽 서브트리에서 가장 큰 값 으로 대체하고 삭제 합니다
AVL트리에 대해 설명해주세요
이진탐색트리에서 한쪽으로 값이 치우칠때 탐색시간이 길어지는 단점을 보완하기위해
좌우 균형을 유지하는 형태의 트리구조입니다
서브트리의 높이는 항상 최대 1만큼 차이가 납니다 1보다 차이가 커진다면 스스로 균형을 잡습니다(Balance Factor)
특징: 이진 트리의 속성을 가진다/
왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다/
어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 차이를 줄인다 /
AVL 트리는 높이를 logN으로 유지하기 떄문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)이다
레드블랙트리에 대해 설명해주세요
자가균형이진탐색트리의 종류로 이진 탐색 트리의 최악의 경우 시간 복잡도를 O(log n)으로 균형을 유지하는데 사용됩니다
특징 :
- 각 노드는 빨간색 / 검은색으로 칠해 집니다
- 루트 노드는 항상 검은색입니다
- 리프노드 모든 리프노드는 검은색입니다
- 빨간색 노드의 자식은 검은색입니다
- 모든 경로가 루트에서 리프까지의 동일한검은색 노드를 포함한다
스택과 큐에 대해 설명해주세요
스택과 큐 모두 선형 자료구조로 두 구조의 차이점은 스택은 LIFO (Last In, First Out) 구조를 가진 자료구조로,
가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조입니다.
반면, 큐는 FIFO (First In, First Out) 구조를 가지며,
가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 구조입니다
스택은 선입후출 - push / pop 연산을 제공합니다 //입구랑 출구가 같고 항아리처럼 한쪽만 열려있다
큐는 선입선출 - enqueue / dequeue연산을 제공합니다
// 스택2개로 큐만들기 굳이구지구질구질해