자료구조

[Algorithm] BFS,DFS 알고리즘 구현(C++)

본 글에서는 IDE로 DEV C++을 사용하였다. 그래프 만들기 보통 그래프를 입력받을 때에는 파일로 받는 경우가 많다. 본 글에서는 txt파일을 사용하였다. graph_1이라는 txt파일을 만들었다. 맨 위의 13은 vertex의 개수이고 12는 edge의 개수이다. 밑의 영어들은 트리 구조의 그래프이다. 해당 파일은 프로젝트 내부에 위치해야 한다. 구현 먼저 코드 블럭 단위로 리뷰를 할 것이다. 리뷰 순서는 앞선 글에서의 실행 순서와 같다. 2023.01.29 - [CS/알고리즘(Algorithm)] - [Algorithm] 그래프 탐색 알고리즘(BFS, DFS) 기본 [Algorithm] 그래프 탐색 알고리즘(BFS, DFS) 기본 개요 반드시 알고 있어야 하는 알고리즘 중 하나인 그래프 탐색 알고..

[Algorithm] 그래프 탐색 알고리즘(BFS, DFS) 기본

개요 반드시 알고 있어야 하는 알고리즘 중 하나인 그래프 탐색 알고리즘이다. 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)이 있다. 그래프가 Connect 상태인지, Unconnect 상태인지 확인하기 위해 사용한다. 선행 지식으로 큐, 스택, 트리, 그래프 자료구조의 이해가 필요하다. 2022.12.30 - [CS/자료구조(data structure)] - [자료구조] 큐(Queue)란? [자료구조] 큐(Queue)란? 개요 큐(Queue)는 선입선출(First-In Firut-Out) 방식의 선형 자료구조이다. 모양은 사람들이 줄을 서있는 모습을 생각하면 이해가 편하다. 구조 큐는 위의 모양과 같은 구조를 가진다. enqueue : 아이템을 mk-develop.tistory.com 2022.12..

[Algorithm] 점근 표기법

세타 표기법(Theta-Notation) 세타 표기는 상한과 하한을 모두 알고 있을 때 사용하는 표기법이다. 조건식은 다음과 같다. 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) f(n)을 기준으로 f(n)을 표현하고자 하는 대표값 g(n)을 놓고 보았을 때, g(n)에 어떤 상수를 곱하고 다른 어떤 상수를 곱한 것이 있을 때, f(n)은 반드시 샌드위치처럼 끼어 있어야 한다. 해당 조건식에서 상수는 c1, c2 이다. n이 n0보다 높은 시점에서 f(n)은 항상 c1g(n)보다는 높고 c2g(n)보다는 작다. 이를 'f(n)은 g(n)과 같은 증가속도를 가진다.' 라고 하며 f(n)은 theta of g(n)에 속한다 라고 한다. g(n)은 f(n)의 점근적 상한 및 하한(asymptotically ..

[자료구조] 트리(Tree) 기본

개요 트리는 노드들의 계층 관계를 표현한 집합체이다. 모양은 침엽수와 같은 나무를 거꾸로 매달아 놓은 것처럼 생겼는데 이제부터 사진들과 함께 알아 볼 것이다. 트리는 종류가 많은데, 해당 글에서는 트리의 정말 기본적인 내용만 다룰 것이다. 규칙 1. 최상위 레벨에 있는 노드는 루트라고 하며 진입 차수가 0이다. 루트 노드는 트리마다 하나밖에 존재하지 않는다. 2. 모든 노드는 0, 또는 n개의 자식 노드를 가진다. 3. 모든 노드는 하나 이상의 부모 노드를 가진다. 4. 트리는 level을 가진다. 가장 꼭대기에 있는 루트 노드는 레벨이 0이며 트리의 루트로부터 특정 vertax까지의 경로 길이로 결정된다. 5. 루트 노드로부터 특정 노드까지의 경로는 반드시 1개만 존재한다. 6. 만약 트리가 루트 뿐이..

[자료구조] 스택과 큐를 이용하여 회문 판별 프로그램 만들기(C++)

https://mk-develop.tistory.com/5 [자료구조] 스택(Stack)이란? 개요 Stack 자료구조란 요소들이 후입선출(Last-In First-Out)되는 방식의 자료구조이다. 말 그대로 가장 늦게 들어온 요소가 가장 처음으로 나간다. 구조 스택은 기본적으로 사진 1과 같은 구조를 가 mk-develop.tistory.com https://mk-develop.tistory.com/6 [자료구조] 큐(Queue)란? 개요 큐(Queue)는 선입선출(First-In Firut-Out) 방식의 선형 자료구조이다. 모양은 사람들이 줄을 서있는 모습을 생각하면 이해가 편하다. 구조 큐는 위의 모양과 같은 구조를 가진다. enqueue : 아이템을 mk-develop.tistory.com 앞서..

[자료구조] 스택(Stack)이란?

개요 Stack 자료구조란 요소들이 후입선출(Last-In First-Out)되는 방식의 자료구조이다. 말 그대로 가장 늦게 들어온 요소가 가장 처음으로 나간다. 구조 스택은 기본적으로 사진 1과 같은 구조를 가진다. 아래에서부터 요소가 쌓이며 Top 포인터는 가장 위에 있는 요소를 가르킨다. operation으로는 대표적으로 Push와 Pop이 있다. Push operation은 스택에 아이템을 추가한다. 사진 2는 사진 1에서 5를 push했을 때의 예시 사진이다. Pop operation은 스택에서 아이템을 제거한다. 사진 3은 사진 2에서 5를 pop하는 예시이다. 사진 2와 3에서, Top 포인터가 가르키는 위치는 항상 스택의 맨 위 임을 알 수 있다. 어디에서 사용하는가? 위 사진은 VS co..

[자료구조] 연결리스트(Linked List)란?

개요 Linked List란 모든 노드들이 자신의 값과 나의 다음 값을 pointing하는 자료구조이다. 왜 사용하는가? 해당 자료구조를 왜 사용하는지 간단한 예시를 들겠다. 예를 들어, 이러한 모양의 배열이 있는데 현재 나는 4와 6 사이에 5라는 값을 넣고 싶다. 이럴땐 어떻게 해야할까? 사진 2와 같이 6과 8을 오른쪽으로 밀어서 공간을 확보한다. 공간을 확보한 후 5를 insert 한다. 얼핏 보면 이게 당연한 것처럼 느껴질 수 있다. 하지만 해당 방법은 굉장히 비효율적이다. 이러한 번거로움을 해결하기 위한 자료구조가 Linked List 즉 연결리스트이다. Linked List의 구조 Linked List는 하나의 메모리 공간(Node)에 데이터와 포인터를 저장한다. 그렇다면 이 자료구조를 사용..

[자료구조] C언어 Pointer에 대하여

개요 알고리즘은 선행 지식으로 자료구조에 대한 이해를 필요로 한다. 자료구조의 경우엔 포인터에 대한 사전 지식이 있다면 이해하기 좋다. 본 글에서는 C언어의 포인터 변수에 대한 아주 기초적인 내용을 다룬다. Pointer란? C언어에서 포인터는 '메모리의 주소를 저장하는 변수' 이다. '&' operator는 어떤 변수의 주소를 받아올 수 있다. '*' operator는 참조한 값을 다시 역으로 따라간다. 포인터는 기본적으로 4byte를 할당받는다. 이렇게 설명하면 어려울 수 있으니 예제코드와 함께 설명하겠다. #include int main() { char a = 'A'; char* pointer = &a; printf("%c %p\n", a, pointer); printf("%p %p\n", &a, ..