우선순위 큐(Priority Queue)란? 일반적으로 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 구조 즉 먼저 들어온 데이터가 먼저 나가는 구조를 가집니다. PriorityQueue는 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조입니다. 우선순위 큐는 힙을 이용하여 구현하는 것이 일반적입니다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행됩니다. Priori..
Queue란? Queue의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미하는데 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조입니다. 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가집니다. FIFO 형태는 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말합니다. Enqueue : 큐 맨 뒤에 데이터 추가 Dequeue : 큐 맨 앞쪽의 데이터 삭제 Queue의 특징 1. 먼저 들어간 자료가 먼저 나오는 구조 FIFO(First In FIrst Out) 구조 2. 큐는 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행함 3. 다른 한 쪽 끝은 리어(rear)로 정..
Stack이란? 자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'입니다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다. Stack의 가장 큰 특징은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띈다는 것입니다. 이 방식을 가진 자료구조인 Stack을 활용하여 다양한 문제를 해결할 수 있습니다. 자바에서 Stack은 java.util.Stack을 import하면 바로 사용할 수 있습니다. Stack의 특징 1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조 2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함 3. 인터럽트처리, 수식의 계산, 서브루틴의 복..
에라토스테네스의 체란? 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이며 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부릅니다. 특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2 ~ N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식이며 일종의 노가다 방식이라 상당히 무식한 방법이지만 이 방식이 프로그래밍에서는 상당히 효율적인 방법론이 됩니다. 에라토스테네스의 체는 반대로 2부터 배수들을 지워나가는 방식이기 때문에 숫자마다 일일이 약수가 있는지 검사할 필요가 전혀 없고, 이미 지워진 숫자는 바로 건너뛰면 되니 실행시간이 매우 짧습니다. 특정 범위에서의 모든 소수를 찾을때 가장 효율적인 알고리즘 에라토스테네스..
유클리드 호제법이란? 유클리드 알고리즘(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘입니다. 비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를 활용한 알고리즘입니다. ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8 구현 (C / C++) 재귀 함수 활용 int GCD(int a, int b) { if(b==0)return a; else return GCD(b,a%b); } 반복문 활용 int GCD(int a,int b){ while(1){ int r = a%b; if(r==0) r..
queue란? queue의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미하는데 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조입니다. 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가집니다. FIFO 형태는 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말합니다. queue는 C++ 표준 라이브러리(Standard Template Library)에 있는 정의 되어 있어 필요할 때마다 만들어 사용하지 않고 include 하여 사용하시면 편리합니다. Enqueue : 큐 맨 뒤에 데이터 추가 Dequeue : 큐 맨 앞쪽의 데이터 삭제 queue의 특징 1. 먼저 들어간 자료..
stack이란? 자료 구조 중 하나인 stack의 사전적 정의는 '쌓다', '더미'입니다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다. stack은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띠는 자료구조입니다. 이 방식이 stack의 가장 큰 특징이자 스택을 사용하는 이유라고 할 수 있습니다. stack은 C++ 표준 라이브러리(Standard Template Library)에 있는 정의되어 있어 필요할 때마다 만들어 사용하지 않고 include 하여 사용하시면 편리합니다. stack의 특징 1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조 2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 ..
vector란? vector는 C++ 표준 라이브러리(Standard Template Library)에 있는 컨테이너로 사용자가 손쉽게 사용하기 위해 정의된 class입니다. vector의 가장 큰 장점은 동적으로 원소를 추가할 수 있으며 크기가 자동으로 늘어난다는 점입니다. 쉽게 말해 크기가 가변적으로 변하는 배열이라고 할 수 있습니다. 속도적인 측면에서는 배열에 비해 떨어지지만 메모리를 효율적으로 관리할 수 있다는 장점이 있어 굉장히 많이 사용합니다. vector는 배열과 마찬가지로 원소들이 하나의 메모리 블록에 연속하게 저장됩니다. 그렇기에 원소가 추가되거나 삽입될 때 메모리 재할당이 발생할 수 있고 상당한 부하가 발생하게 된다는 점은 단점으로 꼽히고 있습니다. vector 구조 vector를 생성..
정렬이 필요할때마다 직접 만들어서 사용할수도 있겠지만 매번 만들어서 사용하기는 번거롭습니다. 간편하게 정렬을 하고 싶다면 직접구현보다는 헤더를 include하여 그 안에 있는 sort()함수를 사용하시면 간편하게 정렬을 할 수 있습니다. sort() 함수는 C++ STL에서 제공하는 함수로써 각종 알고리즘 문제를 풀 때도 활용할 수 있어 자주 쓰이는데, 이 함수의 시간 복잡도는 nlogn입니다. 이 함수는 intro sort라는 정렬 방식을 바탕으로 구현되어 있는데 이 방식은 quick sort를 기반으로 heap sort와 insertion sort를 섞은 방식으로 최악의 경우 n^2의 시간 복잡도를 가지는 quick sort와는 달리, 최악의 경우에도 nlogn을 보장하는 정렬 알고리즘입니다. 배열의..
두 개의 문자열이 같은지 비교하고 싶다면 strcmp, strncmp함수를 사용하면 됩니다. strcmp함수는 비교대상 문자열인 string1 string2이 같은지 비교합니다. strncmp는 문자열을 비교한다는 것에서 일정 길이만큼 비교할 수 있는 옵션이 추가된 함수입니다. 위의 두 함수는 널로 끝나는 스트링에서 작동합니다. 그렇기에 함수에 대한 스트링 인수는 스트링 끝을 나타내는 널 문자(\0)를 포함해야 합니다. strcmp() : 두 문자열이 같으면 0을, 같지 않으면 0이 아닌 값을 반환합니다. strncmp() : 두 문자열의 원하는 길이만큼 같으면 0을, 같지 않으면 0이 아닌 값을 반환합니다. 두 함수의 리턴값은 비교 대상의 어떤 문자열이 더 크냐에 따라 달라지게 되는데 문자열의 크기는 ..
strcat와 strncat 함수는 두 문자열을 이어 붙여주는 기능을 합니다. 첫 번째 주소에 저장된 문자열에 두 번째 주소에 저장된 문자열을 붙여서 반환합니다. 두 함수는 문자열을 이어 붙인다는 형태는 동일하며 strncat는 일정 길이만큼 추가할 수 있는 옵션이 추가된 함수입니다. 위의 두 함수는 널로 끝나는 스트링에서 작동합니다. 그렇기에 함수에 대한 스트링 인수는 스트링 끝을 나타내는 널 문자(\0)를 포함해야 합니다. strcat() :문자열A에 원하는 문자열B를 문자열A 뒤쪽에 이어 붙이는 함수 strncat() :문자열A에 원하는 문자열B의 n개를 문자열A 뒤쪽에 이어 붙이는 함수 strcat(s2, s1)과 같이 strcat 함수에 최종 결과가 나올 문자열과 붙일 문자열을 넣습니다. 위의 ..
C언어 혹은 C++에서 자신이 원하는 문자열을 잘라낼 때 사용하는 함수로 strtok라는 함수가 있습니다. 이 함수는 string token의 약자로 인자 값으로 전달받은 매개변수를 구분자로 하여 문자열을 잘라내어 return 합니다. 만약 더 이상 자를 문자열이 없다면 NULL을 반환합니다. 문자열을 자르는 방식 M Y N A M E I S T O M \0 M Y \0 N A M E I S T O M \0 M Y \0 N A M E \0 I S T O M \0 M Y \0 N A M E \0 I S \0 T O M \0 C언어 또는 C++에서 문자열은 \0으로 종료가 되게 되어있습니다. 그렇기에 인자로 받은 문자열에서 구분자가 있는 위치를 널 포인트로 치환해줌으로써, 문자열을 끊기게 만듭니다. 예를 들..
C언어에서 문자열을 복사하고 싶다면 strcpy이나 strncpy함수를 사용하시면 됩니다. 두 함수의 차이는 복사할 문자열의 길이를 설정하느냐만 다를 뿐 기본적으로 문자열을 복사한다는 것은 같습니다. strcpy() : 대상 문자열 전체를 복사한다. strncpy() : 대상 문자열을 일정 길이만큼 복사한다. strcpy, strncpy 함수 형식 char* strcpy(char * dest, const char* src); char* strncpy(char* dest, const char* src, size_t num); dest : 복사를 받을 대상의 시작 주소 src : 복사를 할 원본의 시작 주소 num : 복사를 할 문자의 개수 ※ size_t는 해당 시스템에서 어떤 객체나 값이 포함할 수 있는..