자료구조의 종류 및 시간 복잡도

프로그래머스 '코딩테스트 광탈 방지 A to Z' 강의 내용을 정리해놓은 포스트입니다.

자료구조 vs 알고리즘

자료구조

• 속도, 공간측면으로 효율적이고 안정적이게 데이터를 처리할 때 사용하는 특정 구조
• 일차원인 컴퓨터 메모리를 현실에 대응하도록 구조화한 것
• 예) stack, queue, graph etc...

알고리즘

• 위 자료구조를 이용하여 로직을 효율적으로 처리할 수 있는 절차나 방법을 공식화한 형태
• 예) binary search, shortest path etc

자료구조의 종료

단순구조

선형구조

• 자료들이 선형으로 나열되어 있는 형태

비선형 구조

• 원소간 다대다 관계, 계층적 또는 망형 구조 - 인간관계, 컴퓨터 폴더 구조 구현하기에 적합

시간복잡도

O(1)이 제일 이상적인 속도이며 뒤로 갈수록 효율성이 떨어진다.
O(1)은 상수 시간, O(n)은 선형 시간으로 불린다.

동일한 로직을 구현하더라도 사용되는 자료구조와 알고리즘에 따라 시간복잡도는 달라질 수 있다.
그렇기 때문에 복잡하더라도 제발 정신차리고 붙잡자