[ 자료구조 ] Stack

#1 스택스택은 데이터를 쌓는 형태로 가장 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last in First Out) 자료구조다.#2 연산push스택에 데이터를 삽입하는 연산으로 스택의 가장 위에 데이터를 저장한다.pop스택에 데이터를 삭제하는 연산으로 가장 마지막에 저장한 데이터를 제거한다.peek스택의 가장 위 데이터를 확인한다.#3 스택의 사용파이썬# 빈 스택 초기화stack = []print("stack:", stack)# 스택에 원소 추가stack = [1, 2, 3]stack.append(4)print("stack:", stack)# 스택 원소 제거stack = [1, 2, 3]stack.pop()print("stack:", stack)# 스택 원소 찾기stack = [1, 2, 3..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 9. 26.

복잡도

시간과 공간프로그램을 실행하기 위해서는 시간과 메모리가 필요하다. 같은 기능을 수행하는 프로그램 둘이 있을 때 시간과 메모리를 덜 소모할수록 효율적인 프로그램이다.복잡도복잡도란 작성한 알고리즘이 효율적인지 시간, 공간적으로 효율적인지를 판단하는 기준이다. 알고리즘의 효율성을 정량화한다. 시간복잡도는 알고리즘의 실행시간을 정량화한 것이다. 공간복잡도는 알고리즘의 실행에 필요한 메모리량을 정량화한 것이다.빅오표기법빅오표기법은 알고리즘의 복잡도를 표기하는 방법 중에 하나로 최악의 경우의 상관관계를 표현한다. 입력 데이터 대비 함수를 실행하는 데에 필요한 비용(시간, 공간)의 상관관계를 수식의 최고차항으로 표현한다.그래프는 시간복잡도를 표현한 것이다. 최고차항이 커질수록 동일 입력 데이터 대비 소요되는 시간이 ..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 9. 26.

최대힙, 최소힙

힙힙은 완전이진트리로 최대값 또는 최소값을 빠르게 찾을 수 있는 자료구조다. 우선순위큐를 구현하는 데 자주 사용된다.힙은 삽입연산과 삭제연산이 있다.삽입연산데이터 삽입은 힙의 맨 끝에서 이뤄진다. 부모노드와 우선순위를 비교해 부모보다 자식이 높으면 부모와 자식의 위치를 바꾸면서 루트노드까지 비교한다.삽입연산의 과정이진트리의 맨 마지막 자리에 노드를 추가한다.부모노드와 우선순위를 비교 후 자식 노드가 우선순위가 높으면 부모노드와 자리를 교체한다.부모노드가 우선순위가 높을 때까지 2를 반복한다.삭제 연산데이터 삭제는 힙의 루트노드에서 이뤄진다. 루트노드를 삭제한 후 가장 마지막에 추가한 노드를 루트노드의 위치로 이동한다. 이동한 노드와 자식노드의 우선순위를 비교해 힙을 재정렬한다.삭제연산의 과정트리의 마지막..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 9. 24.

[ 백준 / Python ] 2164 - 카드2

문제출처 문제분석정수 n을 입력 받은 후 로직에 따라 최후에 남는 카드 번호를 반환하는 로직을 짜야한다. 컨테이너에 1부터 n까지의 카드가 있고 맨 앞의 카드는 제거, 그 다음 카드는 덱의 가장 뒤로 보낸다. 카드가 하나가 남을 때까지 과정을 반복한다. 로직을 정리하면 다음과 같다.1. n을 입력받음2. 정수 1부터 n까지를 아이템으로 갖는 컨테이너 생성3. 컨테이너에서 가장 앞 아이템 제거4. 컨테이너에서 가장 앞 아이템을 맨 뒤로 보내기5. 컨테이너에 남은 아이템의 갯수가 1개일 때까지 3,4 단계 반복6. 남은 아이템 반환코드구현from sys import stdinfrom collections import dequeinput = stdin.readlinen = int(input())queue = ..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 9. 22.

[ 백준 / Python ] 18110 - solved.ac

문제출처 https://www.acmicpc.net/problem/18110문제회고절삭평균이라는 개념을 이용해 알고리즘을 구현해야하는 문제였다. 엣지 케이스에 대한 연습과 파이썬의 round 함수의 작동원리를 배울 수 있게 되었다. 게다가 시간초과를 극복하기 위해 input 대신에 sys.stdin.readline을 써야했다. round() 함수반올림이란 수가 있을 때 5보다 작으면 내리고 5와 같거나 크다면 다음 자리에 1을 더하는 개념이다. 하지만 파이썬의 round 함수는 다르게 작동한다. 수가 5보다 작으면 내리고 5보다 클 때 올리는 것은 동일하다. 하지만 수가 5일 때 처리하는 방식이 반올림 개념과 다르다. 수가 5일 때는 앞자리가 홀수일 때 내리고 짝수일 때는 올린다. 문제접근input함수와..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 9. 21.

[자료구조] 덱

개념Rear와 Front 모두에서 데이터를 넣고 뺄 수 있는 자료구조다. 스택과 큐의 장점을 모두 갖고 있다.특징멤버덱도 큐와 마찬가지로 배열이라 연결리스트를 이용해서 구현할 수 있다. 메모리적인 측면에서 봤을 때 원형큐처럼  배열을 활용해서 구현하는 것이 좋다. 두개의 포인터로 원소들을 관리한다.frontrearfront는 덱의 앞을 가리키고 순서상 가장 앞의 원소의 인덱스보다 -1 값을 가진다.rear는 덱의 뒤를 가리키고 순서상 가장 마지막 원소의 인덱스와 같다. 연산덱은 스택과 큐의 장점을 붙인 자료구조다. 덱의 연산은 다음과 같다.pushFront()pushBack()popFront()popBack()원소들이 어느 방향으로 들어오냐에 따라 포인터의 움직임이 다르다.pushFront()의 경우 덱..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 28.