전체 글149 [자료구조] 정렬 2. 간단한 정렬들 앞서 정렬의 개념에 대해 간략하게 설명했다. 이제 매우 간단한, 그러나 비효율적인 정렬을 쉽게 알아본다.1) 선택 정렬 (Selection Sort)선택 정렬은 리스트에서 가장 작은 숫자를 선택해서 앞쪽으로 옮기는 방법을 반복하여 정렬하는 방식이다.전체 숫자 리스트를 아직 정렬되지 않은 오른쪽 리스트와 정렬이 완료된 왼쪽 리스트로 분류하는데, 맨 처음에는 모든 숫자가 오른쪽 리스트(정렬되지 않은 상태)에 담겨져 있다.즉 오른쪽 리스트에서 가장 작은 숫자들을 계속해서 선택하여 왼쪽 리스트에 차례로 담는 방식을 반복하여 정렬하는 것이다!def printStep(arr, val): print(" Step %2d = " % val, end='') print(arr)def selection_sort(A.. 2024. 1. 7. [자료구조] 정렬 1. 정렬이란? 우리가 효율적으로 데이터를 저장하고 관리하기 위해서 필요한 것 중 하나가 정렬이다. 정렬은 순서를 기준으로 오름차순 정렬과 내림차순 정렬으로 나눌 수 있는데, 오름차순 정렬은 작은 순서대로 정렬하는 것이고 내림차순 정렬은 큰 순서대로 정렬하는 것이다. 정렬시켜야 될 대상을 보통 레코드(record)라고 부르며, 레코드는 여러 개의 필드(field)로 이루어진다. 여기서 정렬이 기준이 되는 필드를 키(key) 또는 정렬 키(sort key)라고 한다. 예를 들어 수많은 경주마(레코드)들을 정렬하고 싶은데… 경주마들은 각각 이름, 키, 나이, 품종 등(필드) 가지각색의 속성들을 가지고 있다 이 중 나는 이름을 기준으로 정렬하고 싶다면, 이름이 정렬 키가 되는 것이다. 정렬 장소에 따른 분류 내부 정렬: 모든.. 2024. 1. 7. [자료구조] 연결된 구조 (Linked Structure) 앞에서 우리는 스택과 큐, 덱을 구현할 때 배열을 이용했다.배열을 이용하면 쉽고 간단하게 구현할 수 있어서 편리하지만 일정 크기로 용량이 고정되고 메모리가 불필요하게 낭비된다는 단점이 있다. 이러한 문제점들을 해결할 수 있게 고안된 자료구조가 바로 연결된 구조이다! 연결된 구조는 노드(node)를 여러 개 연결시켜 구현하는데, 노드 하나에는 요소를 담는 데이터 필드와 다음 노드를 가리키는 링크 필드를 갖는다.즉 가장 처음 노드만 알면 링크 필드를 거치고 거쳐 배열을 사용하지 않고도 해당 자료구조의 모든 요소에 접근할 수 있다는 것이다! (물론 n번째 요소에 접근하는 데에는 O(n)이 소요될 것이다)이 때 가장 처음 노드를 가리키는 변수를 ‘헤드 포인터(head pointer)’라고 한다. 연결 리스트의 .. 2024. 1. 7. [자료구조] 덱 (Deque) 덱: 전단(front)와 후단(rear) 모두에서 삽입 삭제가 가능한 큐즉 큐의 업그레이드된 버전이라고 볼 수 있다. 그래서 원형 큐를 상속해서 덱을 구현하는 게 효과적임! 큐의 기능isEmpty(): 덱이 비어있으면 True를, 아니면 False를 반환한다.addFront(e): 항목 e를 덱의 맨 앞(front)에 추가한다.deleteFront(): 덱의 맨 앞(front)에 있는 항목을 삭제하고 반환한다.getFront(): 덱의 맨 앞(front)에 있는 항목을 반환한다.addRear(e): 항목 e를 덱의 맨 뒤(rear)에 추가한다.deleteRear(): 덱의 맨 뒤(rear)에 있는 항목을 삭제하고 반환한다.getRear(): 큐의 맨 뒤(rear)에 있는 항목을 반환한다.isFull():.. 2024. 1. 7. [자료구조] 큐 (Queue) 큐: 선입선출(FIFO)의 자료구조후단(rear)에서 삽입하고 전단(front)에서 삭제한다.큐를 단순히 front와 queue가 있는 리스트로 구현하면 front의 인덱스는 항상 0, rear의 인덱스는 항상 -1이 되는 문제점이 발생하는데, 이렇게 될 경우 삭제나 삽입 연산 중 하나는 적어도 O(n)의 시간복잡도를 가져서 비효율적임.그래서 원형 큐를 구현하는 것이 더 효율적이다!rear과 front 변수를 삽입과 삭제 시에 바꿔줌으로써 항상 O(1)의 시간을 가질 수 있도록 만들어준다!컴퓨터와 프린터 사이에 인쇄 작업실시간 비디오 스트리밍의 버퍼링은행의 대기표큐의 기능isEmpty(): 큐가 비어있으면 True를, 아니면 False를 반환한다.enqueue(e): 항목 e를 큐의 맨 뒤(rear)에 .. 2024. 1. 7. [자료구조] 스택 (Stack) 스택: 후입선출(LIFO)의 자료구조출입구가 하나밖에 없는 일직선 통로와 같다. 스택이 사용되는 예시로는 아래를 들 수 있다.되돌리기 기능 (Ctrl + Z)브라우저의 이전 페이지로 이동함수 호출 후 메인으로 복귀괄호 닫기 프로그램등등에 사용된다. 스택의 기능isEmpty(): 스택이 비어있으면 True를, 아니면 False를 반환한다.push(e): 항목 e를 스택의 맨 위에 추가한다.pop(): 스택의 맨 위에 있는 항목을 꺼내 반환한다.peek(): 스택의 맨 위에 있는 항목을 반환한다. (꺼내지 않음)size(): 스택의 항목 개수를 반환한다.clear(): 스택을 전부 비운다.스택의 구현class Stack: def __init__(self): self.top = [] d.. 2024. 1. 7. 이전 1 ··· 21 22 23 24 25 다음 반응형
