스파르타 코딩클럽(부트캠프) 알고리즘 특강정리

알고리즘이란

어떤 작업을 수행하기 위해 입력을 받아서 원하는 출력을 만들어 내는 과정을 뜻한다.

 

알고리즘의 수행 내용을 의사코드로 작성하기도 한다.

그 알고리즘의 문제를 얼마나 빠르게 해결하는 지 평가하는

시간복잡도 라는 개념도 같이 존재한다.

의사코드(pseudo-code)=의사하다, 실제와 비슷하다, Pseudo: 가짜의,모조
컴퓨터 프로그램이나 알고리즘이 수행해야할 내용을 논리적으로 서술해 놓은 것.

프로그램
알고리즘을 컴퓨터가 이해하고 실행할 수 있는 특정 프로그래밍 언어로 표현한것.
프로그램 = 알고리즘 + 자료 구조

---

자료구조(Data structure)

데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령을 의미한다.

어떤 자료 구조를 선택하느냐에 따라 효율적인 알고리즘 사용이 가능하다.

자료구조의 필요성

개발적 관점

효율적인 데이터관리

데이터의 효율적인 저장과 검색을 가능하게 하여 처리 시간을 줄이고 성능을 향상시킨다.

데이터 조직

데이터를 논리적으로 구성하여 이해하고 접근하기 쉽게 만든다.

데이터 추상화

데이터 저장의 구현 세부정보를 숨기고 프로그래머가 데이터 조작의 논리적 측면에 집중할 수 있도록한다.

재사용성

일반적인 데이터 구조는 여러 응용 프로그램에서 재사용할 수 있어 개발 시간과 노력을 절약한다.

알고리즘 최적화

적절한 데이터 구조의 선택은 데이터를 처리하는 알고리즘 효율성에 상당한 영향을 미친다.

---

자료구조의 형태

 

배열(Array)

출처  https://www.geeksforgeeks.org/implement-arrays-in-different-programming-languages/

---

연결리스트(Likedlist)

각 노드가 다음 순의 노드를 연결한 형태의 자료 구조이다.

출처 : https://www.geeksforgeeks.org/what-is-linked-list/

---

해시 테이블(Hash Table)

해시 함수를 사용한다. 해시 함수는 키를 입력받고, 그 키에 알맞는 인덱스를 알려준다.

이 방법으로 빠르게 키를 인덱스와 매핑시켜준다.

출처 :   https://www.geeksforgeeks.org/implementation-of-hash-table-in-python-using-separate-chaining/

---

그래프(Graph)

각 노드 들이 그물망처럼 간선으로 연결된 자료 구조

출처 :   https://www.geeksforgeeks.org/introduction-to-graphs-data-structure-and-algorithm-tutorials/

---

스택(Stack)

마지막으로 입력한 값이 제일 먼저 출력되는 자료구조이다. LIFO(Last In First Out), FILO(First In Last Out)

데이터를 입력하는 push와 데이터를 출력하는 pop 기능이 있다.

출처 : https://www.geeksforgeeks.org/stack-data-structure/

---

큐(Queue)

제일 먼저 입력한 값이 가장 먼저 출력되는 자료구조이다. FIFO(First In First Out)

데이터를 입력하는 enqueue와 데이터를 출력하 dequeue기능이 있다.

출처 :  https://www.geeksforgeeks.org/introduction-to-queue-data-structure-and-algorithm-tutorials/

---

트리(Tree)

말 그대로 트리 형태로 이루어진 자료구조이다.

각 노드가 간선으로 연결된 노드를 가질 수 있다.

트리의 꼭대기는 root노드이며, 자식을 가지지 않는 노드는 leaf노드이다.

같은 부모를 갖는 노드는 서로 형제관계가 된다.

트리의 노드는 또 다른 작은 형태의 트리인 서브트리를 가질 수 있다.

출처 : https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/

 

 

알고리즘의 필요성

개발적 관점으로 보았을 때

복잡한 문제를 효율적인 시간 계산을 통해 효과적으로 해결

 

문제 풀이의 과정을 더 안전하고, 빠르고, 수행하기 쉽도록 도와준다.

알고리즘 풀이를 코딩 테스트에 이용하는 경우가 많다.

알고리즘 풀이 사이트 또는 대회를 이용하여 자신의 점수를 올려 어필이 가능하다.

---

Big-O표기법(Big-O notation)

알고리즘의 입력 크기가 n이라면

n²에 비례하는 시간이 소요된다는 것을 뜻한다

수치를 단순화해서 경향성을 보기위한 표기법이다.

출처 :  http://devwebcl.blogspot.com/2016/12/big-o-comparison.html

O(1) < O (logn) < O(n) < O(n logn) < O(n2) <O(2n) < O(n!)

O(1)이 가장빠르고 O(n!)이 가장느리다

O(1)은 현실적 불가능한 수치이다.

O(logn)과 O(n logn)의 복잡도가 효율적인 알고리즘이다.

 

https://hs-backend.tistory.com/15

스파르타 코딩클럽(부트캠프) 11장 공간자원과 공간 복잡도