풀캠정글러

12.16 ~ 12.22 KMP 이분 매칭 문제와 DFS 솔루션 최대 유량 문제와 BFS 솔루션 (에드몬드 카프) 뫼비우스 함수 6주차가 애매하게 어려워서 자꾸 그쪽만 파다보니 PS를 할 시간이 없었다면, 이번주는 정반대였다. 원래 뭔가 막히는 부분이 있으면 낭비하게 되는 시간이 싫어서 잠시 옆에 치워두고 다른 걸 손대는 편이다. 개인적으론 7주차 과제인 웹 서버가 지금까지중에 제일 어렵고 깊게 들어갔다고 생각하는데, 그래서인지 매일같이 알고리즘에 자꾸 손이 가서 오히려 문제를 푸는 시간이 더 많아지는 선순환? 같은 일이 벌어져서 결국 풀다보니 40문제 넘게 풀었다. 이번주에 다룬 주제는 크게 KMP, 이분매칭, 최대유량 이 셋인데, 이분 매칭은 세그먼트 트리처럼 일단 베이스만 이해해도 테크닉적인 부분만..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 12..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include #include "csapp.h" /* Recommended max cache and object sizes */ #define MAX_CACHE_SIZE 1049000 #define MAX_OBJECT_SIZE 102400 void doit(int fd); int parse_uri(char *uri, char *hostname, char *path, int *port); void makeHTTPh..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 12..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include "csapp.h" int main(void) { char *buf, *p; char arg1[MAXLINE], arg2[MAXLINE], content[MAXLINE]; int n1 = 0, n2 = 0; /* Extract the two arguments */ if ((buf = getenv("QUERY_STRING")) != NULL) { p = strchr(buf, '&'); *p = '\0'; strcpy(arg1, buf); strcpy(arg2, p + 1); n1 = atoi(strchr(arg1, '=')..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 12..

밀러-라빈 알고리즘(https://uneducatedjungler.tistory.com/121)에서 이어지는 글 폴라드 로 알고리즘은 입력된 정수 n의 랜덤한 인수를 뽑아내는 알고리즘이다. 정리에 앞서 거칠게 폴라드 로를 요약하자면 아래와 같다. "n과 d의 공약수를 발견할 때까지 d에 유사난수를 대입한다" 얼핏 보면 n에 1부터 차례대로 나눠보는 것과 다름없는 굉장히 무식해보이는 방법같아 보이지만, 실제로는 의외로 빠르다. 그 이유는 생일 역설을 보면 알 수 있다. 생일 역설 (https://ko.wikipedia.org/wiki/%EC%83%9D%EC%9D%BC_%EB%AC%B8%EC%A0%9C) 생일은 366일이라는 한정된 range를 갖고 있다. 따라서 367명 이상이 있으면 반드시 생일이 같은 ..

KMP 정복완료와 동시에 티어랑 클래스 업 다이아 달고 CLASS 8이면 지엽적인 고난도 알고리즘들 외에 범용적으로 쓰이는건 다 아는 셈이라는데 12월안에 P2, 1월중순에 P1까지 가면 2월에 나만의무기 시작하기 전에 다이아를 달수있지 않을?까? 그리고 텐서플로우로 그럴듯한 딥러닝 프로젝트를 개발해서 보이저엑스에 지원하는 행복한 미래...

12.09 ~ 12.15 세그먼트 트리의 구현과 응용 ??? : 이번주 과제는 지난주보다 구현량이 없어보이니 알고리즘도 꾸준히 해야지 6주차의 원래 목표는 세그먼트 트리 + KMP였는데 세그먼트 트리만 익히고 KMP는 보지도 못했다. 간단하게 이론을 볼땐 구간합을 저장한다길래 아 뭔가 아무튼 지엽적인 문제에 솔루션을 제공하는 자료구조겠구나 싶었는데, 정작 파보니 구간 합뿐만 아니라 정말 모든 종류의 'sub'에 대한 데이터를 다룰 수 있었다. 일단 세그먼트 트리를 구현하는법을 배워도 노드에 무엇을 저장할지, 어떤 노드 취합함수로 쿼리를 해결할지가 다 다르니까 한두문제 푸는걸로는 응용력에 도움이 안돼서 가능한 많은 문제를 풀어봤다. 세그먼트 트리 문제를 풀면서 느낀게, 단기간에 많은 개념을 머리속에 때려넣..

3. Explicit free list chain 내림차순 정렬 / 그에 맞는 Best fit find_fit함수 구현 (+2점) 명시적 가용 리스트 chain은 가장 나중에 추가된 원소가 start점에 위치하는, 우선순위 없는 선입후출인 스택의 구조를 갖고 있었다. 속도는 빠르지만 공간 효율에는 그닥 도움을 주지 못해서 속도점수는 높고 메모리 점수는 낮아 한쪽으로 점수가 치우친 상태인데, 빈 블록을 크기순 내림차순으로 정렬함으로써 이 부분을 개선했다. 빈 블록을 보관하는 가용리스트 chain이 크기 내림차순이라면, 가장 큰 블록은 chain의 start에 있을 것이다. 그렇다면 만약 fit을 요구하는 asize가 start보다 크다면 나머지 원소와는 비교하지 않아도 fit이 불가능함을 빠르게 알 수 있..