자료구조와 알고리즘
- 어떤 자료구조와 알고리즘을 쓰느냐에 따라 성능이 크게 달라질 수 있다.
Data Structure (자료구조)
: 컴퓨터 내의 데이터들을 효율적으로 저장하고 사용(관리)하는 방법들
- 코드 상에서 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라 구조화필요
→ 어떤 데이터 구조를 사용하느냐에 따라 코드 효율이 달라짐
대표적인 자료구조
: 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등
Array (배열)
: 데이터를 나열하고 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
- 장점: 빠른 접근 가능 (첫 데이터의 위치에서 상대적인 위치로 데이터 접근 가능 (인덱스)
- 단점: 데이터의 추가/삭제가 어려움 (크기가 고정되어있음)
Queue (큐)
: FIFO(First In First Out), 선입선출 자료구조
- Queue(): 선입선출
- LifoQueue(): 스택 구조, 후입선출
- PrioirtyQueue(): 우선순위가 높은 순으로 데이터 출력
→ tuple형식으로 input, 숫자가 작을수록 우선순위가 높다.
- 운영체제에서 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨
Stack (스택)
: LIFO(Last In First Out), 후입선출 자료구조
- 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
- 장점: 데이터 처리 속도가 빠르다
- 단점: 저장공간의 낭비가 발생할 수 있다
(미리 최대 갯수만큼의 저장공간 확보 필요)
Linked List
: 떨어진 곳에 존재하는 데이터를 화살표로 연결해 관리, 노드와 노드가 포인터로 연결된 형태
- 노드: 데이터 저장 단위
노드 = 데이터값 + 포인터
- 포인터: 각 노드 안에서 이전이나 다음 노드와의 연결 정보를 가지고있는 공간
컴퓨터 내부의 프로세스 구조의 함수 동작 방식에 활용
Algorythm (알고리즘)
: 어떤 문제를 풀기 위한 절차/방법
- 어떤 문제에 대해 특정 '입력'을 넣으면 원하는 '출력'을 얻을 수 있도록 만드는 프로그래밍
- 시간 복잡도 / 공간 복잡도가 중요
시간복잡도
: 알고리즘을 위해 필요한 연산의 횟수 (알고리즘 실행 속도)
- 입력의 크기가 커질수록 반복문이 알고리즘의 수행 시간을 지배
공간복잡도
: 알고리즘을 위해 필요한 메모리의 양 (알고리즘이 사용하는 메모리 사이즈)
알고리즘 성능 표기법
Big O(빅-오) 표기법
- 알고리즘 최악의 실행 시간을 표기 (아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미)
- 입력 n에 따라 몇번 실행 되는지 계산
- O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)
잘읽었습니다.
오타있습니다