자료구조&알고리즘/알고리즘 (3) 썸네일형 리스트형 [알고리즘] 정렬된 연결 리스트에서 이진 탐색 사용하기(C언어) 이진 탐색의 한계점을 공부하던 와중에 동적인 자료구조에서는 사용이 힘들 수 있다는 것을 알았다. 하지만 최근에 스택과 큐를 C로 구현해봤기 때문에 큐를 이용해서 이진 탐색 함수를 만들어보면 재밌을 것 같아서 시도해 보았다. 구상 일반적인 이진 탐색은 배열에서 진행 되기 때문에 값에 접근함에 있어서 배열과 연결 리스트가 어떤 차이점을 가지고 있는지 먼저 생각해 보자. 큐를 사용할 것이기 때문에 사용할 큐에 대한 소스코드는 더보기에 첨부하겠다. 더보기 #include #include typedef struct Node{ int data; struct Node* next; } Node; typedef struct Queue{ Node* front; Node* rear; int count; } Queue; vo.. [알고리즘] 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 다음
