~섹션2 유닛 8
+강의 정리와 개인적인 지식, 의견 또한 포함되어 있습니다.
강의의 자세한 내용은 포함하지 않고 있습니다.
[섹션1 - 개요]
자료구조를 사용해야 하는 이유?
더 나은 유지보수! (개인적인 의견으로 가장 중요한 개발 목표라고 생각)
알고리즘
자료구조에 따라 알고리즘 달라짐.
자료구조에 많은 영향!
프로젝트 시작 시 적절한 자료구조 선택, 사용 결정 후
그에 맞는 알고리즘으로 가공.
결국 유지보수를 염두에 둔다면 굉장히 중요한 사항들!
더 좋은 알고리즘이란?
정답은 없다.
프로젝트의 목적에 따라 보통 속도/메모리 중 우선순위를 선택하게 됨
일반적으로 알고리즘은 속도를 성능의 척도로 사용 (시간 복잡도)
→ 코딩테스트
시간 복잡도는 실제 디바이스의 실행 시간이 아닌 코드를 기준으로 실행시간 예측하는 것.
실제 디바이스 측정은 디바이스, 네트워크 등 환경에 따라 차이가 날 수 있다.
성능에 영향을 많이 주는 것 - 반복문!
최선의 경우 Big-Ω
최악의 경우 Big-O
평균의 경우 Big-Θ
주로 Big-O, Big-Θ 표기법 사용
Big-O 표기법
성능을 정확하게는 표시 X, 입력량에 계산량의 증가 척도 표기
O(1), O(logn), O(nlogn), O(n²), O(2ⁿ), O(n!) 등으로 성능 표시
계산에 가장 많은 영향을 미치는 큰 항으로 성능 표시
상수는 큰 의미가 없어 제거.
예) 7n² + 10n의 시간복잡도는 O(7n²)이 아닌 O(n²)으로 표시
[섹션2 - 자료구조]
1. 일반적인 배열 Array
일반적인 배열은 선언과 동시에 크기 할당(메모리 할당) - 정적 메모리
연속된 메모리 공간 할당, 배열의 시작 주소부터 해당 index 만큼 떨어진 주소에서 참조 - 연속적 주소
배열의 인덱스 참조는 길이에 상관없이 한 번에 가져와 O(1)의 좋은 성능을 가짐.
장점
연속적인 주소로 참조 시 O(1)의 성능
단점
초기에 크기 예측이 어려움 - 수정 시 메모리 낭비의 원인
데이터 삽입, 삭제 비효율적 O(n)의 성능 - 유지보수 비효율적
2. 연결리스트 LinkedList
node로 빈 메모리 공간 연결, 동적 크기
장점
삽입, 삭제에 노드 연결만 변경, 쉬운 유지보수
단점
불연속적인 주소로 참조, 삽입, 삭제 모두 O(n)의 성능
+ 개인 메모
강의에서는 JS를 사용하기 때문에, JS는 기본적으로 연결리스트가 없나? 궁금했다.
JS는 LinkedList 자료구조가 없어 직접 구현해야 한다고 한다.
나의 주 언어인 C#과 C++은 LinkedList 자료구조를 모두 사용 가능하다.
C#
List와 LinkedList가 존재하는데,
List는 일반 정적인 Array배열을 동적으로 구현한 것이다.
따라서 LinkedList와 비슷하게 보이지만, 사실은 편하게 수정 가능한 동적 Array에 더 가깝다.
LinkedList는 위에서 배운 node기반 연결리스트이다.
C++
std::vector와 std::list가 존재한다.
std::vector는 C#의 List와 거의 유사하다.
하지만 C++이라는 개발 환경의 특성에 맞게 메모리 관리와 성능 최적화를 신경 써야 한다.
C++의 std::list가 위에서 배운 node기반 연결리스트이다.
3. 스택 Stack
LIFO 구조
프로그램에서 주로 사용
예) 문법검사기 - 스택으로 괄호를 검사하여 문법 에러 체크
4. 큐 Queue
FIFO 구조
운영체제 - CPU의 처리 FIFO 스케줄링
+개인 메모
C#
Stack과 Queue 자료구조가 이미 존재한다.
하지만, 이는 모두 LinkedList가 아닌, List기반, 즉 Array 기반의 자료구조이다.
이를 LinkedList로 구현해 보고, 필요한 상황에 따라 적용해 보면 좋을 것 같다.
C++
std::stack과 std::queue가 존재하지만, container adapters로
내부 container를 std::deque, std::vector로 설정할 수 있다고 한다.
기본적으로 std::deque (덱 - 양방향 큐)를 사용한다.
덱은 다음에서 배울 자료구조이다.
5. 덱 Deque
삽입, 제거를 head와 tail 모두 가능
stack과 queue 모두 구현 가능
+개인 메모
C#에서는 Deque 자료구조가 없어 직접 구현해야 한다!
위의 이미 존재하는 기능들도 직접 node 연결로 구현하며 복습하면 더 기억에 잘 남을 듯하다.
1주차 마무리
이번주는 인턴 프로젝트가 2개가 몰려 휴일에도 자발적 재택근무를 할 만큼 너무 바빴다..
그럼에도 하루에 조금씩이라도 투자해서 1유닛이라도 볼 걸, 후회가 되었다.
앞으로는 출퇴근 시간에라도 조금 투자해서 보도록 노력해야겠다!
이미 알고 있던 내용들도 그림과 예시를 통하여 시각적으로 공부하니 좋다.
단순 암기가 아닌 지식이 녹아드는 느낌이라 강의 신청한 것 후회가 전혀 없다!
인프런 - 감자 강사님 <그림으로 쉽게 배우는 자료구조과 알고리즘 (기본편)>
그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 강의 | 감자 - 인프런
감자 | 이 강의를 통해 선형 자료구조와 알고리즘을 배울 수 있습니다., [사진] 개발자가 꼭 알아야 할 자료구조 & 알고리즘,그림으로 쉽고 재밌게 알려드려요! 한 번 익힌 기본기가 평생의 코드
www.inflearn.com
'개발 스터디 > CS' 카테고리의 다른 글
| [스터디] 인프런 CS 전공지식 스터디 2기_운영체제(1주차) (6) | 2024.10.06 |
|---|