1. 알고리즘 2주차(linked list)
1) 어레이(array)란?
크기가 정해진 데이터의 공간(한번 정해지면 바꿀 수 없음)
- 접근 방식 : 각 원소에 즉시 접근할 수 있다. 이때 원소의 순서는 0부터 시작하고 이를 인덱스라고 부른다. 이 때 즉시 접근할 수 있다는 말은 상수시간 내(O(1))에 접근할 수 있다는 뜻이다.
- 삽입/삭제 방식 : 원소를 중간에 삽입/삭제하기 위해서는 모든 원소를 다 옮겨야 한다. 때문에 최악의 경우 배열의 길이 N만큼 옮겨야 하므로 O(N)의 시간복잡도를 가진다.
- 추가 방식 : 원소를 새로 추가하기 위해서는 새로운 공간을 만들어야 하므로 매우 비효율적인 자료구조이다.
2) 링크드리스트(linked list)란?
크기가 정해지지 않은 데이터의 공간, 각 칸(노드)을 연결고리(포인터)를 이어주기만 하면 자유자재로 늘어난다.
- 접근 방식 : 특정 원소에 접근하려면 연결고리를 따라 탐색해야 한다. 최악의 경우 모든 원소를 지나가야 하므로 O(N)의 시간 복잡도를 가진다.
- 삽입/삭제/추가 방식 : 원소를 중간에 삽입/삭제하기 위해서는 앞 뒤의 포인터만 변경하면 된다. 따라서 O(1) 시간복잡도 안에 할 수 있다.
3) 배열와 링크드리스트 정리
추가적인 정보로, 파이썬의 list는 array로 구현되어 있지만, 내부적으로 동적배열이라는 것을 사용하여 배열의 길이가 늘어나도 O(1) 시간복잡도가 걸리도록 설계되어있다.
=> 파이썬의 list는 링크드리스트, 배열 모두 사용할 수 있게 만든 효율적인 자료구조❕
4) 클래스란?
같은 속성과 기능을 가진 객체를 총칭하는 개념
객체 : 세상에 존재하는 유일무이한 사물
예를 들어 클래스가 사람이면 객체는 전정국, 박지민 등이 될 수 있다.
-> 같은 속성과 기능을 가진 객체들을 묶어서 정의할 수 있다!
-
생성자(__init__)
객체를 생성할 때 데이터를 넣어주거나, 내부적으로 원하는 행동을 실행할 수 있게 한다.
생성자는 생성시에 호출되는 함수로, 클래스를 생성하기만 해도 print 내용이나 self가 동시에 출력된다.
여기서 self는 객체 자기 자신을 가리킨다.
-
self로 데이터 쌓기
self.name에 param_name을 저장 해 두겠다는 것은 그 객체의 name이라는 변수에 저장된다는 의미이다. -
클래스에 함수 추가
클래스 내부의 함수는 메소드(method)라고 한다.
talk이라는 메소드를 만들면 각 객체의 변수를 이용하여 메소드를 구현할 수 있다.
5) 링크드 리스트 구현(append, 모든 원소 출력)
-
노드들을 만들어 연결완료
하지만 이 방법은 노드들을 일일이 연겨해줘야 하는 방식이기 때문에 LinkedList라는 클래스를 생성하여 이를 반복할 수 있게 해야 한다. -
LinkedList 클래스 생성
LinkdList 는 self.head 에 시작하는 노드를 저장한다.
다음 노드를 보기 위해서는 각 노드의 next 를 조회해서 찾아가야 한다. -
append 함수 생성
현재 있는 노드의 가장 맨 뒤에 새로운 값을 가진 노드를 추가해주는 것이기 때문에 가장 맨 뒤의 노드까지 가야 한다. -
링크드 리스트 모든 원소 출력&결과
6)링크드 리스트 구현(원소찾기/추가/삭제)
-
원소 찾기
-
원소 추가
원소 찾기 코드에 해당 코드를 추가 -
원소 삭제
원소 추가 코드에 해당 코드를 추가
💜 오늘 느끼고 배운 점
오전 오후 : 자료구조와 알고리즘 인터넷 강의 수강
저녁 : 거북이반 실시간 강의 수강
평소에 헷가려했던 클래스를 복습하게 되었고, 링크드 리스트라는 것에 대해 알게되었다. 앞으로의 교육들에서 클래스를 굉장이 많이 사용한다고 들어서 완벽하게 숙지할 수 있도록 복습해야겠다.
