Algorithm

[ 알고리즘 ] 해시 테이블 ( Hash Table )

해시 테이블 Hash table ( hash map ) 이란 해시함수를 사용해서 변환한 값을 index 로 삼아 key 를 value 로 매핑하는 자료 구조를 의미한다. 해시 테이블은 다음과 같은 특징을 가진다. Key 값으로 Value 값을 찾을 수 있기 때문에, 매우 빠른 검색 속도를 가지고 있다. 특정 키값을 알면 value 값이 나오기 때문에 키 값은 Unique 해야한다. Key - value 의 1대1 매칭구조이기 때문에 삽입, 삭제, 검색 모두 평균적으로 충돌이 없는 경우 O(1) 의 시간 복잡도를 가짐 해시 함수 Hash Code 를 만들어주는 함수 MD5, SHA 가 대표적이다. 보통 1비트 값만 바뀌어도 값이 크게 바뀌는 눈사태 효과를 가지고 있다. ( 보안과 관련 ) 해시 테이블의 장..

[ 알고리즘 ] 스택, 큐

스택 ( Stack ) vs 큐 ( Queue ) 스택과 큐는 자료 구조의 형태이며, 서로 상반되는 형태를 가진 자료 구조이다. 둘이 어떤 차이가 있는지 한번 살펴보도록 하자 스택 ( Stack ) 스택이란 쌓는다는 것을 의미한다. 예를 들어 책을 박스에 쌓어서 창고에 보관하려고 했는데 내가 보려고 뒀던 책을 상자에 실수로 넣었으면 넣은 순서의 반대로 하나 하나 꺼내서 책을 찾아야 할 것이다. 상자에 차곡 차곡 쌓인 책을 꺼낼때 밑에서 부터 꺼낼수 없듯이 마지막에 넣은 자료가 가장 먼저 꺼내지는 특징을 가진 구조이다. 이러한 스택의 구조는 후입선출 ( LIFO ) 구조라고 한다. 상자에 책을 쌓는, 스택에 값을 삽입하는 연산을 Push, 상자에서 책을 꺼내는, 스택에 값을 삭제하는 연산을 Pop 이라 한..

[ 알고리즘 ] 그래프, 트리

그래프 트리 방향성 방향, 무방향 방향 사이클 순환, 비순환, 자기순환(self-loop) 비순환 루트노트 루트 없음 한개의 루트 노드 부모- 자식 부모-자식 개념 없음 1:N 의 부모-자식 관계 모델 네트워크 모델 계층 모델 간선 수 자유 N-1개 그래프 그래프란 노드 ( Node ) 와 간선 ( Edge ) 를 하나로 모아둔 자료 구조로, 연결되어 있는 객체들간의 관계를 나타내는 자료 구조이다. 그래프는 다음과 같은 특징을 갖는다. 그래프는 노드 ( 정점 Vertex 라고도 함), 간선 ( Edge ) 로 이루어져 있으며 간선이 화살표인 경우에는 방향성을 띄게 된다 이를 유향 그래프라고 하고, 화살표가 없는 경우는 무향 그래프라고 한다. 간선에 특정한 수치를 가질 수 있는데 이를 가중치 ( Weigh..

[ 알고리즘 ] 이진 탐색 ( Binary Search )

이진 탐색 ( Binary Search ) 업 앤 다운이라는 게임이 있다. 이 게임의 룰은 사회자가 1~100 사이의 숫자를 정한 뒤 그 숫자를 돌아가면서 맞추는 게임으로 부른 숫자가 사회자가 부른 숫자보다 낮으면 Up, 부른 숫자가 사회자가 부르는 숫자보다 높은 숫자면 Down 이라고 해서 그 숫자를 맞추는 게임이다. 이 게임에서 가장 빠른 방법은 당연히 운빨로 한번에 맞추는거겠지만, 평균에 수렴하게 되면 가장 빠르게 답을 찾을 수 있는 방법은 절반값을 계속 불러서 답을 찾아가는 방식이다. 이런식으로 값을 찾아가는 방식이 바로 이진 탐색 방식이다. 이 방식을 사용하면 100에서 값을 찾는데 걸리는 최악의 경우 logn ( 이진 로그) 으로 6.64 정도, 아무리 최악의 상황에도 7번 안에 답을 찾을 수..

[ 알고리즘 ] 배열과 링크드 리스트

배열 연결 리스트 크기 고정 크기 ( 처음 선언 값 ) 동적 사이즈 ( 데이터 삽입 / 삭제에 따라 증감 ) 요소 접근 O(1) : 인덱스를 이용 O(n) : 주소값을 이용 삽입/삭제 (Head) O(n) O(1) 삽입/삭제 ( Tail ) O(1) O(1) 삽입/삭제 ( 중간 ) O(n) O(1) / 탐색 시간 O(n) 배열 ( Array ) 배열은 연속된 메모리 공간에 같은 타입의 데이터를 할당하는 선형 자료 구조이다. 배열의 크기는 선언 시점에서 정해야하며 int Five_grade[30] = {1,2,3,4,5 ..} 배열 생성 시, 선언한 크기만큼의 메모리가 할당된다. 예를 들자면 학교의 출석부 같은 구조라고 할 수 있다. 처음 반을 등록할 때 출석부라는 이름의 메모리에 30번 까지 준비(할당)..

[ 알고리즘 ] 시간 복잡도와 공간 복잡도에 대하여

시간 복잡도 ( Time complexity ) 프로그램이 실행될 때, 입력값과 연산 수행 시간의 상관 관계를 나타내는 척도. 보통 점진적 표현법을 사용함 시간 이름 사용하는 알고리즘 O(1) 상수 시간 ( Constant time) index 를 사용해 데이터 찾기, Push, Pop O(log n) 로그 시간 ( Log time ) 이진 탐색 ( Binary Search ) O(n) 선형 시간 ( Linear time ) 선형 검색 O(n log n) 선형 로그 시간 ( Log Linear time ) 퀵 정렬, 병합 정렬, 힙 정렬 O(n2) 제곱 시간 ( Quadratic time ) 이중 For 문, 삽입 정렬, 버블 정렬, 선택 정렬 O(2n) 지수 시간 ( Exponential time ) ..