프로그래밍
-
[자료구조] 8강 동적 연결된 스택과 큐~ 연결리스트프로그래밍/자료구조 2014. 4. 22. 04:51
동적 연결된 스택과 큐 순차 표현방법은 스택이나 큐가 하나만 있을 때는 효율적이나 여러 개의 스택이나 큐가 동시에 있을 때 이들을 순차적으로 표현할 효율적인 방법이 X , 이 경우에는 연결 리스ㅡ로 표현을 하여 스택은 top pointer로 첫 번 째 노드를 가리키게 하고, 큐의 경우에는 첫 번째와 마지막 노드를 front와 rear pointer가 가리킴으로써 삽입/삭제가 가능하도록 할 수 있다. 비사용 기억 공간 1. 순차 가용 공간에서의 노드 획득2. 초기 가용 공간에서의 연결 리스트 생성3. 연결 리스트 가용 공간에서의 노드 획득4. 연결 리스트로 된 가용 공간에 삭제 노드의 반환 연결 리스트의 응용 1. 다항식의 단순 연결 리스트 표현2. 다항식의 덧셈3. 단순 연결 리스트로 표현된 다항식의 노..
-
[자료구조] 7강 1-2절 연결리스트의 필요성 ~ 단순 연결 리스트프로그래밍/자료구조 2014. 4. 22. 04:50
연결 리스트의 필요성 순서 리스트는 배열을 이용하여 구현 -> 메모리 사용 측면에서의 비효율적인 문제점이 나타난다.순서리스트에서 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간이 소요되는 점이 가장 큰 부담-> 따라서 순서리스트에서 나타나는 문제점을 개선할 자료표현방법이 필요 순서리스트에서 원소의 삽입과 삭제시 빈번한 자리이동으로 복잡도가 증가하고 부담이 증가.이미 사용중인 크기를 변경하고자 하는 경우에는 연속적인 공간의 여유가 있는 경우에서는 문제가 되지 않지만 사용 중인 공간 이후에 여유 공간이 부족하면 기억공간에서 확장할 크기를 포함하는 기억 공간을 다시 할당 받아야하는 문제가 발생한다.연속적인 자료에 대한 추가,삭제가 빈번하다면 순서 리..
-
[자료구조] 6강 3장 스택과 큐 - 4절 스택의 응용프로그래밍/자료구조 2014. 4. 17. 19:03
6강 3장 스택과 큐 - 4절 스택의 응용 *연산자의 우선순위연산자를 괄호를 묶을 경우 우선순위가 달라진다.연산자 우선순위에 따라 연산하는 과정은 스택을 이용하여 표기하기도 함 *수식의 표기법전위 표기식 : 연산자를 피연산자의 앞에 표기하는 방법예: +AB중위 표기식 : 연산자를 피연산자의 가운데에 표기하는 방법예: A+B후위 표기식 : 연산자를 피연산자의 뒤에 표기하는 방법예: AB+ *수식의 표기법중위 표기식 표현A/B+C-D*E전위 표기식 표현-+/ABC*DE후위 표기식 표현AB/C+DE*- *중위 표기를 후위 표기로 변환스택의 응용 분야 : 중위 표기를 후위 표기로 변환하기 위한 용도수식의 연산자에 대해서 우선순위에 따라 괄호를 표현각 연산자를 그에 대응하는 오른쪽 괄호 뒤로 이동괄호를 제거 *다..
-
[자료구조] 5강 3장 스택과 큐 - 2절 큐프로그래밍/자료구조 2014. 4. 17. 17:39
5강 3장 스택과 큐 - 2절 큐 *큐의 정의리스트의 한쪽 끝에서 원소를 삽입, 다른 한쪽 끝에서는 원소의 삭제가 일어나는 구조가장 먼저 삽입된 원소가 가장 먼저 삭제된다고 해서 선입선출(FIFO : First In First Out) 구조 *데크리스트의 양쪽에서 삽입/삭제스택과 큐를 혼합한 구조데크의 종류에는 입력 제한 데크(스크롤), 출력 제한 데크(셀프)가 있다. *요점정리큐는 FIFO 선입선출큐의 삽입 및 삭제 과정 – Front pointer, Rear pointer선형 큐의 문제점을 보완하기 위한 원형큐큐의 적용 분야들 – 작업 스케줄링리스트의 양쪽에서 입출력이 가능한 데크 (입력제한, 출력제한 데크) 순서 있는 리스트- 삽입 연산은 한쪽 끝에서일어난다(rear라고 부른다)-삭제 연산은 삽입의..
-
[자료구조] 4강 3장 스택과 큐 - 1절 스택프로그래밍/자료구조 2014. 4. 17. 16:33
3장 스택과 큐 - 1절 스택 * 스택의 정의스택 : 선형 자료 구조의 한 종류비선형 구조 : 트리, 그래프선형 구조 : 스택, 리스트, 배열 (각각의 원소들이 순서를 가지고 있다)선형 자료 구조의 한 종류원소의 삽입과 삭제가 리스트의 한쪽 끝에서만 이루어지는 구조가장 마지막에 삽입된 원소가 가장 마지막에 삭제되는 구조로서 후입선출(LIFO: Last In First Out)구조삽입(push) : 스택에 원소를 삽입하는 과정삭제(pop) : 스택에서 원소를 꺼내오는 과정top pointer :주로를 가리키는 포인터 값 * 시스템 스택프로그램에서 호출과 복귀에 따른 수행 순서를 관리하기 위한 스택함수 호출이 발생하면 스택 프레임에 여러 정보들을 저장하여 시스템 스택에 삽입호출한 함수 수행에 필요한 지역 변..
-
[자료구조] 3강 2장 배열 - 1절 개요프로그래밍/자료구조 2014. 4. 17. 16:31
자료구조 2장 배열 - 1절 개요 * 배열이란?- 같은 자료형을 가진 원소가 순서를 가지고 만들어진 집합- 배열 원소들은 인덱스(0부터 시작한다) 에 의해 참조- 배열의 인덱스는 배열 원소의 순서를 의미 * 배열을 사용하는 경우 이점- 많은 요소들에 각각의 변수명을 생성하지 않으므로 메모리와 검색 효율이 좋음ex) int I,j,k,l,m,n; 변수선언을 해주었을 경우에는 변수 테이블을 따로 만들어 주어야한다. -> 메모리가 더 쓰인다. -> 배열로 선언해주는 것이 좋다. - 첨자 값만으로 액세스함으로써 배열의 원소값을 참조하는데 있어서 효율적인 표현이 가능ex) z=i+j+k+l+m; -> I,j,k,l,m 이 무엇인지 따로 int로 선언해 주어야한다. 자료형 배열 이름[배열의 크기] = {초깃값 리스..
-
[자료구조] 2강 1장 기본 개념 - 4절 순환 알고리즘프로그래밍/자료구조 2014. 4. 17. 16:29
1장 기본 개념 - 4절 순환 알고리즘 * 순환알고리즘정의하려는 개념자체를 정의 속에 포함하려 사용하는 방법직접 순환 : 함수가 직접 자신을 호출간접 순환 : 다른 제3의 함수를 호출하고 그 함수가 다시 자신을 호출어떤 복잡한 문제를 직접 간단하게 풀 수 있는 작은 문제로 분할하여 해결하려는 방법인 분할 정복의 특성을 가진 문제에 적합 ex) factorial Procedure factorial(n) if n 위 예시의 경우 factorial 안에 factorial을 넣음으로서 순환 알고리즘을 형성하였다. * 순환알고리즘의 또 다른 경우 : 이원 탐색 알고리즘특정한 원소를 찾기 위하여 주어진 리스트를 중간값을 기준으로 2개의 서브 리스트로 분할 -> 중간값과 찾고자 하는 원소를 비교하여 찾고자 하는 값이..
-
[자료구조] 1강 1장 기본 개념 - 1절 자료구조와 알고리즘프로그래밍/자료구조 2014. 4. 17. 16:23
Data : 어떠한 사실이나 값수치값 : 진수로 표현 * 스트링 : 연속적인 저장 공간에 저장된 문자열을 의미하며 문자 사이의 공백을 포함하여 문자열의 길이를 표현 * 정보 : Data값을 처리하여 발생되는 결과 * 자료구조란?- 자료 사이에 존재하는 관계를 개념적으로 정의- 자료를 효율적으로 이용할 수 있도록 자료의 특성에 따라 분류하여 구성하고 저장 및 처리하는 모든 작업 * 자료 구조를 기억 공간 내에서 실현하는 방법- 기억 공간 내에 앞에서부터 차례로 데이터를 기억시키는 방법 (배열)- 자료 사이의 관계가 기억 공간 내의 위치와 독립하여 포인터에 의한 접속으로 얻게 되는 방법 (리스트) * 배열과 리스트의 차이점- 배열 : 메모리 공간 내에 연속적인 공간이 있어야한다 - 리스트 : 메모리 공간 내..