자료구조와 알고리즘 - 자료구조와 알고리즘이란, 자료구조의 종류, 시간 복잡도

본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다.

1. 자료구조와 알고리즘이란

• 자료구조와 알고리즘을 올바르게 사용하면 좋은 프로그램을 만들 수 있음

자료구조

• 메모리를 효율적으로 사용하고 안정적으로 데이터를 처리
• 스택, 큐, 그래프, 트리 등
• 특정 상황에서 유용한 자료구조가 있음
• 상황에 맞게 적절하게 선택

알고리즘

• 특정 문제를 효율적이고 빠르게 해결하는 것이 궁극적인 목표
• 정해진 일련의 절차와 방법을 공식화한 형태로 표현
• 이진탐색, 최단거리 탐색, DFS, BFS

2. 자료구조의 종류

• 단순 구조
  • 정수, 실수, 문자열, 논리
• 선형 구조
  • 배열, 연결 리스트, 스택, 큐
• 비선형 구조
  • 트리, 그래프

선형 구조

• 자료들이 선형으로 나열
• 배열, 연결 리스트, 스택, 큐
• 한 원소 뒤에 하나의 원소 만이 존재

비선형 구조

• 계층적 구조, 망형 구조를 표현
• 원소가 여러개 원소와 관계를 가질 수 있음
• 트리, 그래프

3. 시간복잡도

• Big-O notation
  • 성능을 표기하기위한 표기법
  • 시간 복잡도
  • 접근적 표기법
• O(1) < O(logn) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
  • log의 밑은 2
  • 상수시간 < 로그시간 < 선형시간 < 선형로그시간 < 이차시간 < 지수시간 < 팩토리얼 시간
  • 우측으로 갈 수록 점점 느려짐
• 계수법칙
  • n이 무한에 가까워질 수록 상수의 크기는 무의미 -> 상수 생략 가능
• 합의법칙
  • Big-O 끼리는 더해질 수 있음
• 곱의법칙
  • Big-O 끼리는 곱해질 수 있음
• 다항법칙
• 상수항과 가장 큰 항외에는 무시하면 됨

Reference

프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript