자료구조

연결 리스트(LinkedList)

연결 리스트 리스트는 데이터에 순서를 매겨놓은 자료구조이다. (단일)연결리스트는 리스트의 한 종류이다.여기서는 포인터를 이용해서 연결리스트를 만들어보겠다. 연결리스트는 위의 그림처럼 각 노드들이 연결되어있는 형태를 나타낸다.각 노드 안에는 데이터와 다음노드를 참조하는 포인터로 이루어져 있다.A, B, C 의 노드가 있다고 하면 첫번째 노드 안에는 A라는 데이터와 B를 참조하는 포인터가 있다.두번째 노드 안에는 B라는 데이터와 C를 참조하는 포인터가 있다.세번재 노드 안에는 C라는 데이터와 다음이 없으므로 참조하는 포인터는 없다. 여기서 첫번째 노드를 머리 노드, 마지막 노드를 꼬리 노드라고 한다. 연결리스트의 장점은 원하는 만큼의 노드를 동적으로 추가/삭제 할 수 있다.단점은 배열처럼 메모리공간에 정렬되..

큐(queue)

큐 스택과 같이 데이터를 임시 저장하는 자료구조이다. 하지만 스택과 반대로 가정 먼저 넣은 데이를 가장 먼저 꺼내는 선입선출(FIFO: First In First Out) 구조를 가진다.예: 놀이공원에서 보통 줄 서는 구조 큐에 데이터를 넣을 떄는 인큐(enqueue), 큐에서 데이터를 꺼낼 때는 디큐(dequeue) 함수를 정의 데이터를 직접 꺼내는 것이 아니라 두개의 포인터(front, rear) 를 사용해서 위치를 나타낸다. 코드 # 고정 길이 큐 구현하기 with 링 버퍼. # 기존의 리스트로 dequeue 구현 시 시간 복잡도가 O(n) 으로 상당히 비효율적이다. # 이를 해결하기 위해 링 버퍼를 사용. from typing import Any class FixedQueue: class Empt..

스택(Stack)

스택 데이터를 임시 저장할 때 사용하는 자료구조, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식이다. 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조로 되어있다.데이터를 넣을 때는 push, 데이터를 꺼낼 때는 pop을 사용한다. 파이썬에서는 보통 스택을 구현하지 않고 리스트로 만들고 append 해서 데이터를 넣거나 pop으로 데이터를 꺼낸다.아래의 코드는 스택을 클래스로 구현해본 것이다. 코드 class Stack: class Empty(Exception): """스택이 비어있을 때 pop 또는 peek 를 수행할 때 예외 처리""" print("야") pass class Full(Exception): """스택이 가득일 때 push 를 수행할 때 예외 처리""" pass def __in..

[python] 백준 - 5430. AC

🤔문제 해결 S2 | 자료구조, 데크, 구현 리버스와 제거 두가지 오더가 있다. 리버스를 하게 되면 O(N)의 시간복잡도 발생 그러므로 리버스를 하지말고 이게 뒤집힌 상황인지 아닌지만 구분해준다. 그 후 그대로이면 맨 앞의 숫자를 제거하고 뒤집힌 상황이면 맨 뒤의 숫자를 제거한다. 💻소스 코드 from collections import deque for tc in range(int(input())): # RR이면 원래상태이므로 제거해줌 order = input().replace('RR', '') n = int(input()) number = input()[1:-1] if number: number = deque(list(map(int, number.split(',')))) # R은 뒤집지 말고 my_re..

힙 정렬(heap sort)

📔 힙 정렬(heap sort) 이란 힙트리구조를 이용하여 정렬하는 알고리즘 힙트리: 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리 힙정렬을 하기 위해서는 먼저 힙 구조를 가지도록 만들어야 한다. 히피파이 알고리즘을 통해 힙구조로 만든다. 모든 정점에 대해서 히피파이를 수행하므로 n x logn 의 시간복잡도를 가진다. 사실상 모든 정점이 아니라 절반의 정점만 해도 가능하다 n/2 x logn => (n/2이 logn 보다 크다고 가정할 때) => 결국 O(n) 의 시간복잡도를 가진다. 📔 힙 정렬(heap sort) 구현 # (최대)힙 구조 만들기 def heapify(): for i in range(1, N): c = i while c > 0: root = (c - 1..

병합 정렬(merge sort)

📔 병합 정렬(merge sort) 이란 분할정복을 활용하여 구현하기 때문에 시간복잡도는 O(nlogn) 퀵정렬과 비슷 분할정복: 문제를 작은 2개의 문제로 분리하고 각각 해결한 후, 다시 모아 원래의 문제를 해결하는 방법. 보통 재귀함수 호출을 이용하여 구한다. 퀵정렬과 다른 점이 있다면 퀵정렬의 경우 pivot값에 따라 편향되게 분할 될 수 있는 가능성이 있기 때문에 최악의 경우 O(n^2)의 시간복잡도를 가진다. 그러나 병합정렬의 경우 정확히 반씩 나눈다는 점에서 최악의 경우에도 O(nlogn)의 시간복잡도를 보장한다. 만약 8개의 숫자를 정렬한다고 하자. 8에서 4로 나누고, 4에서 2로 나누고, 2에서 1로 나눈다. 즉 3번 나눴다. 그러므로 나누는 것은 3 = log8 이므로 logn이다. 나..