티스토리

cs-learn

검색하기

블로그 홈

cs-learn

humilde.tistory.com/m

computer science, machine learning, mathematics

구독자: 0

방명록 방문하기

주요 글 목록

연결 리스트 (Linked List) 5 - 양방향 연결 리스트 (Doubly Linked List) 양방향 연결 리스트양방향 연결 리스트는 각 노드가 앞뒤 방향으로 링크된다. 각 노드가 다음 노드 뿐 아니라 직전 노드에 대한 링크도 가져서, 한 노드만 알면 앞뒤로 자유롭게 이동이 가능하다. 양방향 연결 리스트의 삽입 먼저 삽입할 노드의 바로 앞자리 노드를 prev로 레퍼런스하고, prev 다음 자리에 노드를 삽입한다. 양방향 연결 리스트의 삭제삭제할 노드를 curr로 레퍼런스로 설정하고 양쪽 노드를 바로 연결시킨다. 양방향 연결 리스트의 구현class BidirectNode: def __init__(self, x, prevNode:'BidirectNode', nextNode: 'BidirectNode'): self.item = x self.prev = prevNode .. 공감수 0 댓글수 0 2024. 9. 18.
연결 리스트 (Linked List) 4 - 원형 연결 리스트 (Circular Linked List) 원형 연결 리스트(Circular Linked List)연결 리스트에서는 첫 노드와 마지막 노드에 접근성이 극적으로 차이난다. 첫 노드에는 단번에 연결 가능하고, 두번째 노드에는 링크를 끝까지 따라가야 접근할 수 있다. 그 결과 원소를 삽입/삭제할 때, 맨 앞, 맨 끝에 따라서 차이가 난다. 따라서, 이 차이는 마지막 노드가 첫 번째 노드를 링크하도록 바꾸면 해소될 수 있고, 이런 구조의 연결 리스트를 원형 연결 리스트라 한다. 레퍼런스 __head 대신 마지막 노드에 대한 레퍼런스 __tail을 두고, 마지막 노드가 맨 앞의 더미 헤드 노드를 링크하게 만든다. 빈 원형 연결 리스트는 더미 헤드 노드가 자신을 링크한다. __tail을 마지막 노드를 가리키게 만들었을 때, 맨 뒤와맨 앞에 대한 접근성의 차.. 공감수 0 댓글수 0 2024. 9. 18.
연결 리스트 (Linked List) 3 - 연결 리스트의 구현 원소 삽입원소 x를 i번째 자리에 삽입하는 메서드# i번째 연결리스트의 원소 x 삽입하기def insert(self, i:int, newItem): if i >=0 and i ListNode: curr = self.__head for index in range(i+1): curr = curr.next return curr # 연결 리스트의 끝에 원소 x 추가하기 def append(self, newItem): prev = self.__append(self.__numItems-1) newNode = ListNode(newItem, prev.Next) prev.next = newNode self.__numItems +=1 원소 삭제i번째 노드를 삭제하는 메서드 # i.. 공감수 0 댓글수 0 2024. 9. 17.
연결 리스트 (Linked List) 2 - 각 작업 설명 원소 삽입 맨 앞에 원소 삽입__head : 첫 번째 노드를 가리키는 레퍼런스newNode.item = xnewNode.next = __head__head = newNode__numItems += 1... 중간, 맨 뒤에 원소 삽입prev: 삽입 노드의 직전 노드를 가리키는 레퍼런스newNode: 새로 삽입하려는 노드newNode.item = xnewnode.next = prev.nextprev.next = newNode__numItems += 1 .. 연결 리스트에 원소 삽입 알고리즘if i == 0: newNode.item = x newNode.next = __head __head = newNode __numItems +=1else: newNode.item = x newNode... 공감수 0 댓글수 0 2024. 9. 13.
연결 리스트 (Linked List) 1 - 객체 구조 연결 리스트의 객체 구조앞서 언급했듯이, 리스트의 하부 구조는 배열로 이루어져 있어서, 다음 두 가지와 같은 단점이 존재한다. 1. 배열의 크기는 고정되어 있어서 배열이 크기 이상으로 삽입될 경우, 더 큰 배열을 할당받아 원소를 모두 옮겨주는 작업을 진행해야함2. 원소를 삽입 또는 삭제하려면 일부 또는 원소 전부를 한 칸씩 시프트하는 불편함이 존재한다.' 연결 리스트(Linked List)는 배열의 공간 낭비를 피할 수 있는 자료구조이다. 원소가 추가 될 때마다 공간을 할당받아 추가하는 동적 할당 방식을 따른다. 연결 리스트의 노드 구성 item : 정수나 실수 같은 숫자 타입이나 복잡한 객체가 저장 필드next : 다음 노드를 가리키는 링크 연결 리스트의 일반적인 형태__head : 첫 번째 노드를 .. 공감수 1 댓글수 1 2024. 9. 13.
리스트(List) 리스트(list)는 '줄 세워진 데이터' 또는 '늘어선 데이터'를 의미한다. 리스트의 작업 리스트 ADT 예시i번 자리에 원소 x 삽입i번째 원소 삭제원소 x 삭제i번째 원소 확인원소 x의 index리스트 사이즈 etc 리스트 구현 파이썬의 리스트는 하부가 배열로 구현되어 있다중간에 원소 삽입하면, 삽입한 원소 이후의 원소들이 모두 한칸씩 shift 하게됨확보해놓은 배열 공간이 다 찼을 때, 새로운 배열을 할당받아 기존 배열 내용 복사 etc하부 작업을 직접하진 않지만, 배열 기반 리스트의 단점은 분명히 존재함리스트의 객체 구조파이썬에서는 리스트 자료구조가 기본적으로 제공된다. 아래 선언한 리스트 a, b는 각각 하나씩의 객체다.a = []b = [1, 3, 5] 리스트 객체에서는 다음과 같이 11개의.. 공감수 0 댓글수 0 2024. 9. 13.
재귀와 귀납적 사고 어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 재귀적 구조를 갖고 있다고 말한다. 재귀 구조 예시 수열 등차 수열 seq(n): if n = 1: return 1 else: return seq(n-1) + 5 ※반복해서 호출하는 재귀 알고리즘은 끝나기 위해서 반드시 경계 조건을 가지고 있어야한다. 위 알고리즘에서는 if n = 1이 경계조건이다. 피보나치 수열 fib(n): if n=1 or n=2: return 1 else: return fib(n-1) + fib(n-2) ※재귀 알고리즘의 사용은 문제를 해결하는데 유용할 수 있지만, 잘못 쓰면 치명적일 수 있다. 위에 예시에서 n이 커질수록 걸리는 시간이 매우 증가하게 된다. 이는 한번 계산했던 결과.. 공감수 0 댓글수 0 2024. 2. 13.
자료구조 소개 자료구조 간략 소개 선형 자료구조 : 데이터가 한줄로 배치된 자료구조 색인 자료구조 : 데이터를 효율적으로 찾기 위한 자료구조 추상 자료형 (Abstract Data Type) 추상 데이터 타입(ADT : Abstract Data Type)은 어떤 데이터 타입이 어떤 작업으로 이루어지는지만 표현한 것으로, 구현 방법을 명시하지 않는다는 점에서 자료구조와는 다르다. 어떤 대상이 '지원하는 작업을 나열해 표현'하는 것을 '추상적으로 표현'한다라고 하며, 대상을 그렇게 표현한 것을 추상적 데이터 타입이라고 한다. ex) 리스트의 ADT 표현 ADT '리스트' 작업: i번째 자리에 새 원소 넣기 원소 x 찾기 i번째 자리의 원소 삭제하기 비어 있는지 확인하기 청소하기 위처럼 특정 대상에 대한 ADT는 유동적이다.. 공감수 0 댓글수 0 2024. 1. 23.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.