archives

잘 설명된 블로그 : http://jinsolkim.kr/220069891025 먼저 선행되는 작업들 이후에 어떤 작업이 가능하다고 할 경우에 최소한의 시간을 구하는 그런 알고리즘. 아래는 코드. 입력값은 아래처럼 넣어보자. 4 4는 점 4개에, 간선이 4개라는 소리이고, 1 2는 노드 1에서 노드 2로가는 간선 하나가 있다는 소리이다. 나머지도 그런 소리이다. %입력이 다양하게 주어질 경우 그 중에서 가능한 한 경우만 출력한다. 다른 경우를 출력하려면 따로 돌려야 될듯 싶다. 4 4 1 21 32 43 4 # -*- encoding: cp949 -*- import Queue v,e = map(int,raw_input().split()) #노드,간선수 입력받음 adj = [[] for i in range..

이진 트리를 만들고 전위, 중위, 후위 탐색을 구현했다. 처음 배울때는 이걸 어떻게 짜냐... 했는데 지금 보니까 그리 어렵지도 않다. 아래에 main함수에서 addnode호출하는 부분을 보면 알수있듯이 1~10의 숫자를 무작위로 넣었다. 넣은 순서는 1->7->2->8->10->9->3->5->4->6 순서로 넣었고 이리 넣게 되면요렇게 이진 트리가 그려진다. 이걸 전위 중위 후위 순위하면 아래처럼 나온다. #include #include struct Node { int data; Node *leftchild; Node *rightchild; }; Node* newnode(int data) { Node* node = (Node *)malloc(sizeof(Node)); node->data = data;..

스택. 배열로 구현. #include int stack[100]; void push(int *top, int data) { if(*top>99) { printf("stack full\n"); return; } *top += 1; stack[*top] = data; } void pop(int *top) { if(*top==-1) { printf("stack empty\n"); return; } stack[*top] = -1; *top -= 1; } void print_stack() { int i; for(i=0;idata = data; newitem->next = NULL; s = head; } int pop(stack *s) { stack *temp = s; stack *last; int ret; whi..

단일연결리스트 c 코드. 개념 보고 짜봤는데 오랜만에 자료구조 공부하는거라 이 코딩이 맞는지 모르겠다. #include #include struct Node { int data; struct Node *next; }; Node* createnode(int data) { Node *n = (Node *)malloc(sizeof(Node)); n->data = data; n->next = NULL; printf("data = %d의 새 노드 생성\n",data); return n; } void deletenode(Node *n) { free(n); } void appendnode(Node *head, Node *n) { if(head->next == NULL) { head->next = n; printf("..

바로 앞의 선형 탐색법의 문제점은 집적화였다. 선형 탐사법에서 두 번째 이후에 탐사되는 위치가 첫 번째 탐사와 무관하다면 집적화 문제를 완화시킬 수 있다. 특징.이중 해싱에서는 두 번째 탐사를 첫 번째 탐사와 무관하게 하기 위해 두 개의 해쉬 함수를 사용한다. ex.레코드의 갯수 N=17일때 해시 함수를 h1(k) = k mod 19, h2(k) = 8 - (k mod 8) 이라고 하자.키값이 (1, 19, 5, 1, 18, 3, 8, 9, 14, 7, 5, 24, 1, 16, 12, 5) 라고 하면....1은 [1]에 들어간다.(1%19==1)19는 [0]에 들어간다.(19%19==0)5는 [5]에 들어간다.(5%19==5) (여기까진 선형 탐색법과 같다.)그다음 1은 [8]에 들어간다.(1%19==1..

해시 테이블의 크기 M이 레코드의 개수 N보다 클때 사용하는 것으로 동일 주소로 해시되는 원소가 있으면 해시 테이블상의 오른쪽으로 이동하면서 비어있는 공간을 찾아서 첫번째로 만나는 빈 공간에 원소를 저장시킨다. 특징. 해시 테이블에서 할당된 공간이 연속해서 나타나는 뭉치가 있으면 이게 더 커지는 현상이 발생할수 있는데 이것을 집적화(클러스터링)라고 부른다. 이러한 집적화가 발생하게 되면 평균 탐색 시간을 증가시켜 성능을 저하시키게 된다. ex. 레코드의 갯수 N=17일때 해시 함수를 h(k) = k mod 19라고 하자. 키값이 (1, 19, 5, 1, 18, 3, 8, 9, 14, 7, 5, 24, 1, 16, 12, 5) 라고 하면.... 1은 [1]에 들어간다.(1%19==1) 19는 [0]에 들어..

2-3-4트리라는게 있는데 2노드가 많을 경우 공간의 낭비가 심하다는 단점이 있다. 이것의 단점을 극복한 것이다. 2-3-4트리에 관한 설명은 여기에 잘 되어 있다. 레드-블랙 트리의 성질.1. 루트나 외부 노드는 모두 블랙이다.2. 루트에서 외부 노드까지의 경로 상에는 2개의 연속된 레드 노드가 포함되지 않는다.3. 루트에서 각 외부 노드까지의 경로에 있는 블랙 노드의 수는 모두 같다.4. 루트에서 각 외부 노드까지의 경로에 있는 블랙 링크의 수는 모두 같다. 레드-블랙 트리의 자세한 설명은 이 블로그에 잘 나와있다. 실행시간은 표본이 작아서 그런지 이진 탐색 트리랑 비슷하다. // ConsoleApplication5.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다. // #include "s..

이진 삽입 정렬은 삽입 정렬에 이진 탐색을 합친 알고리즘이라고 한다. 앞에 적은 삽입정렬을 보면 알겠지만 정렬되지 않는 원소를 삽입하기 위해서 왼쪽 원소들을 순차적으로 비교해나간다. 그런데 이진 삽입 정렬은 이미 왼쪽 원소들은 정렬되어있으므로, 이 사실을 기반으로 이진 탐색으로 삽입할 위치를 찾는다. 시간복잡도. 최고 평균 최악 삽입 정렬 O(N) O(N^2) O(N^2) 이진 삽입 정렬.O(NlogN) O(N^2) O(N^2) 직접 소스코드를 돌려 본 결과 시간복잡도로 추측해 본것처럼 최고의 경우에만 조금 빨라질거라는 예상과 달리 최고의 경우에는 약간 느려지고, 나머지 경우에는 약간 빨라졌다. 소스.# -*- encoding: cp949 -*- import time import random N = 10..

중간 계산값을 다른 변수에 미리 변수에 저장해놓는 형태의 방법. 동적 계획법을 설명하면 항상 같이 나오는 피보나치 수열 관련해서.. 읽어보기 : http://xaya_epica.blog.me/220061394723 http://cafe.naver.com/ehclub/book5079308/1748 요약 : 재귀함수로 피보나치를 구현하면 뒤로 갈수록 느려진다. 이유는 앞의 수를 계산할때도 난 이미 값을 알지만 프로그래밍적으로는 재귀하므로 계속해서 함수 속으로 들어가기 때문. 동적 계획법을 이용하면 이미 아는 값은 변수에 따로 넣어 줌으로서 이러한 재귀를 피할 수 있다. 아래 코드는 재귀와 동적 계획법 차이 예제이다. 따로따로 실행시켜보자. # -*- encoding: cp949 -*- def fibonacc..

탐색 방법론.어떻게 적을까 하다가 너무 잘되있는 블로그를 찾음.http://blog.naver.com/PostView.nhn?blogId=4717010&logNo=60209820587&parentCategoryNo=4&categoryNo=&viewDate=&isShowPopularPosts=true&from=search 특징.1. 이미 입력된 자료가 정렬되어 있다던지, 작은 값과 큰 값이 번갈아 나오는 경우에는 시간 복잡도가 순차 탐색과 같아진다. # -*- encoding: cp949 -*- import time import random import Queue N = 10000 class Dict: class node: def __init__(self,k,ll,rr): self.key = k self...

탐색 방법론.1. 리스트를 정렬시킨다.2. 처음에는 중간값으로 시작하여 중간값보다 크다 싶으면 (중간값 + 끝값)/2와 값 비교, 이런식으로 반씩 줄여나간다. 당연히 중간값보다 작다 싶으면 (처음값+중간값)/2와 값 비교, 이런식으로 진행한다. 특징.1. 리스트가 이미 정렬되어 있어야만 한다.2. 순차 탐색보다 빠르지만 리스트가 정렬되어 있어야 한다.3. logN+1번 이상의 비교를 하지 않는다. 예전에 여기서 만들었었다. # -*- encoding: cp949 -*- import time import random import Queue N = 10000 class Dict: class node: def __init(): self.key = -1 def __init__(self,max): self.a =..

탐색 방법론.그냥 처음부터 끝까지 하나하나 다 비교한다. 특징.1. 느리지만 세부적인 방법론에 따라 빠를 수도 있다.* 교수님이 말씀했던건데 네이버나 다음 등의 포털사이트에서 자주검색되는 질문등은 파일로 만든후 순차적으로 보여준다고 한다. 자주 검색될수록 앞에 갖다놓으면 더 빨라진다고 함.(맞는지는...)2. 성공적인 탐색의 경우(최선) 1번의 비교로, 최악의 경우 N번의 비교가 필요하므로 평균적으로 N/2번의 비교가 필요하다. 최악의 경우에는 모든 원소를 비교해야 하므로 항상 N+1번의 비교가 필요하다. 5000개 돌리면 2.8초가 나온다. # -*- encoding: cp949 -*- import time import random import Queue N = 5000 class Dict: class..

정렬 방법론.원소들의 첫,두,~~n번째 자리수 따라 새로운 리스트에 넣는다.ex) 첫번째의 경우 71은 [1]위치에, 97은 [7]위치에 들어간다.(일의자리 기준)두번째의 경우 십의 자리수를 기초로 정렬한다.~~ n의 자리수를 기초로 정렬. 설명이 잘된 블로그 : http://kaheeyah.blog.me/220704468091 # -*- encoding: cp949 -*- import time import random import Queue N = 10000 M = 5 def swap(a,i,j): a[i],a[j] = a[j],a[i] def CheckSort(a,n): Sorted = True for i in range(n): if a[i] > a[i+1]: Sorted = False if not ..

정렬 방법론.1. 원소들의 갯수를 세어 배열 count에 저장한다.2. 갯수된 정보를 바탕으로 배열을 재구성한다. 특징.1. 입력 키가 일정한 범위, ex) 1~M사이의 정수로만 이루어져 있다는 것을 미리 알고 있는 경우에 사용 가능하다.2. 추가 기억장소가 필요하다. 시간 복잡도 : O(N) (중복된 for반복문이 없음.) 10만개로 돌렸음에도 불구하고 빠르다. # -*- encoding: cp949 -*- import time import random N = 100000 M = 1000 def swap(a,i,j): a[i],a[j] = a[j],a[i] def CheckSort(a,n): Sorted = True for i in range(n): if a[i] > a[i+1]: Sorted = Fa..

정렬 방법론.1. heapify()함수를 호출해서 힙으로 만든다.힙 구조로 만드는 과정.ex)6 2 8 1 3 9 4 5 10 7 이라는 리스트가 있다고 하자. 이걸 이진 트리로 나타내면.가 되고 이걸 top down히프로 변환하자. 변환방법은맨위의 6 2 8 을 보면 가장 큰 수인 8이 맨 위에 있지 않다. 그러므로 6과 8을 교환한다. (부모가 자식 둘보다 커야 한다.) 그다음에는 2 1 3부분의 3과 2를 교환하고, 이런식으로 하나씩 간다. 그러면 이런식으로 된다. 특징.1. 우선순의 큐의 일종인 힙을 사용한다.2. 제자리 정렬 알고리즘.3. 퀵정렬보다 오래걸림. 시간복잡도 : O(NlogN) # -*- encoding: cp949 -*- import time import random N = 100..

정렬 방법론. ex) 리스트 A = [6, 2, 8, 1, 3, 9, 4, 5, 10 ,7]이 있다고 하자. 1. 리스트 A를 이등분하여 L=[6, 2, 8, 1, 3], R=[9, 4, 5, 10, 7]로 나눈다. 2. L과 R을 각각 정렬하자. 3. 두 리스트 L과 R을 합병하자. 더 참고 http://dntkrl79.blog.me/220733261240 http://blog.naver.com/goldtop0307/80105554620 합병하는 방법. i, j가 각각 있고 i,j중 작은것부터 k위치에 차례차례 들어간다. 특징. 1. 기억장소가 많이 필요하다.(기본 리스트가 100개면 100개의 새로운 기억장소가 필요하다.) 좋은 예제. 번호 순서대로 진행되며 왼쪽으로 먼저 쭉 간 다음에 더 나눌게 없..

정렬 방법론.1. 분할.1). 가장 오른쪽 값을 피봇으로 정한다.2). l부터 시작하여 오른쪽으로 이동하며 피봇보다 큰 값을 가진 원소를 찾는다.3). r-l부터 시작하여 왼쪽으로 이동하며 피봇보다 작은 값을 가진 원소를 찾는다.4). i=l, j=r-l이 들어가게 되며 i가 j보다 커지면(즉 왼쪽 오른쪽이 교차되면) 반복문을 벗어난다.5). a[i]와 a[j]를 서로 교환한다. 1). l값은 인덱스 1로 시작하고,(0은 감시 키값) r값은 끝에서 시작한다. 끝값은 피봇이라고 위에 적었는데 어차피 j=r-l이므로 j는 피봇을 제외한 오른쪽 끝값이 된다. 특징.1. 빠르다.2. 최악의 경우 선택, 삽입정렬과 같다. 예시. 책에서 가져옴. 찾아보니 여기에 있다. 리스트 a = [6, 2, 8, 1, 3, 9..

정렬 방법론.1. h값에 따라 리스트를 새로 만든다. 리스트의 길이는 15이고 h=4일경우 ex) [1번째,5번째,9번째,13번째],[2번째,6번째,10번째,14번째] .. h=13일 경우는 [1번째,14번째],[2번째,15번째] 두개의 리스트가 나온다.(리스트 길이 15인 경우.)2. h값은 3*h+1로 정한다. h=1,4,13,40,121,264...이런 순으로 만들어지는데 리스트의 길이보다 작으면서 가장 큰 값을 선택한다. 리스트의 길이가 15면 h=13을 고른다.3. 정렬시 h=13으로 정렬했으면 그다음으로 작은 h=4로 정렬한다.(그다음은 h=1)4. 각각 새로 만들어진 작은 리스트들은 각각 삽입 정렬을 수행시킨다.5. h=1일경우 그냥 삽입 정렬을 수행한다. 특징.1. 정렬이 된 경우가 유리한..

정렬 방법론.1. 0번째는 값이 맞는지 키값으로 사용하기 위해 -1처럼 가장 작은 값으로 둔다.2. ~1번째까지와 2번째를 비교해서 2번째 원소가 들어갈 자리를 ~1번까지중 만든다음 2번째 원소를 집어넣는다.3. ~2번째까지와 3번째를 비교해서 ~~~ 나머지 동일.4. 끝까지 간다. 특징.1. 계속 비교하므로 리스트 크기가 크면 불리하다. (버블과 비슷)2. 정렬이 거의 된 데이터일 경우 더 유리하다.(교환이 적게 일어나므로) (버블과 비슷)3. 데이터가 역순인경우, 즉 최악의경우에 시간이 엄청 느리다. (버블과 비슷)4. 버블정렬과 다른점은 버블정렬은 n번째와 n+1번째만 비교해서 자리를 바꾸지만 삽입 정렬은 n+1번째의 데이터를 0~n번째까지중 어디에 들어가야할지 자리를 찾아서 집어넣는다는것. 시간 ..

정렬 방법론.1. N번째 위치와 N+1번째 위치의 값을 비교해서, N+1번째 위치의 값이 더 클 경우 N번째와 N+1번째의 값을 교환함. 특징.1. 계속 비교하므로 리스트 크기가 크면 불리하다.2. 정렬이 거의 된 데이터일 경우 더 유리하다.(교환이 적게 일어나므로)3. 데이터가 역순인경우, 즉 최악의경우에 시간이 엄청 느리다. N개의 원소에 대해서 N-1번의 비교를 해야 되기 때문에비교횟수는 N(N-1)2, 시간 복잡도는 O(n^2) 이 된다. 10000개의 데이터를 돌려봤는데 예상한대로 나왔다. 시간복잡도가 같이 n^2인데도 시간 차이가 나는건 위에서 언급했듯이 최악의 경우에 교환이 더 많이 일어나서 오래걸리는것으로 보인다. # -*- encoding: cp949 -*- import time impo..

정렬 방법론. 1. 최솟값을 찾아서 0번째 위치와 바꿈. 2. 0번째 위치를 제외한 최솟값을 찾아서 1번째 위치와 바꿈. 3. N번째까지의 위치를 제외한 최솟값을 찾아서 N번째와 바꿈. 4. 끝까지 가면 성공. 특징. 1. 정렬되있는 순서로 들어오던 아니던 실행시간이 비슷하다. 항상 비교하는양이 동일하기 때문. 2. 추가적인 기억장소를 요구하지 않는다. ex) N개의 원소에 대해서 N-1번의 비교를 해야 되기 때문에(항상 N-1번 비교) 비교횟수는 N(N-1)2, 시간 복잡도는 O(n^2) 10000개의 데이터를 랜덤한 데이터, 최고, 최악의 상황으로 가정하고 돌려봤는데 셋다 비슷비슷할 것이라는 예상과 달리 최악의 상황이 시간이 조금 더 걸렸다. 예상대로라면 다 똑같이 나와야 하는데.. 개인적인 생각으로..