C 언어로 연결 리스트 구현 정글에서 5주차가 진행되고 RB-Tree를 구현하는 과제가 주어졌다. 그것도 C 언어를 이용해서 RB-Tree의 자료구조를 구현해야 하는데, C 언어에 대한 문법도 익숙치 않을 뿐더러 RB-Tree 자료구조 구현 자체가 쉽지 않다기에 비교적 쉬우면서도 선수지식으로 알아야 할 '연결 리스트'와 '이진 검색 트리'를 C 언어를 구현해 봄으로써 C 언어를 익히고, RB-Tree를 구현하고자 한다. Operator 1. 연결리스트 구조체 만들고 사용하기 연결 리스트에서 노드를 추가하는 규칙 노드에 메모리 할당 next 멤버에 다음 노드의 메모리 주소 저장 data 멤버에 데이터 저장 마지막 노드라면 next 멤버에 NULL 저장 아래 이미지는 사용자가 정의한 구조체를 이용해 연결리스..

그리디 알고리즘이란? 그리디 알고리즘은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘이다. 그리디 알고리즘(Greedy Algorithm)란 바로 눈 앞의 이익만을 쫓는 알고리즘이다. 대부분의 경우에는 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 최적해를 찾을 수 있으면 그것을 목표로 삼고, 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다. 이러한 특성때문에 '욕심쟁이 알고리즘'이라는 별명이 붙은 알고리즘이기도 하다. 아래 이미지를 보면 큰 값을 찾기 위한 '그리디 알고리즘의 동작방식과 실제 큰 값은 다르다.'는 것을 알 수 있다. (진짜 욕심쟁이네....

다이나믹 프로그래밍(dynamic programming, DP)이란? 다이나믹 프로그래밍은(DP) 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 구하는 알고리즘 설계 기법이다. 앞에서 구했던 답을 뒤에서도 이용하고, 또 그 뒤에서도 이용할 수 있다. 쉽게 말해서는 답을 재활용하는 것이고, 같은 말로 프로그래밍 영역에서는 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. DP는 구체적인 알고리즘이라기 보다는 문제해결 패러다임에 가깝다. DP는 아래와 같은 특징이 있다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 DP의 구현은 일반적으로 두 가지(탑다운 - 하향식, 바텀업 - 상향식) 방식으로 구현함 ..

그래프 순회(Graph Traversal) 그래프 순회란 그래프 탐색(Search)이라고도 불리우며, 그래프의 각 정점을 방문하는 과정을 말한다. 그래프의 각 정점을 방문하는 그래프 순회(Graph Traversls)에는 크게 깊이 우선 탐색 DFS(Depth-First Search, DFS)과 너비 우선 탐색 BFS(Breadth-First Search, BFS) 2가지 알고리즘이 있다. 두 가지 모두 탐색 알고리즘에 해당한다. DFS는 주로 스택 또는 재귀로 구현한다. BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용된다. 깊이 우선 탐색 - DFS(Depth-First Search, DFS) 깊이 우선 탐색은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고..

그래프(Graph) 비선형 자료구조인 그래프 또는 트리에서 자료를(원소) 보관하는 것을 정점(Vertex) 혹은 노드(Node)라고 부르며, 정점에서 다른 정점으로 가는 경로를 간선(Edge) 혹은 링크(Link, 다른 노드의 위치 정보)라고 부른다. 이를 통해 연결된 노드 간의 관계를 표현할 수 있다. 즉, 연결 관계를 표현하는 자료구조라고 할 수 있다. 아래의 이미지처럼 그래프는 트리보다 더 넓은 범위라고 할 수 있다. 그래프의 종류 방향 그래프(Directed Graph), 무방향 그래프(Undirected Graph) 무방향 그래프는 간선을 통해 양방향으로 갈 수 있다. 방향 그래프는 간선의 방향이 존재하는 그래프로 한 방향으로만 갈 수 있다. 노드 사이에 양방향으로 표시된 간선은 양방향으로 통행..

1. 컴퓨터 시스템으로의 여행 컴퓨터 시스템은 하드웨어와 시스템 소프트웨어로 구성되며, 이들이 함께 작동하여 응용프로그램을 실행한다. 모든 컴퓨터 시스템들은 유사한 기능을 수행하는 유사한 하드웨어와 소프트웨어 컴포넌트를 가지고 있다. HTML 삽입 미리보기할 수 없는 소스 이들 컴포넌트들이 어떻게 동작하고, 프로그램의 성능과 정확성에 어떤 영향을 주는지 알아야 프로그램을 더 잘 개발할 수 있다고 한다. CSAPP에서 배우는 주요 내용 컴퓨터가 숫자를 표시하는 방법 때문에 생기는 이상한 숫자 에러를 피하는 방법 최신 프로세서와 메모리 시스템의 설계를 활용하는 효과적인 기법을 사용해 C 코드를 최적화하는 방법 컴파일러가 프로시저 호출을 어떻게 구현하는지 인터넷과 네트워크 소프트웨어를 감염시키는 버퍼 오버플로..