대학생 쩡딱구리

1-2. 시간 복잡도 분석 1. 알고리즘 분석 0. 알고리즘과 자료 구조 1. 알고리즘이란? "유튜브 알고리즘이 나를 꽤 괜찮은 곳으로 데리고 왔다." 2PM의 '우리 집' 유튜브 영상에 달린 베스트 댓글 중 하나다. 이 예시와 같 jjeongttakgoori.tistory.com 삽입 정렬을 처음 다룬 게시글이다. 안 봐도 무방. 1. 포지션 리스트로 삽입 정렬 문제 풀어보기 워크(walk): 마커부터 첫 번째 노드 방향으로 이동한 것. 워크 앞 노드와 피봇을 비교한다. 피봇(pivot): 마커의 다음 노드로, 정렬해야 할 대상 마커(marker): 정렬된 리스트의 가장 오른쪽 노드 2. insertion_sort def insertion_sort(L): """Sort PositionalList of ..

4-4. 양방향 연결 리스트 한방향 연결 리스트는 연결 구조가 비대칭이라 임의의 노드의 삭제가 아주 비효율적이다. 즉, 아래의 단점을 갖는다. 해당 노드의 레퍼런스를 알아도 삭제에 O(n)의 시간 복잡도를 갖는다. 삭제 jjeongttakgoori.tistory.com 3-3 덱 덱 = 스택 + 큐이다! 스택과 큐를 잠깐 복습하고 보는 것을 추천한다. 3-1. 스택 1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First O jjeongttakgoori.tistory.com 양방향 연결 리스트로 덱을 구현하면 모든 연산이 O(1) 시간 복잡도를 갖는다. 1. LinkedDeque 클래스 from .doubly_linke..

한방향 연결 리스트는 연결 구조가 비대칭이라 임의의 노드의 삭제가 아주 비효율적이다. 즉, 아래의 단점을 갖는다. 해당 노드의 레퍼런스를 알아도 삭제에 O(n)의 시간 복잡도를 갖는다. 삭제를 하려면 삭제할 노드뿐만 아니라 이전 노드의 레퍼런스가 필요한데, 항상 head부터 해당 노드의 이전 노드까지 이동하는 시간이 필요하다. 연결 리스트가 대칭성을 갖도록 이전 노드와 다음 노드의 레퍼런스를 갖도록 해보자. 1. 양방향 연결 리스트 양방향 연결 리스트(Doubly Linked List)는 노드들이 양방향으로 연결된 리스트로, 각 노드들은 객체(element), 이전 노드(prev), 다음 노드(next)의 레퍼런스를 저장한다. 이때 링크를 따라 특정 노드의 데이터를 접근하고 수정한다. 양방향 연결 리스트..

연결 리스트에 대한 내용은 여기에 있다. 4-1. 한방향 연결 리스트 그동안 동적 배열과 동적 배열을 기반으로 한 자료구조를 다루었다. 하지만 동적 배열엔 아래와 같은 단점이 있다. 동적 배열의 길이가 저장하는 요소의 수보다 길다. 즉 메모리 낭비가 있다. � jjeongttakgoori.tistory.com 1. 원형 연결 리스트 원형 연결 리스트(Circular Linked List)는 노드들이 원형으로 연결된 리스트이다. 위 그림과 같이 한방향 연결 리스트의 tail의 next를 head로 연결하면 원형 연결 리스트가 된다. 아래 그림도 보자. 이 그림을 통해 볼 수 있는 원형 연결 리스트의 특징은 다음과 같다. 리스트의 시작과 끝 개념이 없다. 노드 간에 순서 관계를 부여하기 위해 특정 노드의 레..

덱 = 스택 + 큐이다! 스택과 큐를 잠깐 복습하고 보는 것을 추천한다. 3-1. 스택 1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되고(push), � jjeongttakgoori.tistory.com 3-2. 큐 3-1. 스택 1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되 jjeongttakgoori.tistory.com 1. 덱 위에서 썼듯 덱은 스택과 큐를 합쳐놓은..

1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되고(push), 가장 최근에 저장된 값이 먼저 나간다(pop). 스택은 데이터를 순서대로 쌓아두었다가 가장 최근 데이터부터 봐야 할 때 쓰이는데 예를 들어 편집기의 되돌리기 기능(undo)이 스택의 예이다. 스택의 기본 연산은 아래와 같다. Operation Comment S.push(e) Top에 새로운 요소 추가 S.pop() - Top 요소를 반환하면서 제거 - 단, 스택이 비어 있으면 error 생성 S.top() - Top 요소 반환 - 스택이 비어 있으면 error 생성 S.is_e..