개발 공부 블로그

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

게임 서버의 정의 우선 목적을 명확이 해야지 서버책 한 권이라도 잘 이겨나갈 수 있을 것이다.서버가 어떤 프로그램인지 먼저 생각해보자. 온라인 게임이라 하면, 다수와 접속해서 즐기는 MMORPG 온라인 게임도 있을 것이고,디아블로3 처럼 특정 몇 명만 같이 즐기는 게임도 있다. 이런 프로그램들을 만들고 관리하는 서버 프로그래머들은 어떤 일을 할까? 신규 게임이라면 당연히 게임 서버를 만들지 않을까? 기획자들이 이것저것 새로운 게임에 대한 콘텐츠 기획을 제안할 것이고그것에 맞게 프로그램 구조를 고려해 서버 프로그램을 작성할 것이다. 물론 신생회사가 아니거나, 기존 코드가 엉망인 아닌 이상 기존에 안전성을 검증받은코드를 계승해서 제작하게 될 것이다. 요약하면, 이미 돌아올 수 없는 강(가정을 고려한 코딩)을..

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..

연결 리스트란? 필요할 때마다 바구니를 하나씩 마련해서 그곳에 데이터를 저장하고 이들을 배열처럼 서로 연결한다. 라는 개념으로 접근하면 이해하기 쉽다. 바구니 역할이 구조체가 되고, 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다. 그리고 구조체 Node의 변수를 가리켜 '노드'라 한다. 이는 데이터를 담는 바구니보다는 연결이 가능한 개체라는 사실에 중점을 두어 지은 이름이다. 이렇듯 구조체의 정의 하나만 가지고도 연결 리스트의 기본 원리라고 말할 수 있다. 이를 그림으로 표현하면 다음과 같다. 연결 리스트에서의 데이터 삽입 다음 임의 코드로 연결 리스트의 삽입 개념을 잡아보자. Node * head = NULL;// 리스트의 머리를 가리키는 포인터 변수 Node * tail = NULL;// 리스트..

으래 그냥 리스트라고 하면 연결 리스트를 종종 떠올린다. 하지만, 리스트에는 순차 리스트와 연결 리스트가 있다. 순차 리스트는 배열을 기반으로 구현된 리스트이며 연결 리스트는 메모리의 동적 할당을 기반으로 구현된 리스트이다. 하지만 이는 리스트의 구현방법의 차이에서 비롯된 것이기 때문에 이 둘의 ADT가 동일하다고 해서 문제가 될 것은 없다. 물론 각각의 특성의 차이 때문에 ADT에 차이를 두기도 한다. 이는 ADT는 각종 자료구조들의 표준이 아니기 때문이다. 정의하는 사람이나 회사에 따라서, 다시 말해 피룡에 따라서 ADT에도 차이가 난다. 물론 필요에 따라 확장도 가능하다. 하지만 그렇다고 해서 해당 자료구조의 기본 특성을 무시하는 형태로 ADT가 정의되는 것은 아니다. 리스트 ADT 정의를 위해서 ..

트리 순회 일단 트리가 구성되어 있다면, 이 트리를 다양한 방법으로 순회하여 원하는 노드에 접근할 수 잇다. 다양한 순회 방법에 대해 간략히 알아보자. 전위 순회 (preorder traversal) 이 방법은 현재 노드를 먼저 방문하고, 그다음은 현재 노드의 왼쪽 하위 노드를, 마지막으로는 현재 노드의 오른쪽 하위 노드를 재귀적인 방식으로 방문한다. 여기서 '전위(pre)'는 상위 노드를 하위 노드보다 먼저 방문한다는 뜻이다. 전위 순회는 항상 부모 노드를 방문한 다음 왼쪽 자식 노드, 오른쪽 자식 노드를 차례로 방문한다. 이러한 방식의 순호를 루트 노드에서만 수행하는 것이 아니라 루트 노드 아래의 모든 서브 트리에 대해 적용한다. 중위 순회 (in-order traersal) 중위 순회 방법은 왼쪽 ..

하노이 타워 코드 #include void HanoiTowerMove(int num, char from, char by, char to) { if (num == 1)// 이동할 원반의 수가 1개라면 { printf("원반1을 %c에서 %c로 이동 \n", from, to); } else { HanoiTowerMove(num - 1, from, to, by); printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to); HanoiTowerMove(num - 1, by, from, to); } } int main(void) { // 막대 A의 원반 3개를 막대 B를 경유하여 막대 C로 옮기기 HanoiTowerMove(3, 'A', 'B', 'C'); return 0; }