코딩테스트 - 패스트캠퍼스 챌린지 04일차

수강한 강의
Chapter 06 자료구조 (스택)
- 꼭 알아둬야 할 자료 구조: 스택 (Stack)
Chapter 07 자료구조 (링크드 리스트)
- 은근히 어려운 자료 구조: 링크드 리스트
- 다양한 링크드 리스트
Chapter 08 알고리즘 복잡도 표현 기법
- 알고리즘 복잡도 표현 기법 익히기

학습 후기
1. Stack 스택
누군가 예전에 스택을 설명하길 급식실에서 다 먹은 식판을 쌓아 두는 것과 같다고 하였다. 먼저 먹고 나간 사람의 식판이 제일 밑에 있고 설거지를 위해서는 마지막에 쌓인 식판(제일 위)부터 식판을 꺼내기 때문이라나.. 무튼 그렇다고 한다.
Last In, First Out or First In, Last Out
대표적인 스택 활용으로 컴퓨터 내부 프로세스 구조의 함수 동작 방식이 있다.
- 주요 기능
push(): 데이터 넣기
pop(): 데이터 꺼내기
장점: 구조가 단순, 구현이 쉬움
단점: 일반적으로는 데이터 개수를 미리 정해야 함 그에 따른 저장 공간 낭비
프로그래밍 연습: ArrayList로 Stack 구현 > Github

GitHub - insu-choi/codingtest: fastcampus codingtest lecture practice

2. Linked List 링크드 리스트
연결 리스트, 배열과 다르게 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 구조
- 기본 용어
Node(노드): 데이터 저장 단위로 데이터 값과 포인터로 구성
Pointer(포인터): 각 노드 안에서 이전 노드나 다음 노드의 연결 정보를 가지고 있음.

public class Node<T> {
    T data;
    Node<T> next;
    public Node(T data) {
        this.data = data;
    }
}

장점: 미리 데이터 공간 할당하지 않아도 됨
단점: 연결 정보를 찾는데 시간이 걸림, 저장공간 효율이 높지 않음, 중간 데이터 추가 삭제 시 연결 정보 수정 필요

이중 연결 리스트
단일 연결 리스트와 다르게 prev, next 연결 둘 다 가짐

프로그래밍 연습
단일 연결 리스트 구현 > Github

GitHub - insu-choi/codingtest: fastcampus codingtest lecture practice

단일 연결 리스트 구현 > Github

GitHub - insu-choi/codingtest: fastcampus codingtest lecture practice

3. 알고리즘 복잡도 표현 방법
3-1. 시간 복잡도
알고리즘 실행 속도
빅오 표기법: O(N) - 최악의 실행 시간
오메가 표기법: Ω(N) - 최상의 실행 시간
세타 표기법: Θ(N) - 평균의 실행 시간
알고리즘 복잡도는 빅오 표기법(최악의 실행시간)을 기준으로 정한다.
아무리 최악의 상황이라도 이 정도의 성능은 보장한다는 의미
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

3-2. 공간 복잡도
알고리즘이 사용하는 메모리 크기

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.