'자료구조와 알고리즘' 카테고리의 글 목록

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

2022.02.04

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 연결 리스트)

2022.02.03

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) 단점 : 사이즈 추가 / 축소 ..

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

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

2022.01.31

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

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

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

2022.01.25

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

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

소수 빠르게 찾기, sqrt (), 에라토스테네스의 체 + pow()

2022.01.09

공략법 : TargetNum이 소수인지 아닌지 확인하고 싶다면, (1) TargetNum의 sqrt ()로 제곱근을 구하여 약수를 2부터 루트TargetNum까지만 검토한다. (2) 에라토스테네스의 체 개념을 이용하여 for문을 돌면서 특정 i의 배수를 전부 지워나간다. (1) 제곱근까지 약수 범위를 줄인 경우 -> 정상적으로 소수가 출력됨 #include #include using namespace std; bool isPrimeNumber(int x) { int end = (int)sqrt(x); for (int i = 2; i

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

이진탐색 핵심코드

2022.01.04

재귀를 활용한 이진탐색의 핵심 개념이 되는 코드 def Search(start,end,target): if start==end: //~~ return mid = (start+end)/2 if nums[mid]

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

BFS 코드

2021.12.27

bfs 함수에서는 (1) push()하자마자 check=true로 만들어주고 (2) 큐가 비어있지 않는 한 계속 반복할때마다 front()를 pop() 해주는 것이 꽤나 중요해보인다. 그러다보니 첫노드는 그야말로 큐에 들어가자마자(push) 빠져나오게(pop)게 된다. main 함수에서는 차분하게 인접리스트를 구현해야한다. #include #include #include using namespace std; vector numbers[7]; int check[7]; void bfs(int start) { queue que; que.push(start); check[start] = true; while (!que.empty()) { int x =que.front(); que.pop(); cout

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

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

2021.12.15

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

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

배열 회전, 정적 배열 내에서 특정 원소를 선택한 위치로 이동하고 싶을 때

2021.12.15

배열 정보와 인덱스 정보가 두개가 필요하다. 특정 원소의 원래 인덱스와 원소를 보내고 싶은 위치의 인덱스이다. 그리고 두 인덱스 사이를 for문으로 돌면서 배열을 한칸씩 당겨줘야하는 다소 번거로운 작업이 필요하다. 아래 코드는 8번째 숫자를 2번째 위치로 보내고 싶다고 가정하고 작성한 것이다. #include #include using namespace std; void ratate(array& arr, int wantPos, int target) { int last = arr[t]; for (int i = t; i > s; i--) { arr[i] = arr[i-1]; } arr[s] = last; } int main() { array arr = {1,2,3,4,5,6,7,8,9,10}; ratate(..

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

[c++] 삽입 정렬

2021.09.21

삽입 정렬이란 숫자를 원하는 위치를 찾아가서 삽입하는 정렬이다. 필요한 만큼만 움직여서 시간 복잡도는 n의 제곱이라는 점에서 동일할지라도 연산수가 적으므로 버블 정렬이나 선택 정렬보다 빠르다. 2 6 4 9 8 1 3 5 7 라는 9개의 숫자를 한 배열에 담고 삽입 정렬을 활용해 오름차순으로 바꾸는 시뮬레이션을 해보자. 제일 앞 숫자를 0번째 인덱스, 마지막 숫자를 8번째 인덱스라 가정한다. 2 6 4 9 8 1 3 5 7 //2 6 -> 4->2 모두 반복문으로 비교하다가 맨 앞 정착 ) 1 2 4 6 8 9 3 5 7 //현재 상황(불완전하지만 정렬이 차츰 되고 있음) 1 2 _ 4 6 8 9 '3' 5 7 //3을 4 앞에 넣자. (9-> 8-> 6-> 4 모두 반복문으로 비교하다가 4 앞 정착) ..

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

자료구조와 알고리즘

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

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

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

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

소수 빠르게 찾기, sqrt (), 에라토스테네스의 체 + pow()

이진탐색 핵심코드

BFS 코드

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

배열 회전, 정적 배열 내에서 특정 원소를 선택한 위치로 이동하고 싶을 때

[c++] 삽입 정렬

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역