3.

1. 자료구조&알고리즘

• 자료구조+알고리즘 = 프로그램

• 자료구조
• 메모리, 속도, 안정성 쪽으로 상황에 따라 유용한 특정 구조
• ex. 스택, 큐, 그래프, 트리

• 알고리즘
• 일련의 절차와 방법을 공식화한 형태
• ex. 이진, 최단 탐색

2. 자료구조와 알고리즘이 중요한 이유

• 자료구조, 알고리즘을 공부해야 함

• 문제 해결 능력! == 일머리
• 논리적 사고 : 현상을 추론 후 구조화 하여 해답을 찾는 능력
• 전산화 능력 : 현실 -> 컴퓨터로 구현
• 엣지 케이스 탐색 : 예외사항 찾기

• 업무상 발생하는 예외사항에 대응 할 수 있음

3. 자료구조의 종류

• 자료구조의 목적 : 전산화를 위한 것임

• 자료구조의 구분
• 단순구조
• 정수, 실수, 문자열, 논리
• 선형구조
• 한 원소 뒤에 하나의 원소만 존재함
• 배열, 연결리스트, 스택, 큐
• 비선형구조
• 원소간 다대다 관계
• 계층형, 망형
• 트리, 그래프

• 자료구조에 좋고 나쁨은 없다. 특정 상황에 따라 적절한 자료구조를 선택해야한다.

4. 시간 복잡도

• 프로그램의 성능을 정확히 하는 것은 불가능
• 입력크기, 하드웨어/운영체제 성능 등에 따라 달라짐
• 이에 대응하기 위해 Big-O 표기법을 사용함

• 시간 복잡도(Big-O)의 크기
• ... < O(n^2) < O(2^n) < O(n!)
• 우리네 코테에서 O(n^3) 이상의 시간 복잡도는 없다고 보면 됨

• Big-O 표기법의 특징
1. 합/곱의 법칙 : Big-O 끼리는 합/곱할 수 있다.
2. 계수법칙 : n이 무한으로 갈수록 n의 계수는 의미가 없다.
• but, k가 클수록 "실제 "성능에는 영향을 미칠 수 있다.
3. 다항법칙 : 다항식처럼 제일 높은 계수를 채택한다.

• 점근적 표기법으로 인해 계수와 상수는 복잡도에 영향을 주지 않는다.

• JS에서 성능을 측정하는 방법
• Date 객체를 이용해서 연산후 Date - 연산전 Date로 경과된 시간을 측정한다.

5. 배열

5.1. 배열의 특징

• but, 스크립트 언어(JS 등)는 동적으로 크기가 증감 됨

1. 요소에 접근은 idx로 => O(1)

2. 삭제시 공백을 채우거나, 원소 사이에 추가를 하려면 뒤의 원소들을 한칸씩 이동해야 한다. => O(n)
• 추가/삭제 반복이 많음 -> 배열 적합 x
• 탐색이 많음 -> 배열 적합 o

5.2. JS의 배열

• 생성
1. []
2. fill
3. from

• 추가
• push : O(1)

• splice
• 추가 : (idx,0,값) => O(n)
• 삭제 : (idx,1) => O(n)

• 특이점
• 배열은 해쉬/맵과 유사 => 숫자 외의 자료형이 key가 될 수 있음 (because 배열의 자료형==객체)
• length가 내부적으로 관리됨 => key가 숫자 외의 자료형인 원소는 length에 영향 x

6. 연결 리스트

• 각 요소를 포인터로 연결, 관리

• 노드 = 데이터+포인터

• 요소를 제한 없이 추가 가능 (JS는 배열도 그럼 ㅇㅇ)

• 탐색 : O(n), (탐색 제외한)추가/제거 : O(1)

• 요소(노드)가 메모리의 곳곳에 퍼져있어서 포인터로 관리 (cf. 배열 : 순차적으로 존재)

• 유형
• singly : 단방향
• 찾기 : 순차적으로 확인
• 추가 : (이전 노드만 가리키고 있다고 가정) 새 노드의 다음 등록 -> 이전 노드의 다음 수정
• 삭제 : (이전 노드만 가리키고 있다고 가정) 이전 노드의 다음 수정 -> 삭제 노드 ㅂㅇ (garbage collector가 알아서 노드 삭제)
• 추가/삭제 시 이전/다음의 순서 변경 불가능
• doubly : 양방향
• 추가 : (이전 노드만 가리키고 있다고 가정)현재 노드의 이전/다음 등록 -> 다음 노드의 이전 수정 -> 이전노드의 다음 수정
• 삭제 : 이전노드의 다음 수정 -> 다음 노드의 이전 수정 -> 삭제할 노드 ㅂㅇ
• 이전/다음의 순서를 바꿀 수 있음
• circular
• 순회하는 연결리스트
• tail이 head로 연결됨
• 메모리를 아낄 수 있음
• 원형 큐에 사용됨

• JS로 Singly, Doubly, Circular Linked List 구현해보기

7. 스택

• LIFO

• ex) 스택 메모리 : 함수 안의 지역변수, 매개변수가 저장되는 메모리 영역
• 함수 호출 시 (지역변수, 반환 주소 값, 매개변수) 세트가 스택에 push되고 함수가 끝나면 pop된다.

• 구현
• 배열로 구현
• js에서 사용. push/pop
• 연결리스트로 구현
• 언제나 유동적이므로 배열이 유동적이지 않은 C,Java에서 사용하는 방법
• head를 top으로 둔다