목록전체 글 (175)
Cohe
선형검색 선형 검색이란? 선형검색은 주어진 데이터에서 키 값에 의하여 데이터를 찾는 과정이다. 검색 방법 중 가장 단순하다. 선형검색 알고리즘 int sequential_search(int keys[], int find_key, int n) { int i=0; while(i searchnum ) right = middle - 1; else if ( list[middle]==searchnum ) return middle; } return —1 ; } 이진탐색 알고리즘-순환 int binsearch(int list[], int searchnum, int left, int right) {int middle; if(left5개->2개->1개 이므로 최악의 경우 4번 비교하게 된다. 11개의 데이터 데이터가 10..
버블 정렬 버블정렬 : 버블 정렬은 정렬이 진행되는 모양이 비누거품과 같다고 하여 붙여진 이름이다. 나란히 있는 두개의 데이터를 계속하여 바꾸어 나간다. 전체 비교 횟수 : T(n)=n(n-1)/2 시간 복잡도 : O(n²) 알고리즘 list에 대한 기본 버블정렬 알고리즘 void bubble_sort(element list[], int n){ int i, j; element next; for (i=n-1;i>0;i--){ for(j=0;jlist[j+1]{ swap(list[j],list[j+1]}}}} 개선된 버블정렬 버블정렬 각 단계에서 데이터의 이동이 일어나지 않으면 다음 단계로 진행할 필요가 없다. 즉 중간과정에서 정렬이 끝나면 더 이상 비교와 교환이 필요없다. void bubble_sort(e..
이진트리 탐색 알고리즘 트리의 탐색은 트리의 각 노드를 방문하는 작업을 말한다. 👉 다음과 같은 방법들을 생각해 볼 수 있다. 레벨 순 : 레벨이 낮은 순으로 방문 왼쪽 트리 L→ A → 오른쪽 트리 R (중위 탐색) A→왼쪽 트리 L → 오른쪽 트리 R (전위 탐색) 왼쪽 트리 L → 오른쪽 트리 R → A (후위 탐색) 중위 탐색(inorder traversal) 왼쪽 트리 → 루트 노드 → 오른쪽 트리 순으로 방문 주의점 : 왼쪽 트리를 방문할 때 왼쪽 트리 자체가 트리이기 때문에 왼쪽 트리 안에서도 다시 중위 탐색을 한다. 왼쪽 트리로 간 다음 왼쪽 트리의 왼쪽 트리, 왼쪽 트리의 루트노드, 왼쪽 트리의 오른쪽 트리 순이 된다. 예시 1 중위 탐색을 하면 왼쪽 트리(B D E H 0, 루트(A),..
검색 시간복잡도 조작 시 시간복잡도 (insert, delete, update) 배열 O(logN) 정렬이 되어 있다고 가정 O(log N) + O(n) insert 시 위치 찾기 후 데이터 재정렬 연결리스트 O(n) 정렬 여부에 상관 없음 O(n)/O(1)+ O(1) tree O(logn) O(logn)+ O(1) 연결리스트의 삽입 삭제 시 데이터를 이동하지 않는 장점을 살리면서 연결리스트의 검색 시 노드의 처음부터 찾아가야하는 단점을 보완 데이터를 중간부터 찾아가는 이진검색의 장점 이용! 연결리스트의 포인터를 리스트의 중간에 두는 방법을 선택 이진 트리는 연결 리스트의 link 노드를 앞 뒤로 배치한다. ⇒ 검색을 중간부터 시작하여 좌우 중 하나로 분기, 0.5씩 검색 대산을 줄여나감으로써 이진검색의..
연결리스트 처음과 마지막 노드 삽입/삭제 연결리스트의 처음과 마지막에 노드를 삽입 삭제 할 경우 노드 수 n과 노드를 삭제하려면 앞 노드의 주소를 알아야한다 시간 복잡도 → O(n) 원형 연결 리스트 정의 연결리스트의 맨 끝 노드를 첫 번째 노드와 연결시켜서 원형으로 만든 리스트 단순 연결리스트의 마지막 노드를 끝 노드와 연결 시켰다 예시 리스트를 원형으로 만든 다음 리스트의 포인터가 마지막을 가리킨다. 그 후 리스트의 처음과 마지막에 노드를 삽입하는 경우를 살펴보자. 문제 void delete_first(list_ptr *ptr){ if ((*ptr)==NULL){ printf("원소 없음");} //빈리스트 else{ /* 원형리스트의 맨 앞 부분을 삭제하는 함수 */ //ptr의 링크 값을 바꿔야한..
리스트 자료구조 데이터 연산 설명 스택 int stact[100]; (10,30,40,20) push(35); y=pop(); … 삽입과 삭제가 한쪽 끝 큐 int queue[100]; (10,30,40,20) insert(35); y=delete(); … 삽입과 삭제가 양쪽 끝 리스트 int mylist[100]; (10,30,40,20) intsert(45); y=delete(); 삽입과 삭제가 아무 곳에서나 일어난다. (문제점)→ 데이터가 많으면 순서를 유지하기 위하여 데이터 이동이 많아진다. 동적 데이터의 관리 프로그램 실행 중 데이터가 이동을 많이 한다면? 데이터가 움직이지 않으면 검색을 빨리할 수 있다. ex) 공룡에 대한 데이터 타입 데이터는 삽입 삭제 연산에 의하여 위치와 개수가 변한다 데..
후위표기법 후위표기법은 연산자를 피연산자의 뒤에 놓는 방법이다. 스택 응용의 예시이며 수식의 계산은 계산기에서나 컴퓨터 프로그래밍을 할 때 자주 나타난다. 우리가 평소에 쓰는 표기법은 중위 표기법이다. 곱하기. 나누기 연산자가 +.-연산자보다 먼저 계산해야하며 곱하기 나누기 연산자와 +-가 동시에 있으면 왼쪽에 있는 식부터 계산해야하는 것을 알고 있기 때문이다. 수식의 계산 사람 연산자의 우선 순위를 정한다. 우선순위가 같으면 왼쪽 부터인지 오른쪽부터인지 정한다. 복잡하면 괄호를 사용하여 계산한다. 컴퓨터 사람이 하는 방법 대로 계산할 수도 있지만 중간과정을 줄이고 한번에 왼쪽에서 오른쪽으로 계산할 수 있는 효율적인 방법을 개발 수식의 후위식으로 바꾼다. 후위식을 계산한다. C언어의 우선순위 표 수식 계..
전문가 시스템 개발의 배경 인공지능 초창기에는 모든 문제를 탐색으로 해결할 수 있는 시스템을 만들고자 함 → GPS(General Problem Solver) 시스템 일반적 문제를 다 처리하는 기획 H/W, S/W 모두 구려서 못함 문제를 해결하기 위해 보다 제한된 문제에 역량을 집중하는 것이 필요하다는 인식 → 전문가 시스템(export system) 인공지능, 화학 구조식 전문 구현 전문가 의학 법률 등 상식보다 전문가 지식 시스템이 더 쉽게 구현 가능했다. 지식의 중요성! → 지식이 추론 기법만큼 중요함 지식 == 인공지능에게 중요한 역할 추론 기법 → 구조 중 하나이다. 구조 지식 베이스 General kmowledge base Knowledge-base editor 추론 기관 ES shell이라..
인공지능과 게임 게임은 이전부터 인공지능의 매력적인 연구 주제 이유 지적 능력과 연관이 있다. 추상적으로 정의가 가능하다. 비교적 적은 수의 연산자 연산의 결과는 엄격한 규칙으로 정의됨 게임의 정의 2인용 게임, 제로썸 게임, 순차적인 플레이를 가정 제로썸 게임 - 한 경기자는 반드시 승리 다른 경기자는 반드시 패배를 의미 두 경기자 : MAX, MIN MAX : 먼저 수를 두는 플레이어 휴리스틱을 정해야한다. 한 사람이 MAX의 N을 갖고 다른 사람이 MIN의 N을 갖는다. Tik-Tao-Toe 간단한 게임임에도 불구하고 노드가 기하급수 적으로 증가한다. 컴퓨터의 계산이 길어지거나 메모리 공간이 부족하다. # of winning row : 이기는 행 계산 법 -> 그림 참조 A* 와 다르다. 게임 트리..
스택과 큐 자료구조 리스트, 스택과 큐 : 스택과 큐는 리스트 자료구조의 특별한 경우이다 리스트 순서가 있다. 읽기, 삽입과 삭제를 리스트의 어느곳에서나 행함 → 순서 유지를 위해 복잡한 상황이 유지됨. 스택 순서가 있다 삽입과 삭제를 리스트 한 쪽(top)에서 행함 큐 순서가 있다. 삽입은 리스트의 한쪽(rear)에서 하고 삭제는 삽입의 반대쪽(front)에서 행함 자료구조와 연산 모델 자료구조= 자료선언+연산 자료 선언 : 프로그램 언어의 타입을 이용하여 선언 연산 자료의 검색과 갱신에 관한 연산으로 이루어진다 검색 : 찾기 갱신 : 삽입, 삭제, 수정 스택 삽입은 리스트의 마지막, 삭제도 리스트의 마지막에서 행한다 Last-In-First-Out(LIFO)의 자료구조 스택 자료구조와 연산 검색 to..