본문 바로가기

AI/데이터 엔지니어링 데브코스32

[1주차-2] 코딩테스트 연습 - 연결리스트와 스택(3) 스택 스택은 넣을 때(push)는 한쪽 끝에서 밀어 넣어야 하고 꺼낼 때(pull)는 같은 쪽에서 뽑아 꺼내야 하는 제약이 있는 자료를 보관할 수 있는 선형 구조이다(후입선출 구조). 스택 언더플로우(stack underflow): 꺼낼 원소가 없을 때 pull 스택 오버플로우(stack overflow): 스택이 가득 차 있을 때 push 스택의 연산 1) size(): 현재 스택에 들어 있는 데이터 원소의 수를 구함 2) isEmpty(): 현재 스택이 비어 있는지를 판단 3) push(x): 데이터 원소 x를 스택에 추가 4) pop(): 스택의 맨 위의 저장된 데이터 원소를 제거하고 반환 5) peek(): 스택의 맨 위의 저장된 데이터 원소를 반환하는데 제거 x 스택의 추상적 자료구조 구현 1).. 2023. 4. 11.
[1주차-2] 코딩테스트 연습 - 연결리스트와 스택(2) 연결리스트(더미 노드 포함) 더미 노드(dummy node)를 사용하면 기존의 연결리스트에서 '특정 번째 수’를 알려주고 뒤의 노드를 삽입/삭제하는 것이 아니라 “특정 원소의 바로 다음”을 지정하여 노드를 주고 뒤의 노드를 삽입/삭제하는 방식으로 변형을 가할 수 있다. 더미 노드(dummy node)란 0번째 노드를 만들어 내용물이 들어있지 않은 노드로 이를 헤드에 추가하여 더미 노드를 포함한 연결리스트를 구현할 수 있다. 더미 노드를 사용하면 리스트의 양 끝값을 처리할 때, 코드가 간편해진다는 장점이 있다. 기존의 연결리스트를 구현하는 코드에서 변경사항이 있는데 다음 코드를 참고해보자. class Node: def __init__(self, item): self.data = item self.next .. 2023. 4. 11.
[1주차-2] 코딩테스트 연습 - 연결리스트와 스택(1) 연결리스트 연결리스트는 각 원소를 줄줄이 엮어서 관리하는 방식이다. 각각의 아이템(node)에는 데이터(data)와 다음 데이터를 가리키는 링크(link)가 담겨 있다. 리스트의 맨 앞은 ‘헤드(head)’라고 하고 맨 끝은 ‘테일(tail)’이라고 한다. 연결리스트는 원소를 삭제하거나 다른 원소를 삽입하는 것이 선형배열의 경우보다 빠르다. 하지만 메모리 소요가 크고 특정 원소를 참조하는 데 선형배열보다 시간이 오래 걸린다는 단점이 있다. [기본 구조] class LinkedList: class Node: def __init__(self, item): self.data = item self.next = None def __init__(self): self.nodeCount = 0 self.head = N.. 2023. 4. 11.
[1주차-1] 코딩테스트 연습 - 선형배열과 재귀 알고리즘 파이썬에서 이미 데이터 타입을 제공하더라도 기본적인 데이터 타입만으로 해결할 수 없는 문제가 있을 수 있다. 예를 들어, 파이썬 내장함수인 max 함수는 모든 원소를 다 탐색하므로 리스트의 길이만큼의 시간이 걸린다. 즉 자료의 길이가 길어질수록 소요 시간이 오래 걸린다. 1. 선형배열 파이썬에서 배열은 리스트라는 데이터형으로 제공된다. list.append() #원소 덧붙이기 list.pop() #원소 하나 꺼내기 위의 두 작업은 시간 복잡도가 O(1)이므로 실행시간을 최소로 할 수 있다. 물론 list.pop(n)처럼 인덱스를 지정해주면 시간 복잡도가 O(n)이 된다. list.insert() #원소 삽입하기 del list[n] #원소 삭제하기 list.index() #원소 위치 찾기, 해당 원소가 .. 2023. 4. 10.

티스토리툴바