자료구조&알고리즘 (7) 썸네일형 리스트형 [자료구조] 덱(Deque)의 개념과 연결 리스트로 구현(C언어) INDEX 1. 덱의 개념 2. 덱의 ADT를 구성하는 함수 3. 구현 3-1. 노드와 덱 구조체 3-2. 덱의 초기화와 비어 있는지 확인 3-3. 덱의 Front삽입과 Rear삽입 3-4. 덱의 Front추출과 Rear추출 1. 덱의 개념 덱은 아래의 그림처럼 직관적으로 이해하는 것이 가장 편하다. 스택이 입구와 출구가 1개뿐이었고 큐가 입구와 출구가 구별되는 일방향 통로의 느낌이었다면 덱은 큐의 업그레이드 버전인 양방향 이동 통로라고 이해할 수 있다. 그만큼 큐보다 개념적인 것들이 더 등장하게 된다. 덱에서 정보의 접근과 저장은 오직 Front와 Rear에서만 가능하다. 즉 큐보다 데이터 접근성이 더 좋아진 것이다. 덱의 Front에서 시작해서 Rear까지 이동할 수 있고 그 반대도 마찬가지로 가능하.. [자료구조] 스택을 활용해서 두 자리 수 이상의 연산이 가능한 계산기 만들기(C언어) 스택으로 계산기를 구현하려면 아래와 같은 과정을 거쳐야 한다. 중위 표기법을 모두 후위 표기법으로 바꾼다. 후위 표기법으로 바뀐 식을 스택에 넣어준다. 스택에 있는 값들을 특정 규칙에 따라 연산한다. 중위 표기법과 후위 표기법에 대한 내용은 위키 문서를 참조하기를 바란다. 이해를 돕기 위해서 후위 표기법을 가장 잘 설명한 블로그 주소도 남긴다. 주로 스택은 구제체 안에 배열을 선언한 상태로 사용한다. 아래는 스택을 구성하는 여러 기능들을 구현해 보았다. 이들 모두 계산기 구현에 중요한 역할을 하기 때문에 반드시 알고 넘어가야 한다. #include #include #include #define MAX_LEN 100 typedef struct Stack { // 스택 구조체 int data[MAX_LEN].. [자료구조] 연결 리스트(C언어) 연결 리스트(Linkedlist) 연결 리스트란 노드가 연결되어 있는 자료구조이다. 이때 노드는 노드만의 데이터와 포인터를 갖고 있다. 여기서 데이터는 우리가 저장하고자 하는 대상이 될 수도 있다, 예를 들면 수열, 등수에 따른 시험 점수 등이 될 수 있다. 즉 관리되는 데이터를 표현하는 것이 노드의 데이터 부분이다. 노드의 포인터는 사실 연결 리스트를 연결 리스트로 만들어주는 가장 중요한 특성이다. 포인터는 다음 노드 또는 이전 노드와의 연결을 담당한다. 즉 데이터 관리를 위한 포인터인 것이다. 우리가 알고 있는 일반적인 배열과는 다르게 데이터의 추가와 삭제가 어느 지점에서도 O(1)만에 가능하다는 장점이 있다. 하지만 단점으로는 데이터로의 임의적 접근이 상당히 제한된다는 점이다. 왜냐하면 초기 데이터.. [알고리즘] 정렬된 연결 리스트에서 이진 탐색 사용하기(C언어) 이진 탐색의 한계점을 공부하던 와중에 동적인 자료구조에서는 사용이 힘들 수 있다는 것을 알았다. 하지만 최근에 스택과 큐를 C로 구현해봤기 때문에 큐를 이용해서 이진 탐색 함수를 만들어보면 재밌을 것 같아서 시도해 보았다. 구상 일반적인 이진 탐색은 배열에서 진행 되기 때문에 값에 접근함에 있어서 배열과 연결 리스트가 어떤 차이점을 가지고 있는지 먼저 생각해 보자. 큐를 사용할 것이기 때문에 사용할 큐에 대한 소스코드는 더보기에 첨부하겠다. 더보기 #include #include typedef struct Node{ int data; struct Node* next; } Node; typedef struct Queue{ Node* front; Node* rear; int count; } Queue; vo.. [자료구조] 큐(Queue).(C언어) INDEX 1. 개요 2. 배열? 연결리스트? 3. 구현 3-1. Node(노드) 3-2. Queue(큐) 3-3. initQueue(초기화) 3-4. isempty(비어 있는지 확인) 3-5. enqueue(데이터 삽입) 3-6. dequeue(데이터 반환) 3-7. printQueueContents(큐에 있는 원소들 출력) 3-8. 주석 제거한 전체 코드 1. 개요 FIFO(First In First Out) 방식을 취하고 있는 자료구조이다. 스택(Stack)의 업그레이드 버전이라고 생각하면 쉽다. 왜냐하면 입출구를 공유하는 스택과는 다르게 큐는 입구와 출구가 다르기 때문이다. 큐는 단방향 구조인 동시에 rear부분에서 enqueue(데이터 삽입)와 front부분에서 dequeue(데이터 출)가 발생.. [알고리즘] CCW(Counter Clock Wise) INDEX 1. 개요 2. 외적 3. 사용 1. 개요 외적을 이용해 3개의 점 사이의 관계를 구할 때 사용되는 알고리즘이다. 이 알고리즘을 보고 놀랐던 게, 컴퓨터는 생각보다 인간이 쉽게 할 수 있는 일들을 못한다. 예를 들어 좌표 평면에 존재하는 좌표들의 관계를 파악함에 있어 인간의 인지 능력이 훨씬 직관적으로 정확하다. ccw알고리즘은 세 가지 상황에 대해 세 가지 값을 return한다. 시계 방향 → ccw0 2. 외적 외적과 연관이 깊은 알고리즘이고 사실 외적의 원리 그 자체를 이용한다고 해도 과언이 아니다. 외적은 일반적으로 2개의 3차원 공간의 벡터에 대한 연산이다. 스칼라가 나오는 내적과 달리 외적은 크기(스칼라)와 방향(벡터)을 모두 얻을 수 있다. 사실 ccw에서는 방향만이 관심 대상이다.. [알고리즘] 이진 탐색(Binary Search) INDEX 1. 정의 2. 방법 3. 소스 구현 4. 장점 5. 단점 1. 정의 ▶ 오름차순으로 정렬된 1차원 배열에서 특정한 값을 찾아내는 알고리즘 반드시 오름차순으로 정렬된 배열에서만 사용 가능하다. 왜냐하면 찾으려는 숫자가 n일 때 현재의 위치가 n보다 작을 때 n은 반드시 현재의 위치보다 뒤에 있음을 기본으로 깔고 있기 때문이다. 또한 이진 탐색을 사용하는 목적은 크게 두 가지가 있다. 찾고자 하는 원소가 배열에 있는지에 대한 존재 여부. 찾고자 하는 원소가 배열에 있다는 것을 확실히 알고 있지만 위치 정보를 알고 싶을 때. 2. 방법 오름차순 배열과 찾고자 하는 값(6)이 있다고 가정하자. { 1, 2, 3, 4, 5, 6, 7 } 우선 배열의 중간에 있는 값(4)을 입력한다. 현재 위치(4)와.. 이전 1 다음
