Data Structure 정리

검색알고리즘

1. 선형 검색(Linear Search) - 앞부터 하나하나 검색하는 알고리즘 

2. 이진 검색(Binary Search) - Sort시키고 중간을 잘라 검색 (답을찾을때까지 반복)

3. 해시(Hash) - 인덱스를 만들어 Element / Index Number를 이용해 인덱스로 나누는 방법

• 충돌 - 만약 다른값에서 같은 결과가 나왔다면 아래 2가지 방법을 사용
  • 체인법 : 해시값이 같은 원소를 연결 리스트로 관리함
  • 오픈 주소법:빈 버킷을 찾을 때까지 해시를 반복함

스택 vs 큐

스택(Stack)

• LIFO(Last In First Out) - 마지막으로 들어온게 처음으로 나간다.
• 실사용 예 :
  • 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
  • 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
  • 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
  • 후위 표기법 계산
  • 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

큐(Queue)

• FIFO(First In First Out) - 처음으로 들어온게 처음으로 나간다
• 실사용 예 :
  • 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
  • 은행 업무
  • 콜센터 고객 대기시간
  • 프로세스 관리
  • 너비 우선 탐색(BFS, Breadth-First Search) 구현
  • 캐시(Cache) 구현

재귀 알고리즘

• 직접 재귀
  • 내부에서 자신과 똑같은 함수를 호출
  • 예: a()에서 a()를 다시 호출
• 간접 재귀
  • 내부에서 자신과 다른 함수를 호출
  • 예: a()에서 b()를 다시 호출 그리고 b()에서 a()를 다시 호출
• 하향식 분석
  • 가장 위쪽에 위치한 상자의 함수 호출부터 시작하여 계단식으로 자세히 조사해 나가는 분석 방법
• 상향식 분석
  • 하향식과 반대로 아래쪽으로부터 쌓아 올리며 분석하는 방법