데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복 기법으로 특정한 값을 찾아내는 알고리즘 이진 탐색 알고리즘 동작 원리 Up&Down 게임과 흡사하다 정렬된 배열의 가장 중간 인덱스를 지정한다 찾으려고 하는 값이 지정한 중간 인덱스의 값이라면 탐색을 종료한다 찾으려고 하는 값이 중간 인덱스의 값보다 큰 값인지, 작은 값인지 확인한다 값이 있는 부분과 값이 없는 부분으로 분리한다 값이 있는 부분에서 다시 1단계부터 반복한다 장점 ( 주 사용처) 사전 검색, 도서관 도서 검색, 대규모 시스템에 대한 리소스 사항 파악 등 탐색을 반복할 때마다 탐색 범위가 절반으로 줄어들게 되는 이 알고리즘은 데이터 양이 많을수록 더 높은 효율을 가지게 된다 정렬된 배열에서 요솟값을 더 효율적으로 검색할 때 사용 데이터의..
모든 값을 대입하는 방법 컴퓨터 과학에서 Brute Force는 시행착오 방법론을 말한다 암호학에서는 Brute Force Attack이라고 한다 이는 특정한 암호를 풀기 위해서 모든 값을 대입하는 방법을 말한다 쉽게 말해, 암호를 모르는 0-9 사이의 4자리 숫자로 된 자물쇠가 있다고 했을 때, 이 자물쇠의 비밀번호를 풀기 위해서 0000부터 9999까지의 모든 경우의 수를 대입하여 푸는 방법이다 Brute Force Algorithm의 의미 무차별 대입 방법을 나타내는 알고리즘 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도 공간 복잡도와 시간 복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법 Brute Force Algorithm이 사용될 때 프로세스 속도를 ..
탐욕스러운, 욕심 많은 Greedy Algorithm은 매 순간, 최적이라 생각되는 해답을 찾으며, 이를 토대로 최종 문제의 해답에 도달하는 문제 해결 방식 문제 해결 절차 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복 마시멜로 실험 지금 마시멜로를 받겠다고 하면 1개를 받을 수 있지만, 1분을 기다렸다가 받는다면 2개를 받을 수 있다. greedy는 지금 당장에 최선인 선택을 하기 때문에 지금을 선택하여 1개를 받지만, 전체적으로 보면 ..
시간 복잡도 필요로 하는 시간을 따지는 것 : 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는가? BIig-O 표기법 시간 복잡도를 표기하는 방법은 3가지가 있다 Big-O (빅-오) - 최악 : "최대 이 정도까지 시간이 걸린다" Big-Ω (빅-오메가) - 최선 : "최소한 특정 시간 이상이 걸린다" Big-θ (빅-세타) - 평균 : "보통 이 정도 시간이 걸린다" 이 중 Big-O 표기법이 가장 자주 사용된다 다른 방법처럼 최악의 경우가 일어나지 않기를 바라는 것보다는 최악의 경우도 고려하여 대비하는 것이 바람직하다 O(1) 입력값의 크기와 관계없이 같은 시간이 걸린다 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다 pub..
Deque (Double Ended Queue, 양방향 대기열) Deque는 Stack과 Queue의 특성들이 혼합된 느낌이다 Stack : 데이터가 한 방향으로 추가되고 삭제할 수 있음 Queue : 데이터가 한방향으로 추가되고 다른 방향으로 데이터가 삭제됨 자료구조 스택 Stack Stack 데이터를 순서대로 쌓는 자료구조 가장 먼저 들어간 데이터가 가장 나중에 나올 수 있다 그림과 같이 길이 막혀 더 이상 진행할 수 없는 경우 분홍색 자동차가 가장 먼저 들어왔지만 뒤 차 e-room.tistory.com 자료구조 큐 Queue 큐는 줄을 서서 기다리다, 대기행렬이라는 뜻이 있다 가장 먼저 들어온 데이터가 먼저 나갈 수 있다 고속도로 톨게이트는 가장 먼저 도착한 자동차가 먼저 통과할 수 있다 분홍색 ..
여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조 복잡한 네트워크망과 같은 모습 Graph의 구조 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다 하나의 점을 그래프에서는 정점(vertex)이고, 하나의 선은 간선(edge)이라고 한다 용어 정리 정점 (vertex) : 노드라고도 하며 데이터가 저장되는 그래프의 기본 원소 간선 (edge) : 정점 간의 관례를 나타낸다 인접 정점 (adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점 가중치 그래프 (weighted graph) : 연결의 강도가 얼마나 되는지 적혀있는 그래프 비 가중치 그래프 (unweighted graph) : 연결의..
나무의 형태를 가지고 있다 하나의 뿌리로부터 가지가 사방으로 뻗은 형태이다 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다 데이터를 순차적으로 나열시킨 선형 구조가 아닌, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다 노드(Node) : 트리 구조를 이루는 모든 개별 데이터 루트(Root) : 트리 구조의 시작점이 되는 노드 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드 Tree의 구조 깊이 (depth) 루..
큐는 줄을 서서 기다리다, 대기행렬이라는 뜻이 있다 가장 먼저 들어온 데이터가 먼저 나갈 수 있다 고속도로 톨게이트는 가장 먼저 도착한 자동차가 먼저 통과할 수 있다 분홍색 자동차가 가장 먼저 도착했기 때문에 가장 먼저 통과하며 파란색 자동차는 앞의 자동차들이 모두 빠져나갈 때까지 기다려야 한다 큐도 마찬가지로 가장 먼저 입력된 데이터가 첫 번째로 출력된다 (가장 나중에 입력된 데이터는 마지막에 출력된다) Queue의 특징 FIFO (First In First Out) 먼저 들어간 데이터가 처음에 나오는 선입선출의 구조를 가지고 있다 데이터는 하나씩 넣고 뺄 수 있다 두 개의 입출력 방향을 가지고 있다 (데이터의 입력, 출력 방향이 다르다)
Stack 데이터를 순서대로 쌓는 자료구조 가장 먼저 들어간 데이터가 가장 나중에 나올 수 있다 그림과 같이 길이 막혀 더 이상 진행할 수 없는 경우 분홍색 자동차가 가장 먼저 들어왔지만 뒤 차가 모두 빠져야만 나갈 수 있다 가장 먼저 들어간 자동차는 가장 나중에 나올 수 있다(= 가장 나중에 들어간 자동차가 가장 먼저 나올 수 있다) Stack의 특징 LIFO (Last In First Out) 먼저 들어간 데이터는 나중에 나오는 후입 선출의 구조를 가지고 있다 데이터는 하나씩 넣고 뺄 수 있다 하나의 입출력 방향을 가지고 있다 (제한적 접근)
