미처 완성되지 못한 알고리즘

테이블의 시간 복잡도는 O(1)이다. 테이블에 저장되는 데이터는 키와 값이 하나의 쌍을 이룬다. 키가 존재하지 않는 값은 저장할 수 없으며, 모든 키는 중복되지 않는다.

이진 탐색 트리의 탐색 연산은 O(log2n)의 시간 복잡도를 가진다. 이러한 이진 탐색 트리는 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보인다. 이것이 이진 탐색 트리의 단점이며, 이 단점을 해결한 트리를 가리켜 '균형 잡힌 이진 트리'라 불리운다. 그 종류는 다음과 같이 5가지가 된다. 1.AVL 트리2.2-3 트리3.2-3-4 트리4.Red-Black 트리5.B트리 AVL트리는 노드가 추가될 때, 그리고 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 멋진 트리다. AVL트리에서는 균형의 정도를 표현하기 위해서 균형 인수라는 것을 사용하며 이 균형 인수는 다음과 같이 계산된다. 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 AVL 트리는 ..

일반적으로 큐는 FIFO 구조로, 먼저 입력된 데이터가 먼저 출력되지만 우선순위 큐는 각 데이터의 우선순위에 따라 나중에 입력된 데이터가 더 먼저 출력될 수도 있다. 우선순위 큐의 구현 방법에는 3가지가 있다. 1.배열2.연결 리스트3.힙 여기서 1,2방식은 각 각 문제점이 있다. 1. 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 한다.2.삽입의 위치를 찾기 위해서 최악의 경우 저장된 모든 데이터와 우선순위의 비교를 진행해야 될 수도 있다. 2의 경우는 1,2방식 모두에게 해당하며 1의 경우는 1의 방식에 해당된다. 그래서 우선순위 큐는 힙이라는 자료구조를 이용해서 구현하는 것이 일반적이다. 힙이란? 이진트리이되 완전 이진 트리이며, 모든 노드..

트리는 선형 자료구조인 스택과 큐와 다르게 비선형 자료구조이다. 선형 자료구조들은 보통 삽입,삭제 등 기능에 초점이 맞춰져 있다면 트리는 '표현'에 초점이 맞춰져 있다. 즉, 트리는 계층적 관계를 표현하는 자료구조이다. 트리가 표현할 수 있는 것들 중 예를 들자면, 디렉터리 구조나 기업의 조직도 등이 있겠다. 트리 관련 용어: 1.노드 트리의 구성요소에 해당하는 데이터. 2.간선 노드와 노드를 연결하는 연결선 3. 루트 노드 트리 구조에서 최상위에 존재하는 노드 4.단말 노드 아래로 또 다른 노드가 연결되어 있지 않은 노드 5.내부 노드 단말 노드를 제외한 모든 노드 6.조상 노드 특정 노드의 위에 위치한 모든 노드를 가리켜 '조상 노드'라 한다. 7.후손 노드 특정 노드의 아래에 위치한 모든 노드를 가..

큐는 스택과 함께 대표적인 자료구조 중 하나인데, 스택과는 다르게 큐는 선입선출이라고 하여 먼저 입력된 자료가 먼저 출력된다. 이러한 큐의 예는 실생활에서도 여럿 찾아볼 수 있는데 그 중 하나가 은행에서 순번대로 업무처리 하기 등 순서대로 처리하는 업무가 하나지 아닐까 싶다. 큐를 변형된 형태로 덱이라고 있는데, 이는 앞에서도 삽입,삭제가 가능하며, 뒤에서도 삽입,삭제가 가능한 자료구조이다.

윈도우 프로그램은 크게 메인 부분과 메시지 처리 부분으로 나뉜다. 메인 부분: 윈도우를 만들고 화면에 윈도우를 띄dㅔ서 발생하거나 응용 프로그램과 관련해 발생하는 모든 메시지를 전송하는 역할. 메시지-> 이벤트가 발생하면 오는 신호. 신호는 윈도우 커널이 보낸다. 콘솔모드 C언어는 메인함수가 main()이지만, 우니도우 프로그램의 메인 함수는 WinMain()이다. 윈도우 프로그램에서는 WinMain()에서 보내온 메시지를 처리하기 위해 메시지 처리 함수가 필요하다.WndProc()수 이름은 WinMain()에서 윈도우 클래스를 등록할 떄 같이 등록되어야 한다. WinMain()함수는 메시지 큐에서 차례대로 메시지를 꺼내어 WndProc()함수로 보낸다.

스택은 FILO(first in last out) 또는 LiFO(Last in First out )으로 선입후출,후입선출. 즉, 처음 들어간 데이터가 가장 마지막에 나오는 구조이다. 스택은 한방향에서 데이터의 인풋, 아웃풋이 이뤄진다. 계산기에서 자주 사용된다. 중요 ADT로는 데이터 입력을 Push, 데이터 출력을 Pop이라 한다.

Undo기능을 추가할 때 유용하다. abstract class Command { protected Receiver m_receiver; public Command(Receiver receiver) { m_receiver = receiver; } public abstract void Execute(); } class ConcreteCommand : Command { public ConcreteCommand(Receiver receiver) : base(receiver) { } public override void Execute() { m_receiver.Action(); } } class Receiver { public void Action() { Console.WriteLine("Called Receiv..

상태 체크를 하여, 변경 시 결과에 따라 수행시킬 수 있다. 주로 UI에 쓰인다. abstract class Observer { public abstract void Update(); } abstract class Subject { private List m_observers = new List(); public void Attach(Observer observer) { m_observers.Add(observer); } public void Detach(Observer observer) { m_observers.Remove(observer); } public void Notify() { foreach (Observer o in m_observers) o.Update(); } } class Concret..

어댑터 패턴: 기존에 쓰던 메소드나 클래스를 새로운 클래스에 매핑을 해준다. 기능 변경과 추가했을 때 어댑터 패턴을 사용하여 유지보수가 가능하다. ex) class Target { public virtual void Request() { Console.WriteLine("Target Request Method"); } } class Adaptee { public void SpecificRequest() { Console.WriteLine("Adaptee SpecificRequest Method"); } } class Adapter : Target { private Adaptee m_adaptee = new Adaptee(); public override void Request() { m_adaptee.S..