많은 자료구조, 알고리즘에 대해 배우는 이유?
특정 자료구조는 삽입/삭제가 빠르고
특정 자료구조는 조회가 빠르다.
경우에 따라 다양한 자료구조와 알고리즘을 사용해야 한다.
어레이와 링크드리스트
*코딩에서 변수를 옮길 때 한번에 하나씩 옮길 수 있다.
배열(Array)
배열은 크기가 정해진 데이터 공간이고, 한 번 정해지면 바꿀 수 없다.
→원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조
→O(N)의 시간 복잡도를 가진다.
→순차적으로 데이터를 저장
링크드 리스트(Linked list)
리스트는 크기가 정해지지 않은 데이터 공간이다. 연결 고리로 이어주면, 자쥬자래로 늘어날 수 있다.
→리스트는 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 한다.
→연결 고리를 포인터라 부르고, 각 화물 칸을 노드라고 한다. O(N)의 시간 복잡도를 가진다.
→리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 된다.
1) LinkedList는 self.head에 시작하는 노드를 저장한다.
2) 다음 노드를 보기 위해서는 각 노드의 next를 조회해서 찾아가야 한다.
정적배열 VS 동적배열
정적배열 (Static array)
일반적으로 배열이라고 하면 정적배열을 의미하는 거라고 생각하면 된다.
동적배열 (Dynamic array)
정적배열의 데이터 삭제와 추가를 가능하게 하는 방법은 하나 있다.
바로 현재의 배열의 길이보다 1이 큰 새로운 배열을 만들고 이미 있던 값들과 새로 추가된 값들을 새 배열에 복사하는 것이다.
그리고 이 아이디어를 통해 만들어진 것이 바로 동적배열이다.
클래스는 분류, 집합, 같은 속성과 기능을 가진 객체를 총칭하는 개념
-클래스를 이용하면 같은 속성과 기능을 가진 객체들을 묶어서 정의할 수 있다.
클래스에는 생성자(Constructor)라는 게 있는데 객체를 생성할 때 데이터를 넣어주거나, 내부적으로 원하는 행동을 실행하게 할 수 있다.
이진 탐색(Binary Search)
탐색할 데이터를 정확히 반으로 나누어 한쪽에 데이터가 없다면 한쪽을 버리면서 탐색하는 방법입니다.
단, 이진 탐색은 데이터가 미리 정렬되어 있어야지 사용할 수 있습니다.
시간 복잡도: 로그N만큼 걸린다. 연산량이 반ㄴ으로 나눠진다 싶으면 로그N이라고 봐도 무방하다.
*이진 탐색을 이용하기 위해서는 일정한 규칙으로 정렬되어 있는 데이터일떄만 이진 탐색이 가능하다.
순차 탐색(Sequential Search)
데이터가 담겨있는 리스트를 앞에서부터 하나씩 살펴보아서 원하는 데이터를 찾는 방법입니다.
재귀란?
재귀(Recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻함
→재귀 함수는 바로 자기 자신을 호출하는 함수!
재귀 함수를 사용하는 이유?
재귀 함수를 이용해서 간결하고 효율성 있는 코드를 작성할 수 있기 떄문
재귀 함수를 사용할 때는 끝나는 지점, 빠져나가는 지점을 설정해줘야 한다.
