본문 바로가기

분류 전체보기

 (127)
점근적 표기법 이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;) big-Θ표기법이란, 어떤 알고리즘을 실행함에 있어서, 실행 횟수인 n이 충분히 커졌을 때의 근접한 한계값 big-Θ표기법을 사용하는 것은 실행 시간에 대해 점근적으로 위, 아래에 근접한 한계값이 있다고 표현하는 것 "점근적으로"라는 말을 쓰는 이유는 큰 값의 n에 대해서만 적용되기 때문 "근접한 한계값"이라는 말은 위, 아래로 상수값 내에서 실행 시간을 좁힐 수 있다는 뜻 Big-Θ 표기법은 실행 시간에 대하여 위아래에 점근적으로 근접한 한계가 있지만 한계를 위에만 둘 때도 있음 때로는 "실행 시간은 최대한 이만큼 커지지만 더 천천히 커질 수도 있다"는 의미인 점근적 표기법 형태를 사용하는 것이 편리할 수도 있음. 이런 경우..
[JAVA] Quick Union Improvements 이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;) 저번 포스팅에서 다뤘던 Quick Union은 Quick Find에 비해 union 연산이 빠르다는 장점을 다뤘지만, 트리의 크기가 커질 수 있다는 단점을 가지고 있었습니다. 이번 포스팅에서는 Quick Union에서 트리의 크기에 따라 발생할 수 있는 문제를 해결하는 알고리즘에 대해 알아보겠습니다. 첫 번째 개선 알고리즘은 Weighted 알고리즘입니다. 이 알고리즘은 union 연산에서 트리를 만들 때, union 연산에서 매개변수로 받는 인자들의 순서에 관계 없이, 더 작은 트리를 가진 쪽이 더 큰 트리를 가진 쪽의 자식 노드로 들어가는 방법입니다. 이를 통해 크기가 큰 트리가 작은 트리의 자식 노드로 들어가 트리의 크기..
[C언어] 전화번호부 v.3 이번 포스팅에서는 이전 포스팅에서 구현했던 전화번호부를 보완해서, 1. 옳지 않은 명령어를 걸러내고 토크나이징(tokenizing)해서 2. 저장된 사람의 수가 배열의 용량을 초과할 경우 동적 메모리 할당으로 배열의 크기를 키우는 기능을 추가하겠습니다. 명령어 오류를 처리하기 위해선 이전의 전화번호부처럼 buf에 하나의 단어만 저장해서 명령어를 처리하는 것이 아니라, 한 줄 단위로, 즉 엔터(\n) 키를 입력받기 전까지의 문자열을 통째로 처리해야 합니다. 1. 문자열을 줄 단위로 읽어서 토크나이징(tokenizing) int read_line(char str[], int limit)// limit으로 받은 길이 만큼의 문자열을 읽어냄 { int ch, i = 0; // getchar()는 한 개의 문자만..
세상에 온갖 쉬운 말들 어느 시대든, 호시절이든 보릿고개든, 그 와중에 쉬운 말들이 존재한다. 그 중에는 남을 현혹하는 말들이 많고, 또 그 중에는 그걸 말하고 다니는 것을 당당하게 여기는 이들마저 존재한다. 나는 아직도 울타리 안에 살고 있지만, 건너 보고 건너 들은 세상은 쉽지 않은 것 같다. 쉽지 않은 세상에 쉽다는 말을 쉽게 하는 자들의 말을 듣고 싶지 않다. 어려운 세상이고 쉽지 않은 길이라면, 그걸 수긍하고 그에 맞춰 열심히 하는 수밖에 없지 않을까 싶다. 쉽지 않은 길은 고난과 그 궤를 같이 하는 경우가 많겠지만, 그럼에도 고난의 궤를 벗어나는 어려운 길에 즐거움이 있고 기쁨이 있으면 좋겠다.
[C언어] 전화번호부 v.2 char* numbers[CAPACITY];// 전화번호는 그냥 '010-1234-5678'같이 문자열로 다루는 게 편함 int n = 0;// 저장되는 사람의 수 void add(); void find(); void status(); void remove(); void load(); void save(); int main() { char command[BUFFER_SIZE]; while (1) { printf("$ "); scanf_s("%s", command); // 사용자로부터 명령어를 받음 if (strcmp(command, "read") == 0)// 명령어와 두 문자열을 비교. 두 문자열이 동일하면 0를 리턴 load(); else if (strcmp(command, "add") == 0) a..
[JAVA] Quick Union 이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요 ;) 이전 포스팅에서 다뤘던 Quick Find 알고리즘은 union 연산에 있어서 모든 배열에 한 번씩 접근을 해야 하기 때문에 시간 비용 측면에서 매우 비싸고expensive 비효율적이라는 사실을 확인했습니다. 이번 포스팅에서는 그 union 연산을 조금 더 효율적으로 처리할 수 있는 Quick Union 알고리즘에 대해 알아보겠습니다. Quick Union 알고리즘은 루트(root)라는 개념을 사용합니다. union 연산을 처리할 때 연결된 모든 멤버들에 접근하여 값을 변경하는 것이 아니라, union 연산을 통해 연결을 할 때 자식 노드로 멤버를 저장시키고 자신은 root가 되는 방식입니다. 이 그림을 보면 Quick Un..
[JAVA] Quick Find 이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;) Quick-Find는 위와 같이 하나의 배열이 존재할 때, 그 배열의 인덱스에 저장된 값들을 다른 인덱스에 저장된 값들과 연결시키고(union), 또 연결되었는지 확인하는(connected) 알고리즘의 한 유형입니다. 그 구조를 도식화한 것이 위의 그림입니다. Union의 기본 구조는 위와 같습니다. union()에 두 인덱스 값을 줬을 때, 앞의 인덱스에 저장된 값을 뒤의 인덱스에 저장된 값으로 변경하는 방식입니다. public class QuickFind { private int[] id; public QuickFind(int N){ id = new int[N]; for(int i=0; i
[C언어] 전화번호부 v.1 #include #include #define CAPACITY 100 #define BUFFER_SIZE 20 char* names[CAPACITY];// 배열의 각 칸에 저장되는 데이터의 타입. 사람 이름의 주소를 저장하는 배열 = char* char* numbers[CAPACITY];// 전화번호는 그냥 '010-1234-5678'같이 문자열로 다루는 게 편함 int n = 0;// 저장되는 사람의 수. void add(); void find(); void status(); void remove(); int main() { char command[BUFFER_SIZE]; while (1)// 사용자가 빠져나가기 전까지 무한반복 { printf("$ "); scanf("%s", command); // ..

티스토리툴바