추상자료형

정의An abstract data type (ADT) is a data type that is organized in such a way that the specification of the operations on the objects is separated from the representation of the objects and the implementation of the operations.💡 데이터와 그 데이터에 적용할 수 있는 연산을 추상적인 수준에서 정의데이터의 구현 세부사항을 숨기고 사용자는 추상자료형이 제공하는 연산을 통해서만 데이터와 상호작용한다. 핵심개념자료형의 추상화데이터의 구현방식의 세부사항에 대해 숨기고 데이터와 관련 된 연산을 통해서만 상호작용할 수 있도록 정의한 데이터타..

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

[자료구조] 큐

개념 정의FIFO(First in First Out)의 자료구조 Front: 가장 처음에 들어온 원소의 인덱스 - 1Rear: 가장 마지막에 들어온 원소를 가리키는 인덱스capacity: 큐가 최대로 담을 수 있는 원소의 개수(배열의 크기 - 1)size: 현재 큐에 담겨져 있는 원소의 개수(size = rear - front)enqueue: 큐에 데이터를 넣는 연산(rear = (rear + 1) % capacity)dequeue: 큐에서 데이터를 빼는 연산(front = (front + 1) % capacity)Front 와 Rearfront, rear 두 개의 인덱스를 사용해서 전체 배열의 시작과 끝을 추적한다.front와 rear의 값이 동일할 경우, 해당 큐는 비어있다.front는 가장 먼저 추..

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

[알고리즘] 다이나믹 프로그래밍

의미최적부분구조 | 중복하위문제복잡한 문제를 간단한 하위 문제로 나눠 푸는 최적화기법 중에 하나다. 문제가 최적부분구조이고 하위문제들이 중복되는 경우에 동적 프로그래밍 전략을 적용할 수 있다. 최적부분구조란 문제의 최적 해결방법이 하위 문제들의 최적 해결방법으로 구성되는 구조다.용도배낭 문제와 동전 교환문제와 같은 최적화 문제, 최장공통 부분수열과 편집거리와 같은 문자열 처리, 최단경로 문제, 최소 비용경로와 같은 경로 찾기, 최적 자산 배분문제, 작업 스케줄링 문제 등 복잡한 문제를 효율적으로 해결하는 데에 쓰인다. vs 분할정복유사점문제를 나눠서 푼다작은 문제로 쪼갠다작은 문제도 최적화 문제다차이점최적화 문제 등 쪼개진 문제에서 중복된 문제들이 발생한다.구현전략탑다운큰 문제를 작은 문제로 쪼개서 푸는..

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

스택 예제: 미로찾기

스택스택은 데이터를 쌓는다. 그리고 가장 나중에 들어온 데이터를 먼저 처리한다. 당장 눈에 들어온 일부터 먼저 처리하는 느낌이다. 미로를 탐험하다보면 보고 있는 위치가 어떤 장소이냐에 따라 스택에 넣을 지 말지, 탐색을 할 지를 결정할 수 있다. 위치struct Pos { int row; int col; // 디버깅을 위한 편의 기능 friend ostream &operator 스택으로 미로찾기void StackMaze() { Stack s; Pos start = {1, 1}; // i = 1, j = 1 시작 지점 s.Push(start); while (!s.IsEmpty()) { Pos p = s.Top(); s.Pop(); ..

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

[자료구조] Stack

자료구조를 사용하는 이유데이터는 구조화 된 여부에 따라 정형, 비정형으로 구분한다. 컴퓨터 시스템에서 데이터를 효율적으로 다루기 위해서는 데이터가 구조화되어야한다. 데이터를 효율적으로 저장하고 관리하기 위해 구조화 된 형태를 자료구조라고 한다. 배열, 스택, 큐 모두 자료구조이다. 자료구조마다 각기 다른 방식으로 데이터를 관리하고 처리한다. 스택개념스택은 후입선출원칙(LIFO)에 따라 데이터를 관리한다. 데이터를 넣는 순서와 반대로 데이터가 꺼내진다. 즉, 가장 마지막에 넣은 데이터가 가장 먼저 나오게 된다.스택에서 가장 마지막에 들어간 데이터의 위치를 top이라고 한다.스택은 push, pop, peek 연산이 있다. push 연산은 데이터를 넣는다. pop은 top에 있는 데이터를 제거한다. peek..

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

[ 백준 / Python ] 17478 - 재귀함수가 뭔가요?

문제출처https://www.acmicpc.net/problem/17478   문제분석재귀함수의 구현을 연습하는 문제다. 입력값에 따라 문자열을 어떻게 출력하는 지의 로직을 짜야한다.코드구현n = int(input())dashes = "____"line0 = "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n"line1 = '"재귀함수가 뭔가요?"\n'line2 = '"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n'line3 = "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n"line4 = '그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."\n'line5 = '"재귀..

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