Big-O notation 프로그램의 성능을 알기 위해선 입력 크기, 하드웨어 성능, 운영체제 성능 .... 등 고려해야할 것이 많다. 따라서 프로그램의 성능을 정확하게 파악하는 것은 불가능하다. 그래서 대략적인 성능을 비교하기 위한 상대적인 표기법(Big-O notation)을 사용한다. O(1)에서 O(log n) .... O(n!)로 갈수록 점점 시간이 오래 걸린다. O(log n)과 O(n)이 눈으로 봤을 때는 크게 차이가 없는 것 같지만 n이 1024일 경우 O(n)은 1024번 반복하지만 O(log n)은 10번만 반복하게된다. O(3n - 30)이나 O(3 log n)같은 시간 복잡도는 본적이 없을 것이다. 그 이유는 Big-O notation이 점근적 표기법을 따르기 때문이다. 점근적 표기..

1. 자료구조? 메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표로 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다. 특정 상황에서는 빠르게 작동하지만 반대로 특정 상황에서 느리게 작동할 수 있기 때문에 상황에 맞는 자료구조를 고를 수 있는 능력이 필요하다. 자료구조의 종류는 다음과 같이 있다. 선형 구조 한 원소 뒤에 하나의 원소 만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 가진다. 선형 구조에 해당되는 자료구조는 배열, 연결 리스트, 스택, 큐 등이 있다. 비선형 구조 원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절하다. 비선형 구조에 해당되는 자료구조는 트리와 그래프 등이 있다. 2. 알고리즘? 특정 ..

우리가 문제 해결 시에 사용하는 동적 계획법(DP) 또는 분할 정복과 같은 완전 탐색에 기초한 디자인 패러다임은 실생활에서 사용하기 매우 한정적이다. 예를들어, 인공지능 체스 프로그램을 브루트 포스 방식으로 짠다면 이동 가능한 모든 말의 움직임을 다 확인한다. 하지만 이 방법으로 개발한다면 말과 이동할 수 있는 칸이 너무 많기 때문에, 게임이 끝나지 않는다고 한다. (경우의 수가 10^120 가지) 결국 모든 경우의 수를 확인하지 않고도 답을 찾아낼 수 있는 방식을 사용해야 한다. 휴리스틱 알고리즘이란? 불충분한 시간이나 정보로 인해 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않을 경우 보다 빠르게 사용할 수 있는 추론의 방법이다. 기본적으로 가능성이 없는 답들을 탐색하는..

크루스칼 알고리즘 : 가장 적은 비용으로 모든 노드를 연결하기 위해 사용되는 알고리즘 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘입니다. ​ ※ 신장 트리 : 그래프 내의 모든 노드를 포함하는 트리 노드 = 정점 = 도시 : 그래프에서 동그라미에 해당하는 부분 간선 = 거리 = 비용 : 그래프에서 선에 해당하는 부분 ​ 위 그래프를 살펴보았을 때 6개의 노드와 8개의 간선이 있습니다. 해당 그래프를 크루스 칼 알고리즘을 적용시켜 본다면 아래와 같습니다. ​ 잠시 그래프에서 모든 노드를 연결하기 위해 최소한으로 필요한 간선의 수는 N( 노드) - 1개입니다. 즉 위 그래프는 노드가 6개 있으므로 최소 비용 신장 트리를 만들기 위해 필요한 간선의 수는 5개입니다. ​ 일단 모든 노드를 최대한 적은 ..

Union-Find ( 합집합 찾기) : 대표적인 그래프 알고리즘. 서로소 집합( Disjoint-Set) 알고리즘이라고도 한다. 여러 개의 노드가 존재할 때 두 개의 노드를 선택하여, 현재 두 노드가 같은 그래프에 속하는지 판별 -> Find와 Union 연산을 수행할 수 있다. ​ 위와 같이 여러 개의 노드가 자유분방하게 존재하고 있다고 했을 때, 이들은 모두 연결되지 않고 각자 자신만을 집합의 원소로 가지고 있을 때 아래와 같이 표현할 수 있다. 모든 값은 자기 자신을 부모 노드로 가지고 있습니다. 이때, 위와 같이 1과 2가 연결되었을 때, 표로 표현하였을 때 아래의 표로 나타납니다. 노드 번호 1 2 3 4 5 6 7 부모 노드 번호 1 1 3 4 5 6 7 2번째 인덱스의 값에 ' 1 ' 이 ..

깊이 우선 탐색 : 탐색을 할 때 깊이를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 ​ ' 맹목적으로 각 노드를 탐색 ' 할 경우 주로 사용하는 탐색 기법으로, 모든 노드를 방문하고자 하는 경우 ( 완전 탐색) 사용 너비 우선 탐색 ( BFS) 보다 지나온 경로를 쉽게 파악할 수 있다는 장점이 있다. 또 층별로 모든 자식 노드를 저장해야 할 필요가 없기 때문에 BFS에 비해 메모리 요구량이 훨씬 적다 ​ ※ 어느 방향으로 검색할지 확률에 따라 속도가 많이 빨라질 수도 있고 느려질 수도 있다.(확률 의존) ​ 깊이 우선 탐색을 수행하기 위해서 필요한 준비물은 Stack이다. 이다. ※컴퓨터는 구조적으로 스택의 원리를 사용하기 때문에 재귀 함수를 사용하여 구현이 가능하다. ​ 이제 어떤 식으로 정렬이 이루..

너비 우선 탐색 : 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 ​ ' 맹목적인 탐색 ' 을 하고자 할 때 사용할 수 있는 탐색 기법으로 ' 최단 경로 ' 를 찾아준다는 점에서 최단 길이를 보장할 때 많이 사용 ​ ※ 시작점과 거리가 멀수록 탐색이 느려진다. 하지만 근처에 있을 경우 빠르게 탐색 가능하다. ※ 맹목적인 탐색 : 이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 탐색하는 방법을 말한다. ​ 너비 우선 탐색을 하기 위해서 필요한 준비물은 Queue ( 큐 ) 이다. ​ 우선 어떤식으로 정렬이 이루어 지는지 보자면! 다음과 같이 1 2 3 4 5 가 서로 연결되어 있다고 보았을 때 너비 우선 탐색을 해보자면 시작 노드 ( Start Node ) 를 큐에 삽입..

Queue : 데이터를 일시적으로 저장하기 위한 자료구조 가장 먼저 들어온 데이터가 가장 먼저 나가는 자료구조 ( FIFO : First In First Out) ex) 은행 창구 : 먼저 번호표를 뽑은 사람이 먼저 서비스를 받는다. Queue를 코드로 구현해보자면 import java.util.LinkedList; public class QueueEx { public static void main(String[] args) { Queue s = new Queue(); for(int i = 1; i