자료구조와 알고리즘/자료구조

[C# 자료구조] 동적 배열(List: C++vector와 유사함) 구현

Board 클래스 안에서 List를 써보고, 그 List의 동적 배열 로직을 직접 구현하는 코드 List using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Algorithm { class Board { public int[] _data = new int[25]; //배열 public List _data2 = new List(); //동적 배열 public LinkedList _data3 = new LinkedList(); //(이중)연결 리스트 public void Initialize() { _data2.Add(101); _data..

[C# 자료구조] 선형 자료 구조 ( 배열 vs 동적 배열 vs 연결 리스트)

public int[] _data = new int[25]; //배열 public List _data1 = new List(); //동적 배열 public LinkedList _data3 = new LinkedList(); //(이중)연결 리스트 **주의 C++과 혼돈될 수 있는데 C#에서의 List는 C++에서의 Vector, C#에서의 LinkedList는 C++에서의 List 각각 대응해서 비슷하게 짜여진 자료구조이다. 선형 구조는 자료를 순차적으로 나열한 형태 - 배열 - 연결 리스트 - 스택 / 큐 비선형 구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태 - 트리 - 그래프 1. 배열 (1) 장점 : 연속성(임의 접근 Random Access 가능) (2) 단점 : 사이즈 추가 / 축소 ..

[순환과 반복] 팩토리얼 계산 프로그램

팩토리얼을 순환, 반복 개념에 맞추어서 프로그램을 짜면 다음과 같다. 1. 순환 #include #include #include using namespace std; int factorial(int n) { cout

C# Queue와 Stack 특성을 LinkedList로 그대로 구현

Queue와 Stack은 LinkedList의 축소판이라고 할 수 있다. (선입선출, 후입선출 만을 구현할 때, 큐와 스택이 훨씬 직관적임.) list의 경우에는 stack을 구현하는데 어려움이 없으나, queue 구현에는 문제가 있다. 가장 앞 원소를 지우고 나면 뒤에 쌓인 원소들을 한칸씩 앞으로 미뤄야하는(이사시켜줘야하는) 작업을 추가해야하기 때문! 게임에서 Stack은 UI를 구현할 때 응용가능하다. 가장 마지막에 뜬 UI 창부터 사라지게 만들 수 있기 때문! queue 같은 경우는 네트워크 상 여러명의 유저가 한 몬스터를 타겟한다고 했을 때 가장 먼저 때린 유저의 타격부터 들어갈 수 있도록 타격값을 줄세우기 시킬 때 사용할 수 있을 것이다. namespace ConsoleApp1 { class P..

[C++]원형큐 구현, 줄서기 예시

큐는 가장 먼저 입력한 자료를 가장 먼저 출력하고 싶을 때 사용한다. 정류장에서, 사람들이 줄지어 서서 기다리다가 버스가 오면 순서대로 타는 예의범절을 생각하면 된다. 큐를 구현하는 기본 idea는 배열 내 head(처음 선 사람)와 tail(마지막에 선 사람) 인덱스을 잡고 enqueue(줄이 길어지는 상태) 할 때마다 tail++; dequeue(앞사람부터 버스에 타서 줄이 짧아지는 상태) 할 때마다 head++;을 하는 것이다. 하지만 배열을 아주 크게 잡지 않는 경우, 큐의 배열 크기 마지막까지 head가 도달하여 앞쪽의 빈 배열(head가 거쳐지나간)들을 재활용할 수 없어 메모리낭비가 심한 편이다. 그러므로 원형큐를 쓴다면 선형 큐에 비하여 동일한 배열이지만 꾸준하게 head가 거쳐지나간 인덱스..