자료구조 & Algorithm
-
알고리즘의 분석 : 시간 복잡도 & 공간 복잡도자료구조 & Algorithm 2011. 10. 12. 17:58
알고리즘의 효율성을 평가하는데 있어서 그 기준은 크게 2가지로 잡는다고 한다. 하나는 시간. 그리고 공간이 바로 그것이다. 간단하게 설명하면 시간 복잡도는 얼마나 빠르게 실행되느냐에 대한 것이고 공간 복잡도는 얼마나 메모리를 많이 차지하느냐에 대한 것이다. 가장 좋은 알고리즘은 시간은 적게 걸리고 메모리의 사용은 적어야 하는거겠지. 시간과 공간은 반비례 하는 경향이 있다. 요즘은 공간보다는 시간이 우선이다! 일반적으로 알고리즘의 분석(analysis of algorithm)이라 함은 알고리즘을 이루는 명령어들의 수행횟수를 계산하여 알고리즘의 시간 복잡도를 구하는 일을 일컫는다. 여기서 시간의 복잡도란 알고리즘을 구성하는 명령어들이 몇번이나 실행됬는지 센 결과(frequency count) + 각 명령어의..
-
JAVA로 구현한 입력된 문자열을 받아서 오름차순 버블 소트 하기자료구조 & Algorithm 2011. 10. 12. 16:04
버블 소트 버블 정렬 Bubble Sort Bubble Sort는 이웃한 두 원소를 비교하면서 정렬을 해나간다. 일반적으로 앞에서부터 정렬하여 값이 큰 원소를 뒤로 보낸다고 보면 된다. 즉 맨뒤부터 정렬이 이루어지는 것이다. 그림으로 보면 이해가 쉽다. 1. 인접한 두 원소를 비교하여 자리를 교환하는 작업을 첫 번째 원소부터 마지막 원소까지 차례로 반복하여 가장 큰 원소 69를 마지막 자리로 정렬한다. 2. 같은 작업을 수행하여 나머지 원소 중에서 가장 큰 원소인 31을 끝에서 두 번째 자리로 정렬한다. 3. 같은 작업을 수행하여 나머지 원소 중에서 가장 큰 원소인 30을 끝에서 세 번째 자리로 정렬한다. 4. 같은 작업을 수행하여 나머지 원소 중에서 가장 큰 원소인 22를 끝에서 네 번째 자리로 정렬한..
-
스택 계산기자료구조 & Algorithm 2011. 10. 12. 14:01
우리 인간은 2 - 9 * (4 + 3) 형태의 infix(중위표기법)를 사용한다. 하지만 컴퓨터는 postfix(후위표기법) 형태를 사용한다. 그리고 prefix(전위표기법) 라는 것도 있다. 요 3개의 형태를 살펴보면 다음과 같다. infix 는 4 * 3 postfix 는 4 3 * prefix 는 * 4 3 스택 계산기라는 것은 사용자에게 infix 형태의 문자열 수식을 입력 받아서 postfix 형태의 수식으로 바꾼 후 계산하는 것이라고 보면 되겠다. infix 를 postfix 로 바꾸는 방법을 간단히 살펴보면 5 - ( 3 * 4 ) / 3 + 10 이라는 식이 있다. 1. 먼저 이 식에 가능한 모든 괄호를 다 취한다. ( ( 5 - ( ( 3 * 4) / 3 ) ) + 10 ) 2. 각 괄..
-
C로 구현한 Quick Sort (퀵 정렬)자료구조 & Algorithm 2011. 10. 1. 22:20
퀵 소트는 다른 정렬 알고리즘에 비해 상대적으로 속도가 빠르고 큰 배열에 대해서도 잘 동작하기 때문에 가장 널리 사용되는 정렬 알고리즘이다. 큰 배열을 일정한 기준값을 경계로 하여 기준값보다 큰 값들과 작은 값들로 구성된 작은 두 개의 배열로 분할한다. 그리고 분할된 각 배열을 똑같은 방법으로 다시 정렬하는 점진적인 방법을 사용한다. 배열을 분할하기 위해 먼저 기준값을 선정하는데 여기선 배열의 마지막 값을 key값으로 잡았다. 그리고 for 루프에서 배열의 왼쪽과 오른쪽에 각각 left, right 포인터를 두고 중앙으로 이동하면서 left에 기준값보다 큰 값, right에 기준값보다 작은 값을 찾는다. 그리고 두 값을 교환하여 기준값보다 작은 값은 배열의 왼쪽으로 보내고 큰 값은 오른쪽으로 보낸다. 이..
-
Binary Search - 이진 검색자료구조 & Algorithm 2011. 10. 1. 16:24
이진 검색은 범위를 계속 절반씩 줄여 가면서 검색하기 때문에 자료의 양이 커도 비교 회수가 많이 않은 것이 장점이다. 베열의 크기가 n일 때 최악의 경우라도 log2n 번 비교하면 원하는 값을 찾을 수 있다. 극단적인 경우 n이 40억이라 하더라도 기껏 32번만 비교하면 되므로 순차 검색과는 비교할 바가 아니다. 이진 검색이 이렇게 속도가 빠른 이유는 자료가 크기순으로 정렬되어 있기 때문이다. 그래서 이진 검색에 사용할 자료는 삽입할 때도 반드시 이 조건을 지키도록 해야 한다. 처음부터 순서대로 검색하는 것이 아니라 중간 부분을 쿡쿡 찔러보는 식이므로 키값이 중복될 경우 어떤 키가 검색될지 알 수 없는 맹점이 있다. 위 예에서 키를 21로 바꿀 경우 두 개의 21중 어떤 값이 검색될 것인가를 예측할 수 ..