본문 바로가기

For all category

Algorithm #2. Search algorithm. - 2.5 Red-Black Tree (1). 이번에 소개할 Red-Black Tree 는 Binary search tree 의 일종입니다. 이전에 구현했던 Binary Search Tree 는 다음과 같은 node 구조체를 선언했었죠. typedef struct node{ char dat; struct node *lLink; struct node *rLink; } bTree_node; node 의 값을 저장할 변수와, 좌/우측 link node 의 값을 포함하는 구조체입니다. 하지만, Red-Black Tree 는 여기에서 '색깔' 을 저장할 추가 변수의 선언이 필요합니다. 다시말하면, 각 node 는 'Red' 혹은 'Black' 의 색깔을 갖는다는 것이죠. 그럼 이쯤에서 Red-Black Tree 의 필요성을 설명드려야 할 듯 합니다. 예전 포.. 더보기
Algorithm #2. Search algorithm. - 2.4 Binary Tree Search (2). #include #include #include /*Binary search tree 구현에 사용할 NODE 구조체. */ typedef struct node{ char dat; struct node *lLink; struct node *rLink; } bTree_node; /* Binary search tree의 구성을 위한 함수의 prototype. */ void bTreeInsert(char data, bTree_node **root); /* Tree 구성에 필요한 함수의 prototype. */ bTree_node *TreeConstruct(void); /* Binary tree searching 에 필요한 함수의 prototype. */ int bTreeSearch(char key, bTree_.. 더보기
Algorithm #2. Search algorithm. - 2.4 Binary Tree Search (1). 테슬라 군이 트리 자료구조에 대한 일반적인 설명을 해 주었군요. -_-a - Dlbo 군이 그렇게나 강조하는 테슬라 군과의 자료구조 포스팅 첫번째 연동입니다. - 트리 구조에 대한 일반론은 테슬라군이 이미 설명을 해 놓았으니 생략하겠습니다. Binary Tree 는 트리 자료구조 중에서도 각 부모 노드가 자식 노드를 2개씩 가지는 자료구조를 말합니다. Binary Tree Search 기법은 일반적으로 Binary Tree 의 일반적 특징을 따릅니다만,여기에 한 가지 조건이 더 붙죠. 그것은 각 노드에 저장되는 레코드의 값 순서가 ' Left < Root < Right ' 여야 한다는 것입니다. 일반적으로 Binary Tree Search 는 동적인 자료집합에 대해서 가장 효율적입니다. 값을 그냥 넣기만.. 더보기
12 / 26 Reuent 포스트 연기. 갑자기 일이 마구마구 들어오는 바람에 -_- 오늘내로 올리기는 힘들 듯 합니다. 내일 중으로 올라갑니다. 더보기
Algorithm #2. Search algorithm. - 2.3 Binary Search. 이번 주제는 Binary Search. 즉, 이분 검색입니다. 왜 'Binary' 라는 표현이 나왔는지 궁금하실텐데요, 이는 검색 방식 때문입니다. 앞서 작성한 'Quick Sort' 알고리즘에서 'Divide and Conquer' 와 'Three of median' 기법을 설명 드렸을겁니다. Binary Search 알고리즘은 이 기법들을 동시에 사용합니다. 단, 전제 조건은 '이미 정렬된 레코드' 에서 사용해야 한다는 전제조건이 붙죠. 그럼 알고리즘 소개를 해 볼까요. 1. 이 레코드의 중앙값을 찾는다. - 이미 정렬된 레코드라 가정한다. - 2. . 만약 찾을 key 값이 이미 찾아놓은 레코드의 중앙값과 같다면 Find it. 3. 먄약 찾지 못했다면 3 - 1. key 값보다 중앙값이 작은 경우.. 더보기
Reuent 연기공지. -_- 매번 연기하는 것 같군요. 크흠 ㅡ,.ㅡ 다음주에 전과목 시험이 모두 몰려있어서... 12/5일 포스팅과 12/12일 포스팅은 불가능할 것 같습니다. 더보기
Algorithm #2. Search algorithm. - 2.2 Sequential Search. 쫌 많이 늦었군요... 죄송합니다 -_-a; H 대학교 친구한테 C 언어 알려주느라 어제 늦게 들어왔습니다. 매번 공지도 없이 늦네요 orz. 여튼.. 각설하고. 이번 주제는 Sequential Search - 순차검색 - 입니다. 혹자는 Linear Search - 선형 검색 - 이라는 표현도 쓰기도 합니다. 이는 알고리즘의 특성때문에 나온 말이죠. - 사실 알고리즘이라 하기 좀 민망하긴 합니다. -_-;;;;; - Sequential Search 라는게 사실 별 것 아닙니다. 말 그대로 찾으려는 자료를 소스에서 처음부터 순차적으로 계속 검색해 나가는 거죠. 가령. S T U D Y I N G T H E L O G I C A L W O R L D 로 초기화되어 있는 기준 배열 input 에서 W 라는 .. 더보기
Algorithm #2. Search algorithm. - 2.1 검색 알고리즘의 종류. ( & Algorithm vs. Data Structure (??) ) 이제부터 포스팅해 나갈 주제는 Search algorithm 입니다. Sort algorithm과 마찬가지로 거의 모든 프로그램 - 사실상 전부 -_- 라고 해 두죠 - 에서 필수적인 알고리즘 중 하나입니다. Database 와의 연동이 없는 프로그램은 거의 없다고 해도 무방하기 때문이죠. 작게는 간단한 인원 관리 프로그램부터, 크게는 게임, OS, 그리고 서버에 이르기까지. 이런 거대한 자료 뭉치 - Database - 에서 원하는 자료를 찾아야 한다고 가정해 봅시다. 여러분들은 어떻게 하실 건가요? . . . 이런 물음에 대한 답은 이미 여러가지가 나와 있습니다. 정렬과 함께, 학계에서 가장 많이 연구되어 왔고 또한 필요성 역시 가장 높은 알고리즘 주제중 하나이기 때문이죠. - 그리고 아마 세계 어딘.. 더보기
복귀신고 -_- 크흠. 드디어 쌓이고 밀린 일들이 다 끝났군요 -_- 힘들었습니다. 예상보다 2일정도 더 늦어졌는데요... 쩝. 오늘부로 복귀 신고합니다. 아마 포스트는 오늘 오후쯤에 올라갈 것 같네요 -_-ㅋ 더보기
Reuent 포스트 연기 공지. 학교 행사 관계로 오늘 포스트 업데이트가 늦을 것 같습니다. 더보기
9 / 29. 이제 기본적인 정렬 알고리즘에 대한 포스팅이 끝났군요. 아직 포스팅 하지 않은 정렬 알고리즘이 꽤 있긴 합니다. -Selection Sort, Shell Sort, Merge Sort, Counting Sort, Bucket Sort, External Sort - 하지만, 저 중 Selection Sort 를 제외한 나머지는 그다지 잘 사용되지 않는 알고리즘들이라 제외했습니다. 그리고 Selection Sort 역시 다시 언급할 필요는 못 느꼈었구요. 하지만 역시 원하시는 분들이 있다면 - 그리고 제가 끌린다면 - 따로 포스팅하죠. -_-a 흠... 그리고 자료구조 포스팅은 아무래도 제가 하지 않는 것이 나을 것 같네요. 다른 분에게 양도하겠습니다 -_-ㅋ 원하시는 분은 댓글 다셔서 가져가시구요. 다음은.. 더보기
Algorithm #1. Sort algorithm. - 1.6 Radix Sort algorithm. 이번엔 기수 정렬, Radix Sort 대해 알아보죠. Radix Sort 는 기본적으로 비트열을 정렬 대상으로 삼는 알고리즘입니다. 그래서 숫자 배열에 대해서는 매우 효율적인 알고리즘 중 하나입니다만, 문자 배열에 대해서는 탐색해야 할 비트열이 많아지므로 그다지 효율적인 선택이 아닙니다. 이 경우엔 다른 Sort 알고리즘을 선택하는걸 추천하죠. 우선 Radix Sort 는 두 가지로 나뉘어 집니다. 1. Radix Exchange Sort(기수 교환정렬) 2. Straight Radix Sort(직접 기수정렬) 흠... 그 중 Radix Exchange Sort 는 가장 직관적인 방법이라 할 수 있겠군요. 일상생활에서 우리가 가장 즐겨쓰는 방법입니다. 보통 인간은 10진법 체계를 사용합니다. 따라서, .. 더보기
Algorithm #1. Sort algorithm. - 1.5 Heap Sort algorithm. 이번 주제는 Heap Sort 알고리즘입니다. Heap Sort 를 알기 위해선 Heap 이란 자료구조에 대한 설명이 필요하겠군요. Heap 은 일반적으로 완전 이진트리(Complete Binary Tree) 로 추상화됩니다. - 포화 이진트리와 완전 이진트리의 차이점은 알고 계시리라 생각하겠습니다. - 우선 Max - heap 을 봅시다. 각 자식 노드와 부모 노드의 값을 비교할 때, 부모 노드의 값이 자식 노드들 보다 크게끔 완전 이진트리를 구현합니다. 그리고 재귀적으로 모든 서브 트리에 대해 위와 같은 정의를 적용해 주고, 그 이후 이 완전 이진트리를 level 별로 순회해 가면서 배열에 넣어주면 Max - heap 이 완성됩니다. - 즉, 각 서브 트리 별 루트 노드의 값이 서브 트리의 레코드 중.. 더보기
Algorithm #1. Sort algorithm. - 1.4 Quick Sort algorithm. 네. 저번주에 포스팅 하는 걸 잊었습니다. ... 그래서 이제부터 일주일 내내 하나씩 포스팅하기로 약속했습니다. - Matrix 때문에 지금 Dlbo 군에게 열심히 갈굼당하고 있습니다. -_- 이건 그것도 겸한거죠. - 큼... 각설하고. 이번 포스팅 주제는 Quick Sort 알고리즘입니다. 정렬 알고리즘 중 가장 효율적이고 사용 빈도가 높은 알고리즘 중 하나입니다. - C 언어 라이브러리 함수로 qsort() 라는게 있습니다. Quick Sort 를 라이브러리화 해 놓은 거라 쉽게 사용이 가능합니다. 이것도 이유가 될 수 있겠죠. 비교 함수만 하나 더 만들어 주면 끝이거든요. - 흠... 일단 Quick Sort 를 소개하려면 'Divide and conquer' 라는 알고리즘 기법부터 설명해야 할까.. 더보기
Algorithm #1. Sort algorithm. - 1.3 Bubble Sort algorithm. 이번은 거품정렬 . Bubble Sort에 대해서 알아보죠. 간단히 말해, 이런 이름이 붙은 이유는 정렬과정의 모양 때문입니다. 한 레코드와 인접한 index들을 비교해 가장 큰 레코드 값이 한 칸 한 칸씩 옆으로 밀려나가는 모습이 마치 거품모양과 같다 하여 이런 이름이 붙었다. .... 고 합니다. -_-;;;;;;; - 전 그렇게 못 느끼겠습니다만. 제 상상력이 부족한 건가요????- last index 가 n 인 문자열 배열 a 가 있다고 가정합시다. 이 문자열을 Alphabet order 로 Bubble Sort 를 써서 정렬하고자 한다면. 레코드 값을 비교하기 위해 레코드 쌍을 마련한다. -> 이 경우, 인접한 요소끼리 레코드 쌍을 만든다. 한 레코드 쌍의 첫번째와 두번째 요소를 비교한다. ->.. 더보기
Algorithm #1. Sort algorithm. - 1.2 Insertion Sort algorithm. 흠. 두 번째 포스트군요 ㅇ_ㅇ. 이번 포스트는 앞서 언급했던 정렬 알고리즘들을 세분화하고 그 특징. 그리고 구현법에 대해 알아보죠. 우선, 가장 간단한 것부터 알아보도록 할까요. 우선 삽입 정렬(Insertion Sort)입니다. 삽입 정렬 알고리즘은 보통 카드 게임에서 카드를 정렬하는 것으로 비유하고 있습니다. 카드 몇 장을 이미 받았다고 가정하고, 카드 덱(Card deck) 에서 카드 한 장을 뽑아 손에 쥐어 봅시다. 그리고 나서 무늬에 관계없이 카드를 정렬하려 한다고 가정합시다. 여러분들은 어떻게 하시나요? 일반적으로, 이미 카드 몇 장을 받은 시점에서 카드를 정렬할 겁니다. 우선 처음 두 장을 비교하고, 값 순서대로 배열하겠죠. 그리고 나서 아마 '이미 정렬된' 두 장의 값 범위를 비교하고 나.. 더보기
Algorithm #1. Sort algorithm. - 1.1 정렬 알고리즘의 필요성, 그리고 알려진 알고리즘의 종류와 일반적 특성. 흠... 자료구조 포스팅을 먼저 한다는걸 잊고 알고리즘부터 준비했군요 -_-;;;; 정렬 알고리즘들의 포스팅이 끝난 다음엔 기초 자료구조부터 시작하죠. - ... 포스트 제목을 정말 거창하게 지어버렸네요 -_-;; - 여튼. 이번 포스팅 주제는, Sort algorithm. 즉 정렬 알고리즘입니다. 어떤 작업을 하든지 우린 '정렬작업' 이라는걸 해야하는 경우가 많습니다. 사실 우리 주위엔 정보를 정렬하는 것이 필수적인 분야들이 많습니다. 가장 대표적인 예를 들자면 고객 관리 프로그램이겠죠. 특히 중, 고등학생들의 정보를 관리하는 학생 정보 관리 시스템이라던가. 자. 물론 자료 입력시 정렬을 해서 넣는 경우도 있겠죠. 하지만 우리가 프로그래밍을 할 땐, 우리의 고객이나 서버 채점기는 '정렬을 하지 않고 자.. 더보기
Reuent - 포스팅 계획서. 흠... 안녕하십니까. Reuent 라고 합니다. 독음이 궁금하시면 '로이엔트'라 읽어주세요 -_-. 독일어의 독음을 따르시면 됩니다. - 아이디에 얽힌 비화는 제 블로그를 참조해 주시길... - 일단 이 팀의 팀블로그 관리자 -_- 를 맡고 있구요, 건의사항 등등이 있으시면 연락주시면 빠른 시간 내에 조치를 취하겠습니다. 소개는 이정도로 하고... 본론으로 들어가지요. 앞으로 제가 포스팅 할 부분은 자료구조와 알고리즘 분야입니다. 우선 기본적인 자료구조의 정의와 그 구현법을 중심으로 전개해 나갑니다. 그러나 큰 비중을 두진 않고, 단지 한번 더 기본기를 다진다는 느낌으로 합니다. 그 이후는 알고리즘을 각 카테고리별로 묶어서 포스팅합니다. 물론 그 구현법도 씁니다. 단지, 자료구조나 알고리즘이나... C.. 더보기
PKU 2390. Bank Interest [AC] #include int main(void) { int i, r, m, y; double result; scanf("%d %d %d", &r, &m, &y); result = m; for(i=0; i 더보기
PKU 2390. Bank Interest. [판정:AC] 선ㅋ빵ㅋ 아침출근이라 안풀리면 어쩌나 걱정했는데 한큐에 끝ㅋ #include #include void main() { double r; double m; int y; scanf("%lf %lf %d", &r, &m, &y); printf("%d\n", (int)floor( m * pow(1+r/100, y) )); } 더보기
PKU 2390. Bank Interest 은행 이자 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8868 Accepted: 5327 설명 Farmer John은 작년에 돈을 좀 벌었습니다. 그래서 그 돈을 어딘가에 투자하고 싶은데, 투자해서 얼마의 이익이 나올지 알고 싶어합니다. 그는 그가 이용하는 은행에서 매년 적립되는 이율 R (0부터 20 사이의 정수)을 알고 있습니다. 지금 그가 가진 돈은 100부터 1,000,000 사이의 정수 M 입니다. 근데, 그는 총 Y (0부터 400까지) 년에 걸쳐서 돈을 투자하려고 합니다. 그가 저축한 돈이 미래에 총 얼마가 되서 돌아올지를 알려주세요. 반올림 없이 정수 부분만 나타내세요. 부호가 있는 32비트형 정수로 테스트 데이터에 대한 답이 .. 더보기
PKU 2390. Bank Interest Bank Interest Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8868 Accepted: 5327 Description Farmer John made a profit last year! He would like to invest it well but wonders how much money he will make. He knows the interest rate R (an integer between 0 and 20) that is compounded annually at his bank. He has an integer amount of money M in the range 100..1,000,000. He knows how many .. 더보기
[PRJ] AMAZE v1.12 새 버전이 또-_-; 나왔습니다~ 업데이트 내용 ------------------------ [ Game Play ] - 20행 이상 또는 20열 이상의 maze에 대해 미니맵 출력 ( 미니맵에 나타나는 정보는 [ maze의 형태, 시작점·도착점의 위치, 플레이어의 위치 ]입니다 ) ------------------------ 1.10 완성되었을 때부터 생각했던건데 이번 버전에서 구현했습니다 :) ------------------------ 최근에 올라온 포스트 중에 유독 제 프로젝트 글이 많은 것 같아서 앞으로 짝수버전마다 포스팅하겠습니다 ( 제 개인블로그에는 홀수버전도 포스팅합니다 ) 업데이트가 잦다보니 그렇게 포스팅해도 텀이 아주 길진 않을 것 같아서요 -_-a 더보기
PKU 2871. A Simple Question of Chemistry. AC get -_-! main(){float p,c;scanf("%f%f",&p,&c);for(;c!=999;printf("%.2f\n",c-p),p=c,scanf("%f",&c));puts("End of Output\n");} 숏코딩작렬 더보기
파일시스템 - 03. FAT 12, FAT 16! FAT 엔트리 부분? 포스트가 쪼까 늦었네요; 아마 다음 포스트는 대략 금요일이나 토요일즈음 올라가지 싶습니다. ------------------------------------------------------------------------------------------------------------------ FAT12와 FAT16은 FAT엔트리가 각각 12, 16비트로 구성된 파일시스템입니다. 12비트로 구성된 FAT12는 주로 용량이 적은 플로피디스켓에, 16비트로 구성된 FAT16은 윈도95, 98시절 사용하던 소용량의 하드디스크에 쓰이던 파일 시스템이지요. 두 시스템이 공통적으로 갖는 부분은 "최초 1섹터인 512바이트가 부트 코드 블록" 이라는 겁니다.(사실 FAT계열은 다 이래요;) 이 부분은 BPB(Bio.. 더보기
[PRJ2] OTHELLO v1.02 AMAZE 업데이트가 늦어지다보니 자연스럽게 업데이트가 늦어진 OTHELLO입니다 :) 업데이트 내용 ------------------------ [ 1 Player Game ] - [ 1 Player Game ] 구현 ( AI 없이 무작위로 놓기 때문에 오델로를 처음 접해본 사람은 쉬움 혹은 보통, 경력자들은 매우쉬움의 난이도를 체감할 것이라 추측 ) ------------------------ 원본은 http://cm4st.tistory.com/6 :) 더보기
[PRJ] AMAZE v1.11 오래 기다리셨습니다 :) Built-in Game을 만드는 데 시간을 너무 소비한 탓에 이제야 업데이트를 합니다 =_= 업데이트 내용 ------------------------ [ 공통사항 ] - 특정 maze를 [ Custom Game ]또는 [ Load Maze ]로 불러올 경우 발생하던 오류를 수정 ( 이 오류는 이미 v1.10b에 수정되어있습니다 ) [ Game Play ] - [ Built-in Game ] 구현 ( v1.11에서 [ 난이도 5 ]는 구현되어있지 않습니다 -_-; 그건 나중버전에; ) ( 각 난이도별로 3개의 maze가 있으며, 셋 중 하나가 임의로 선택되어 등장 ) - [ Custom Game ]에서 도착점에 도달했을 때, 초기화면으로 빠져나가던 것을 게임종류선택화면으로 수정.. 더보기
PKU 2871. A Simple Question of Chemistry [AC] #include int main(void) { float prev, curr; scanf("%f", &prev); while(1) { scanf("%f", &curr); if(curr == 999) { break; } printf("%.2f\n", curr-prev); prev=curr; } printf("End of Output\n"); return 0; } 단순히 float 수 두개의 차이값만을 출력하면 되는 문제라 쉽네요. 더보기
PKU 2871. A Simple Question of Chemistry. [판정:AC] 심플하죠 =_= 마지막에 End of Output 출력하는 것만 안 잊어버리면 한방에 AC받았을텐데 -_-; #include #include using namespace std; int main() { vector v; float fl; int i, j; for( i = 0; fl != 999; i++ ) { cin >> fl; if( fl == 999 ) { continue; } v.push_back(fl); } for( i--, j = 1; j < i; j++ ) { printf("%.2lf\n", v[j] - v[j-1]); } printf("End of Output\n"); return 0; } 더보기
PKU [2871]. A Simple Question of Chemistry [AC] #include int main() { float currInput; float prevInput = 0.0; float result; scanf("%f", &currInput); while(1) { prevInput = currInput; scanf("%f", &currInput); if((int)currInput == 999) { printf("End of Output"); printf("\n"); break; } result = (currInput - prevInput); printf("%.2f", result); printf("\n"); } return 0; } In PKU Judge System. 현재 인풋값과 직전 인풋값의 차이를 출력하면 끝입니다. - 현재 실습실 컴퓨터 세팅하면서 컴파일 확.. 더보기

티스토리툴바