1. 자료구조와 알고리즘
자료구조 (data structure)
자료(※)를 효율적으로 관리하는 방법, 방법론.
※ 자료란 즉 데이터를 말함. 컴퓨터로 다룰 수 있는 모든 것들. 변수, 상수, 파일 etc
꼬리 물기, stack, 트리 구조...etc
알고리즘 (algorithm)
효율적으로 연산하는 방법. 생각의 순서
*
자료구조와 알고리즘을 고려한 코드란
성능(속도), 용량, 비용을 고려한 코드!!
2. 시간 복잡도와 공간 복잡도
시간 복잡도(time complexity)
수행 시간에 대한 척도
개념
" 100개의 통조림에 맛있는 통조림 하나가 섞여있다. 맛있는 통조림을 찾아라! "
라는 질문에 대해
-
최선의 경우 : 1번만에 찾았어요!
-> 빅 오메가 표기법 (Big-Ω) -
보통의 경우 : 50번만에 찾았어요
-> 빅 세타 표기법 (Big-θ) -
최악의 경우 : 100번만에 찾았어요...
-> 빅 오 표기법 (Big-O)
알고리즘의 성능은 시간 복잡도로 설명하는데,
이를 표기하는 방법으로 빅 오 표기법 (Big-O) 이 많이 사용된다!
고려해야 할 것
for문의 중첩을 고려할 것!
for문이 1개일 경우 O(n) 만큼의 시간 복잡도가 발생한다. 2개일 경우 O(n^2) 3개일 경우 O(n^3)...
for문을 최소한으로 굴려서 시간 복잡도를 줄일 수 있도록 하자!
공간 복잡도(space complexity)
메모리 사용량의 척도
시간 복잡도와 같이 빅 오 표기법 (Big-O) 을 많이 사용한다.
*
요즘은 메모리 기술의 발달로 시간 복잡도의 중요성이 증대했다고 하니, 시간 복잡도를 중점적으로 고려하며 공간 복잡도도 확인하기!
3. 배열과 연결 리스트
배열
기능
- 조회 : O(1)의 조회 시간을 가진다. 하나만 뽑아내기 때문!
- 삽입 & 삭제 : 만약 배열 맨 끝에서 추가를 하거나 삭제를 한다면 O(1).
- 정렬 : 정렬 알고리즘에 따라 시간 복잡도가 달라진다.
- 검색 : 첫 원소부터 끝 원소까지 훑기 때문에 O(n). 혹시나 정렬 되어있는 배열이라면 O(log n)도 가능하다 !
특징
- 삭제를 하더라도 그 자리에 흔적이 남아있다.
연결 리스트 (linked list)
데이터가 꼬리에 꼬리를 무는 느낌. 화물 열차를 생각하자!
장점
- 유동적으로 데이터를 떼었다 붙였다 할 때 유리.
- 원소의 삽입 & 삭제가 빠르다. (그러나 조회는 처음부터 끝까지 훑어야 하기 때문에 비효율적. O(n))
노드(node)
데이터가 저장되는 칸을 일컫는다.
맨 앞의 칸은 HEAD, 마지막 칸은 TAIL.
포인터(pointer)
현재 노드가 가리키는 다음 칸을 말한다.
