알고리즘

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

[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 ..

[Algorithm] 선형검색, 이진검색 알고리즘과 점근분석(Linear&Binary search)

선형검색, 이진검색 알고리즘이란? Linear&Binary search는 배열에서 특정한 값을 찾을 때 쓰는 검색 방법이다. 해당 글에서는 변수가 N 하나만 있다고 가정하고 작성할 것이다. 예를 들어 N = [1, 3, 8, 9, 4, 10, 6, 2] 라는 배열이 있다고 가정하겠다. 이 배열에서 나는 10이라는 값을 찾고 싶다. Linear search는 배열의 앞에서부터 value값이 10인지 아닌지 찾는다. 시간복잡도는 O(n)이다. 시간복잡도가 O(n)인 이유는 만약 내가 2라는 값을 찾고 싶다면 처음부터 끝까지 배열을 순회해야 하기 때문이다. Binary search는 배열의 중간값에서부터 시작한다. 우선 Binary search는 배열이 정렬된 경우에만 사용이 가능하다. N을 오름차순으로 정렬..

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

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