대학생 쩡딱구리

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 1. 연결 리스트의 위치 식별 방법 연결 리스트에서 인덱스로 위치를 식별하면 좋을까? - 좋지 않다. 연결 리스트를 인덱스로 접근하려면 반복적으로 탐색해야 하므로 효율적으로 처리할 수 없으며, 연결 리스트가 바뀔 때마다 인덱스가 달라질 수 있다. 즉, 비효율적이다. 연결 리스트에서 직접 노드로 위치를 식별하게 하면 어떨까? - 노드는 내부 클래스로 은닉시켜 둔 상태이므로 외부로 노출하는 것은 객체 지향 설계 사상에 위배된다. 그렇다면 왜 ..

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로 연결하면 원형 연결 리스트가 된다. 아래 그림도 보자. 이 그림을 통해 볼 수 있는 원형 연결 리스트의 특징은 다음과 같다. 리스트의 시작과 끝 개념이 없다. 노드 간에 순서 관계를 부여하기 위해 특정 노드의 레..

한방향 연결 리스트 내용 참고! 4-1. 한방향 연결 리스트 그동안 동적 배열과 동적 배열을 기반으로 한 자료구조를 다루었다. 하지만 동적 배열엔 아래와 같은 단점이 있다. 동적 배열의 길이가 저장하는 요소의 수보다 길다. 즉 메모리 낭비가 있다. � jjeongttakgoori.tistory.com 1. 스택 구현 스택이 뭔지 기억이 안 난다면 이 글을 참고하면 좋을 것 같다. 3-1. 스택 1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되고(push), jjeongttakgoori.tistory.com 가장 먼저 들어간 것이 가장 나중에..

그동안 동적 배열과 동적 배열을 기반으로 한 자료구조를 다루었다. 하지만 동적 배열엔 아래와 같은 단점이 있다. 동적 배열의 길이가 저장하는 요소의 수보다 길다. 즉 메모리 낭비가 있다. 분할 분석 방식이 실시간 시스템에서 허용되지 않을 때가 있다. 배열의 삽입 또는 삭제 연산 비용이 O(n)으로 비싸다. 삽입, 삭제 연산이 중요할 경우 문제가 될 수 있다. 동적 배열의 이러한 단점을 해소해 삽입/연산을 빠르게 할 수 있는 선형 자료구조가 연결 리스트이다. 1. 연결 리스트란? 연결 리스트는 분산 관리 방식 자료구조이다. 이 말은 각 요소 별로 노드를 할당해 관리한다는 의미이다. 연결 리스트는 노드가(node)가 링크(link)로 연결된 순차 자료 구조로, 요소의 접근이 느리지만(O(n)) 삽입/삭제 연..

덱 = 스택 + 큐이다! 스택과 큐를 잠깐 복습하고 보는 것을 추천한다. 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. 덱 위에서 썼듯 덱은 스택과 큐를 합쳐놓은..