[클라우딩 어플리케이션 엔지니어링 TIL] TIL(Today I Learned) - Day11

 

 

 

들어가기전에

자료구조중에서 알고리즘의 기초를 공부하며, 첫수업에 배웠던 것들을 기록하듯 작성하며, 복습한다.

 

 

강의를 보며 나의 주관적인 생각이 들어가 정리한것임으로 반드시 '내가 적은것이 맞다' 라는 것이 아니므로 읽어보시고 이상한부분이 있다면 저에게 알려주시거나 꼭 다른곳도 검색해서 찾아보기를 바랍니다.

 

---

 

 

 

목차

1. 학습 주제

• 자료구조
• 시간 복잡도_Big-O notation; 빅오 표기법
• 연결리스트
• 스택
• 큐

2. 주요 메모 사항 소개

3. 공부하며 어려웠던 내용

 

 

 

학습 주제.1
자료구조

메모리를 효율적으로 사용하며, 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표로

상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다.

Stack, Queue, Graph, Tree

 

알고리즘

특정 문제를 효율적이고 빠르게 해결하는 것이 궁극적인 목표로 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.

Binary Search, Shortest Path

 

 

선형 구조

한 원소 뒤에 하나의 원소 만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 가진다.

선형 구조에 해당되는 자료구조는 배열, 연결 리스트, 스택, 큐 등이 있다.

Array, Linked List, Stack, Queue

 

비선형 구조

원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절하다.

비선형 구조에 해당되는 자료구조는 트리와 그래프 등이 있다.

 

 

학습 주제.2
시간 복잡도_Big-O notation; 빅오 표기법

빠른순 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2") < O(n!) 느린순

 

 

 

4가지 법칙

• 계수 법칙 : n이 무한에 가까울 수록 상수 k의 크기는 의미가 없다
• 합의 법칙 : 빅오끼리는 더해질 수 있다.
• 곱의 법칙 : " 곱해질 수 있다.
• 다항 법칙 : 다항식일 때 표기법

 

표기할 시 기억해야 할 두가지

1. 상수항은 무시

2. 가장 큰 항은 외엔 무시

 

Date 객체를 이용한 성능측정 방법

const start = new Date().getTime();

// ...

const end = new Date().getTime();
console.log(end - start);​

 

Date 객체를 이용한 성능측정 방법 예제

console.log("Start");
const start = new Date().getTime();
const N = 100000000;

let total = 0;
for (let i = 0; i < N; i += 1) {
	total += i;
}

const end = new Date().getTime();
console.log(end - start);
console.log("Finish");
/*
    Start
    1114
    Finish
*/

 

 

 

학습 주제.3
연결 리스트

각 요소를 포인터로 연결하여 관리하는 선형 자료구조

 

특징

• 메모리가 허용하는한 요소를 제한없이 추가가능
• 탐색은 O(n)이 소요
• 요소를 추가하거나 제거할 때 O(1)이 소요
• 단일연결 리스트(Singly Linked List), 이중연결 리스트(Doubly linked List), 원형연결 리스트(Circular Linked List)
• 단일연결 리스트, 이중연결 리스트, 원형연결 리스트

연결 리스트 핵심로직 : 요소 찾기, 요소추가, 요소삭제

 

단일연결 리스트

Head에서 Tail까지 단방향으로 이어지는 연결 리스트

가장 단순한 형태인 연결 리스트

 

이중연결 리스트

양방향으로 이어지는 연결 리스트

단일연결 리스트(Singly linked List)보다 자료구조의 크기가 조금 더 크다.

 

원형연결 리스트

Singly 혹시 Doubly Linked List에서 Tail이 Head로 연결되는 연결 리스트

메모리를 아껴쓸 수 있다. 원형 큐 등을 만들때도 사용도니다.

 

 

학습 주제.4
스택 과 큐

스택

Last In First Out이라는 개념을 가진 선형 자료구조

바닥이 막힌 상자를 생각하면 편하다.

 

 

큐

Fist In First Out 이라는 개념을 가진 선형 자료구조이다.

선형 큐(Linear Queue)와 원형 큐(Circular Queue)가 존재한다.

 

선형 큐 (Linear Queue)

Array로 표현할 수 있다.

 

원형 큐 (Circular Queue)

Front와 Rear가 이어져있는 Queue

Circular Queue는 Linked List로 구현했을 때 이점이 없다.

 

 

---

 

주요 메모 사항 소개

자료구조

선형 구조, 비선형 구조, Stack, Queue, Graph, Tree

Big-O notation

계수, 합, 곱, 다항 법칙

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2") < O(n!)

연결리스트

선형 자료구조 | 단일연결, 이중연결, 양방향연결

 

공부하면서 어려웠던 내용
자료구조와 알고리즘을 이용한 실습풀이

이론은 착착 기록하고 잘 쓰고 그랬던거같은데, 실습으로 풀어보니 실전단계에서 제대로 배우지 못했음을 느끼고는 반복숙달 및 자주 사용해서 문제해결능력을 길러서 익숙해지게끔 하는게 크다 생각했다...