[자료구조] 덱

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

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 8. 28.

[C++] 상속

개념새로운 클래스는 기존 클래스의 속성과 메서드를 물려받을 수 있으며, 이를 통해 새로운 클래스는 기존 클래스의 기능을 확장하거나 수정할 수 있다.코드예시class Base { // 피상속 클래스, 부모클래스public: int base_var; void base_function() { // base class function }};class Derived : public Base { // 상속클래스, 자식클래스public: int derived_var; void derived_function() { // derived class function }};클래스 상속Derived 클래스가 Base 클래스를 상속한다.class Derived : publ..

• format_list_bulleted 프로그래밍 언어/C++
• · 2024. 8. 28.

추상자료형

정의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.

스코프

#1 스코프란?식별자가 유효한 범위자바스크립트 엔진이 식별자를 검색할 때 사용하는 규칙식별자란 어떤 값을 구별하여 식별할 수 있는 고유한 이름이다. 변수나 함수의 이름을 식별자라고 한다. #2 스코프의 종류전역과 전역스코프전역이란 코드의 가장 바깥영역이다. 전역에 변수를 선언하면 전역변수가 된다. 전역변수는 어디서든지 참조할 수 있다.지역과 지역스코프지역이란 함수 몸체 내부이다. 지역변수는 자신의 지역 스코프와 하위 지역 스코프에서 유효하다. #3 스코프 체인정의: 스코프가 계층적으로 연결 된 것스코프체인은 물리적으로 렉시컬환경(lexical environment)라는 자료구조로 구현된다.변수참조시 자바스크립트 엔진은 스코프체인에서 참조되는 위치부터 시작해서 상위 스코프 방향으로 이동하며 선언된 변수를 ..

• format_list_bulleted 프로그래밍 언어/JavaScript
• · 2024. 8. 25.

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

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

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 8. 19.