c++

[Algorithm] 코드 블럭 단위 복잡도 분석

개요 코드 블럭은 C++일수도 있고, 수도코드, 의사코드 일수도 있다. 점근적으로 n이 커질 때, 점근적 런타임과 점근적 메모리 문제의 크기를 설명하는 변수, n이던 아니던 vertex의 개수던 edge의 개수던 이런 parameter를 표현하는 것이 첫번째 단계이다. 알고리즘의 asymptotic behavior은 이 알고리즘이 n이 커졌을 때, 문제의 크기가 커졌을 때 어떻게 행동하는지, 과연 이 알고리즘이 n이 아주 큰 상황에서도 잘 동작하는지에 대한 정보를 제공한다. 예를 들어 A는 세타오브 n square이고 B는 n log n일 때 n의 값이 2k일 때는 A의 경우 4k square B의 경우 2k log k + 2k 이다. 하지만 2k에서 10k로 5배 증가시킨다면 A의 요구시간은 5 * 5..

[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) 기본 개요 반드시 알고 있어야 하는 알고리즘 중 하나인 그래프 탐색 알고..

[자료구조] 스택과 큐를 이용하여 회문 판별 프로그램 만들기(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 앞서..