개발 공부 블로그

int main(){ IntStack s; InitializeSTK(&s, 8); for (int i = 0; i stk = (int*)calloc(max, sizeof(int)); s->max = max; s->cur = -1; return 0;}int PushSTK(IntStack* s, int x){ if (s->cur >= s->max-1) { printf("\n\n스택이 가득 찼습니다!\n추가할 수 없습니다!\n\n"); return -1; } s->cur++; s->stk[s->cur] = x; printf("\n%d의 값이 정상 저장되었습니다!\n", s->stk[s->cur]); return 0;}int PopSTK(IntStack* s, int* x){ if (s->cur stk[s-..

완벽한 해싱 n개가 n개의 버킷에 하나씩 따로따로 저장된다면 완벽한 해싱이라 볼 수 있다.입력한 데이터가 뭔지 모두 알고 있을 경우에만 가능하다. 대부분의 경우에는 입력이 정확히 어떤 것들이 들어올지미리 알 수가 없기 때문에 충돌이 최소가 되는 좋은 해시 함수를 사용할 필요가 있다.  유니버설 해싱 유니버설 해싱은 "랜덤 해싱"으로 이해하면 더 쉽다.난수를 사용하는 무작위 알고리듬이 성능을 높이는 데에 도움이 되는 예로 퀵 정렬을 들 수 있다.이와 같이 난수의 개념을 해싱 함수에 적용한 것이다. 입력이 어떤 것들인지 정확히 알 수 없는 무작위인 경우에 항상 해시값들을 고르게 분포시켜주는 함수를 만드는 것은 어렵다.때문에 유니버설 해싱에서는 해시 함수에 난수를 적용한다.  암호화 해시 함수 다양한 길이의 ..

삽입 정렬(Insertion Sort): 이해와 구현  이번에 소개하는 삽입 정렬은보는 관점에 따라서 별도의 메모리를 필요로 하지 않는 '개선된 선택 정렬'과 유사하다고 느낄 수 있다.하지만 전혀 다른 방법으로 정렬을 이뤄나간다.이와 관련해서 다음 그림을 보자.  위 그림의 배열은 정렬이 완료된 부분과 완료되지 않은 부분으로 나뉘어 있다.이렇듯 삽입 정렬은 정렬 대상을 두 부분으로 나눠서,정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에'삽입'해 가면서 정렬을 진행하는 알고리즘이다.그럼 다음 그림을 통해서 5,3,2,4,1의 오름차순 정렬 과정을 보이겠다.   위 그림의 가장 윗부분에서 보이듯이,첫 번쨰 데이터와 두 번째 데이터를 비교하여,정렬된 상태가 되도록 두 번째 데이터를 옮기면서 정렬..

동적 계획법의 접근 방식 1단계: 동적 계획법 필요조건 분석하기 부분집합의 합과 같은 문제에 직면하게 되면먼저 이 문제를 동적 계획법으로 해결할 수 있는지를 확인해야 한다.일반적으로 주어진 문제가 다음 속성을 가지고 있다면 동적 계획법으로 해결할 수 있다. 중복되는 부분 문제 : 일반적인 분할 정복 기법과 마찬가지로,최종해(final solution)는 여러 개의 부분 문제 조합으로 표현될 수 있어야 한다.그러나 분할 정복과는 달리 특정 부분 문제가 여러번 발생할 수 있다.최적 부분 구조 : 주어진 문제에 대한 최적해(optimal solution)는부분 문제의 최적해로부터 생성될 수 있다.  위 그림을 보면 크기가 n인 부분집합은 크기가 n - 1인 부분집합에 새로운 원소 하나를 추가하여 만들 수 있다..

우선순위 큐의 구현 방법 우선순위 큐를 구현하는 방법은 다음과 같이 세 가지로 구분할 수 있다. 배열 기반 구현연결 리스트 기반 구현힙을 이용하는 방법 배열이나 연결 리스트를 이용하면 우선순위 큐를 매우 간단히 구현할 수 있다.참고로 다음 그림에서, 저장된 숫자는 데이터인 동시에 우선순위 정보라고 가정하였다.숫자 1이 가장 높은 우선순위를 뜻하며, 이보다 값이 커질수록 우선순위는 낮아진다고 가정하였다.  배열의 경우, 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시킨다.이렇게 하면 우선순위가 높은 데이터를 반환 및 소멸하는 것이 어려운 일이 아니다.하지만 다음과 같은 단점이 따른다. 데이터를 삽입 및 삭제하는 과정에서데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야한다. 이..

동적 계획법이란?1. 메모이제이션2. 타뷸레이션3. 부분집합의 합 문제4. 문자열과 시퀀스에 대한 동적 계획법해당 게시물은 다음 작업을 수행할 수 있는 지식을 담았다. 주어진 문제에 동적 계획법을 적용할 수 있는지 분석하는 능력메모이제이션과 타뷸레이션 기법을 서로 비교하여 적절한 방법을 선택함메모이제이션을 위한 적절한 캐시 사용 방법을 찾을 수 있음직관적인 전수 조사 방법을 사용하여 주어진 문제를 분석점진적으로 최적화 알고리즘을 구현하면서 동적 계획법 해법을 개발할 수 있는 능력 해당 게시글에서는 동적 계획법에 대해 소개하겠다.그리고 컴퓨터 과학 분야에서 널리 알려진몇몇 문제를 동적 계획법으로 해결하는 방법에 대해 알아보겠다. 많은 프로그래머가 좋아하기도하고 동시에 두려워하기도 하는 동적 계획법은분할 정..

Tree + (heap)   트리는 매우 중요한 자료구조 중 하나이다.연결리스트는 노드들이 한 줄로 연결된 선형적인 자료구조인 반면트리는 부모 - 자식 관계를 계층적으로 표현한 보다 일반적인 자료구조이다. 추상적으로 표현하면 연결 리스트처럼 데이터를 저장하고 있는 노드와 노드를 연결하는 에지(또는 링크)로 구성된다.연결 리스트와 차이점은 에지가 부모 - 자식 관계를 표현한다는 점에서 차이가 있다. 트리 용어 부모노드 / 자식노드 : 부모노드는 자식 노드를 위에 있는 노드를 말한다.자식 노드는 1이상의 레벨을 가지는 노드로 부모노드 밑에 있는 노드이다. 조상노드 / 자손노드 : 트리 노드간의 레벨간의 관계가 2이상 차이나는 노드를 말한다.보다 아래면 자손노드 보다 위면 조상노드라고 한다. 루트노드 : 모든..

// 삽입 정렬 { int arr[] = { 1,2,4,5,3,6 }; int size = sizeof(arr) / sizeof(arr[0]); Print(arr, size); int i = 4; int key = arr[i]; int j = i; for (j = i; j > 0 && arr[j-1]>key; j--) { if (arr[j - 1] key; j--) { arr[j] = arr[j - 1]; cout

#include #include #include #include #include #include #include #include #include using namespace std; bool CheckeSorted(int arr[], int size) { if (arr[0]

static int ListNum = -1; class List { public: List* CurPtr = this; List* BeforePtr = nullptr; List* AfterPtr = nullptr; int Index = 0; int Value = 0; bool IsDummy = false; ~List(); }; // 빈 List 생성 void InitialList(); // 원하는 만큼의 수와 해당 값으로의 초기화된 List 생성 void InitialList(int MaxIndex, int Value); // 부분 삭제 void DeleteIList(int iter, List* InDeleteList); // 전체 삭제 void DeleteAllList(); // 삽입 void Push..