지식/자료구조 (10) 썸네일형 리스트형 [자료구조] 후위 수식(Postfix) 이번 포스팅에서는 후위 수식에 대해서 알아보겠습니다. 수식을 표현하는 방법은 크게 3가지가 있습니다. infix notation : a * b (연산자가 피연산자 사이에 위치합니다.) prefix nonation: * a b (연산자가 피연산자들 앞에 위치합니다.) postfix nonation: a b * (연산자가 피연산자들 뒤에 위치합니다.) 이 결과들은 모두 a와 b를 곱한 값을 의미합니다. 이중에서 우리에게 익숙한 방식은 infix notation일 겁니다. 하지만 infix notation은 약간의 단점이 존재합니다. 연산자들이 가지는 우선 순위가 있지 때문에 이에 맞춰서 연산을 해야한다는 문제점이 있습니다. 따라서 임의로 연산자의 우선순위를 조정하기 위해서는 괄호를 사용해야하는 번거로움이 생.. [자료구조] 큐(Queue)... So cute... 안녕하세요. 오늘은 자료구조 큐에 대해서 알아보겠습니다. 큐는 스택과 비슷합니다. 하지만 작동하는 방식이 약간 다르고 스택의 탑과 바텀을 큐에서는 다른 말로 표현합니다. 스택에서 요소를 스택의 탑에 추가했던 것처럼 큐는 rear(or back)에서 요소를 추가합니다. 또한 요소의 삭제는 스택의 탑에서 일어났지만 큐는 front에서 일어납니다. 큐는 스택처럼 가장 먼저 입력된 데이터가 맨 아래 쌓이고 가장 나중에 입력된 데이터는 맨 위에 쌓이는 구조입니다. 하지만 스택에서처럼 입출력이 맨 위에서만 일어나지 않습니다. 위에서 설명드린바와 같이 입력은 rear 출력은 front에서 일어납니다. 이러한 구조를 FIFO(First in, First out)이라고 합니다. 먼저 들어온 녀석이 먼저 나간다는 것입니다.. [자료구조] (Stack)스택이 뭐여 먹는겨? 안녕하세요 이번 포스팅은 자료구조 스택에 대하여 알아보겠습니다. 스택은 일단 쌓다라는 뜻인데요. 탑처럼 데이터를 쌓는 것을 상상하시면 좋습니다. 스택은 가장 먼저 입력된 데이터가 맨 아래 쌓이고 가장 최근에 입력된 데이터는 가장 위에 쌓이는 구조를 가지고 있어요. 이 구조를 LIFO(Last In, Final Out) 이라고 합니다. 그래서 항상 스택의 입출력은 맨 위에서만 일어납니다. 이 부분 즉 스택의 맨 위를 스택 상단(stack top) 이라고 합니다. 반대로 스택의 맨 밑바닥 부분은 스택 하단(stack bottom) 이라고 합니다. 이 각각의 스택에 저장되는 데이터를 요소(elements)라고 합니다. 여기서 삽인 연산(push) 와 삭제 연산(pop)이 일어납니다. 삽입 연산(push)는 스.. [자료구조] KMP(Knuth-Morris-Pratt) Algorithm KMP 알고리즘은 문자열 내에서 특정 패턴을 엄청나게 빠르게 찾아주는 알고리즘입니다. 해당 패턴의 위치를 빠르게 알 수 있지요. KMP알고리즘은 이전 포스팅의 마지막에 다루었던 패턴을 찾는 방법처럼 스트링과 패턴의 불일치가 발생했을 때 최대한 중복된 연산을 피하면서 문자열과 비교할 수 있도록 합니다. 이렇게 하기 위해서는 먼저 얼마나 중복연산을 피할것인지 판단하기 위한 값들이 필요합니다. 이를 failture function이라고 한다. failure function은 패턴문자열의 접두사와 접미사의 일치하는 부분을 계산하고 이를 fail 배열에 저장합니다. fail 배열의 첫 번째 인덱스의 값은 -1로 설정합니다. 인덱스의 의미는 현재 패턴의 문자가 패턴의 첫문자부터 #번째 문자까지 일치한다는 것을 말합.. [자료구조] 문자열(Strings) 문자열이란 한정된 순서를 가진 크기가 0이상인 문자들의 집합을 말합니다. C에서는 배열을 통해서 문자열을 나타낼 수 있습니다. #define MAX_SIZE 100 char s[MAX_SIZE] = "dog"; char t[MAX_SIZE] = "house"; 또한 선언할 때에는 다음과 같이 선언할 수도 있습니다. char s[] = "dog"; char t[] = "house"; 이때에는 문자의 개수+1개 만큼 크기가 자동으로 할당 됩니다. 하지만 다음과 같이 선언할 수 없습니다. char u[]; //compile error 배열을 초기화하지도 않고, 크기도 정해주지 않는다면 컴파일 에러가 발생합니다. 이번에는 strcat 함수를 이용하여 문자열에 대해 더 알아보겠습니다. #include #inclu.. [자료구조] 희소 행렬 (Sparse Matrix) Sparse Matrix는 행렬의 대부분의 요소가 0인 행렬입니다. 이와 반대로 0이 대부분이 아니라면 Dense Maxtrix라고 합니다. 다음과 같이 행렬에 수많은 0이 보이는 것을 알 수 있는데 이를 Sparse Matrix라고 합니다. 만약 행렬의 크기가 엄청나게 큰 상황이라면 엄청난 공간낭비가 따라올 수 밖에 없습니다. Sparse Matrix의 표현은 다음과 같이 합니다. 행,열,값으로 특정할 수 있다. 행이 오름차순이 되도록하며, 행이 동일하면 열이 오름차순이 되도록한다. 작업이 종료되면 행의 개수, 열의 개수, 0이 아닌 값의 개수를 알도록 한다. 따라서 위의 그림을 다시 나타낸다면 다음과 같이 나타낼 수 있습니다. a[0]에는 행의 개수, 열의 개수, 0이 아닌 값들의 총 개수가 들어갑니.. [자료구조] 다항식 (Polynomials) 배열을 사용하여 다항식을 관리할 수 있습니다. 많은 방법들이 있지만 대표적으로 Dense representation 과 Sparse representation이 있어요. Dense representation은 모든 다항식의 항과 계수가 0인 모든 항을 포함하는 것을 말합니다. Dense representation의 장점으로는 아주 간단한 연산 방법으로 다항식을 계산할 수 있다는 것입니다. 하지만 여전히 문제점이 있어요. 모든 다항식의 항과 계수가 0인 모든 항을 포함하다 보니 공간의 낭비가 생길 수 밖에 없고, 대부분의 항들이 계수가 0인 상황이 더 많을 겁니다. 그래서 Sparse representation을 사용하기도 합니다. Sparse representation은 각각의 다항식의 항들이 지수와 계.. [자료구조] 구조체와 공용체 (Structures and Unions) 이번에는 구조체와 공용체에 대해서 알아보겠습니다. 먼저 구조체는 데이터 요소들의 집합이라고 할 수 있습니다. 각각의 데이터 요소들은 타입과 변수의 이름을 통해 구별됩니다. 이해를 돕기 위해 예를 먼저 들어보겠습니디. struct { char name[10]; int age; float salary; } person; 위의 구조체는 현재 이름이 person이고 3개의 fields를 가진다고 말합니다. 또한 이때 구조체의 크기는 fields의 크기의 합입니다. 여기서는 char: 10byte, int: 4byte, float: 4byte 이므로 18byte가 구조체의 크기가 됩니다. 구조체의 field에 접근할때는 . 이라는 operator를 사용합니다. strcpy(person.name, "james");.. 이전 1 2 다음
