-
0x03.탐색 알고리즘:선형 탐색0x.알고리즘 2017. 2. 21. 10:20
탐색 알고리즘 레코드(record)는 임의의 객체에 대한 정보를 나타내는 다수의 필드(field)로 구성되어 있는데, 여러 개의 레코드를 명확하게 구별할 때 사용되는 키(key) 필드도 이에 포함된다.(레코드의 구조체로는 파일(file)과 테이블(table)이 있다.) 탐색이란 어떤 키 K를 가진 레코드가 파일 상에 있는지 조사하는 절차로, 탐색을 요청할 경우에 기입하게 되는 것이 키이고, 탐색 후의 출력 결과가 레코드의 위치가 된다. 컴파일러의 경우 식별자 이름이 키가 되고, 식별자에 붙어있는 여러가지의 정보를 포함한 것이 레코드가 된다. 탐색을 하기 위해서는 키에 대한 조건을 지정해야 하는데, 다음과 같이 세부적으로 나눌 수 있다.(파일상에 존재하는 모든 레코드가 갖는 키가 각자 다르다는 전제가 필요..
-
0x02.알고리즘(3):스택&큐&트리0x.알고리즘 2017. 2. 20. 14:09
3.스택(stack) 스택은 메모리관련 개념으로 많이 접할 수 있다. 스택의 어원은 건초더미로 알려져 있는데, 농부들이 건초들을 한 곳에 모을 때 차곡차곡 쌓이는 모습과, 그것들을 사용하기 위해 위에서부터 조금씩 덜어가는 모습을 본따 지었다고 한다. 속된 말로, 빨리 들어온 놈보다 늦게 들어온 놈이 먼저 선택된다는 뜻이다. 이 성질을 유식한 말로 LIFO(Last-In-First-Out)이라고 하기도 한다. 스택은 연산 시 중간 결과를 잠시 기록할 때 주로 사용되는데, 다음은 스택이 산술식을 계산하는 과정이다. 아래에서 사용된 방식은 역 폴란드(Polish Postfix) 표기방식인데, 이는 연산자들이 자신의 피연산자들의 직후에 위치하도록 하는 방법으로, 데이터가 숫자이면 스택에 추가하고, 연산자이면 스..
-
0x01.알고리즘(2):배열&연결 리스트0x.알고리즘 2017. 2. 19. 23:59
1. 배열(Array) 데이터를 하나의 순서로 나열한 것을 선형 리스트(linear list) 또는 열(sequence)라고 하는데, 주로 배열과 연결 리스트를 사용한다. 그 중에 배열은 메모리에 연속으로 데이터를 나열할 때 주로 사용하는데, 직접 접근에 용이하여 각 요소를 참조하는데 시간이 적게 걸린다는 장점이 있다. int element[size]; 하지만 연속된 특징 때문에 특정 열에 새로운 요소를 삽입할 경우, 그 장소를 비우기 위해 요소를 이동시켜야 되는 불편함이 있다. 장소 : p, 데이터 : val void insert(int p, int val){ int i; for(i=length; i>=p; inext; } 아까 언급하였지만, 연결 리스트의 핵심은 쉬운 데이터 삽입과 삭제이다. 다음의 ..
-
0x00.알고리즘0x.알고리즘 2017. 2. 18. 22:48
알고리즘 알고리즘이란 어떤 문제를 해결하기 위한 절차를 기술해 놓은 것이다. (여기서의 절차는 어떤 작동을 어떤 순서로 할 것인가를 나열한 것을 말함) 알고리즘의 특성으로는 다음과 같이 4가지가 있는데, 모두 충족을 시켜야 한다! 1. 엄밀성(Preciseness) 기술된 내용은 한 가지 이상의 의미를 포함하지 않음 2. 실효성(Effectiveness) 주어진 상황에 영향을 주어서 실제로 상황을 변화시키는 효과가 있어야 함 3. 입출력(Input/Output) 입력이 주어지고, 그에 따른 출력이 있어야 함 4. 종료성(Termination) 기술된 절차는 반드시 종료상태에 도달해야 함 알고리즘의 간단한 예로 유클리드 호제법을 들어보자. (쉽게 말해서 두 수의 최대공약수를 구하는 공식임.. 느낌오시죠?)..