본문 바로가기

컴퓨터/Algorithm26

힙 우선 순위 큐를 구현하는 데 쓰이는 자료구조이다. 힙의 기본 : 부모 노드는 자식 노드보다 우선순위가 높다. (몇 년 전에는 이진트리의 기본과 헷갈렸던 것 같다 ) 삽입의 기본 : 제일 끝에 추가한 뒤, 부모와 자리를 바꾸면서 본인 우선순위에 맞는 곳을 찾는다. 삭제의 기본 : 요소 1을 반환한 뒤, 제일 끝 노드를 1로 가져와서 자식과 자리를 바꾸면서 본인 우선순위에 맞는 곳을 찾는다. 힙이 아닌 배열을 힙으로 만들기 위해서는 시간 복잡도 O(nlogn)이 들지만, PS에서 쓰지 않는다.(어차피 힙으로 쓸 자료구조라는 전제 하에 그걸 사용하므로) 아래 코드에서 일반적인 코드와 차별점을 둔 것은 삽입 정렬때와 비슷한 것인데, 데이터가 들어가는 곳부터 진행하면서 스와핑을 하지 않고, 스와핑없이 밀기만 하다.. 2019. 12. 21.
문자열의 해시함수(Honor's method) PS 분야에서 일반적인 해시 함수는 다음과 같다. (DJB) ※ 다른 해시 함수들을 알고 싶다면 사이트 참고 https://www.partow.net/programming/hashfunctions/ unsigned long hash(const char *str) // DJB { unsigned long hash = 5381; int c; while (c = *str++) { hash = (((hash 2019. 12. 21.
더블 링크드리스트 Head, Tail은 struct node형이 struct node* 형보다 더 좋다. 이유는 삭제 코드의 예외 상황(노드가 한 개인 경우)이 없어지기 때문이다. 초기화 시 head.next = &tail, tail.prev = &head; 를 하면, 추가 코드의 예외 상황(노드가 없는 경우)이 없어진다. 다음 코드는 head의 next가 가장 최근에 추가된 노드 구조(tail이 없을 때 추가 O(1))의 링크드리스트 구현이다. struct node{ ... // data struct node* prev; struct node* next; } struct node head, tail; void init(){ head.next = &tail; tail.prev = &head; } void add(struc.. 2019. 12. 21.
배열 기반 링크드리스트(myalloc) 정적배열로 미리 선언해놓고, 노드 할당 요청 시 주소만 받아오는 형식이다. 몇 번까지 할당해줬는지를 별도의 변수에 담아두고, 그 변수가 가리키고 있는 요소를 리턴 후 변수를 증가시켜주면 된다. 속도는 malloc 함수를 이용해 매번 할당받는 것보다 빠르다. 링크드리스트 최대 크기를 알고 있을 때 쓸 수 있는 방법이다. #define MAX_NODE (10000) struct node{ ... // data; struct node* prev; struct node* next; }; struct node node[MAX_NODE]; // 정적 배열 struct node head; int node_cnt = 0; // 이미 할당 받은 노드 수 void add(){ struct node *p = &node[++.. 2019. 12. 21.
자료형 별 표현 크기 맨날 눈으로 훑고 지나가던건데, 최적화 코드를 짜다보니 중요한 걸 체감하게 된다. bool : 0,1 만 나타내지만 (1B) unsigned char : 0~255 (1B) signed char : -128 ~ 127 unsigned short : 0 ~ 65535 (2B) signed short : -32768 ~ 32767 unsigned int : 0 ~ 4,294,967,295 ( 대략 40억 = 4G ) (4B) signed int : -2,147,483,648 ~ 2,147,483,647 (대략 20억 = 2G ) unsigned long long : 0 ~ 18446744073709551615 (8B) -> 영문자 문자열 13자리까지 표현 가능 2019. 12. 16.
DFS 1. 방문하지 않은 이웃 정점들 중 선택하여 방문 2. 더 이상 방문할 정점이 없으면 퇴각. 방문 여부(초기값 -1)를 체크하는 정적 배열 전역 변수 필요 void backtrack(state){ visit[state] = 1; // VISITED if ( End_state || Invalid_state) // 종료 혹은 가지치기 return; for (neighbor case) if(visit[neighbor] == -1){ // UNVISITED backtrack(neighbor); } } 재귀를 쓰는 이유 : 주사위 1번의 경우의 수 -> for문 1개가 필요 주사위 2번의 경우의 수 ->for문 2개 필요.. 주사위 n번이면 ?? 재귀의 단점 : 스택 오버플로우 ( 현업에선 거의 안씀 -> 알고리.. 2019. 11. 17.

티스토리툴바