삼전동해커

이진 트리를 배열을 이용해 먼저 구현해 보자. 위 사진을 보면 0번째 배열은 사용하지 않고 1번에 A, 2번에 B ~ 순서로 저장한다. 이번엔 이진 트리를 연결 리스트를 이용해 구현해보자. 연결 리스트는 위와 같이 왼쪽, 오른쪽으로 구분한다. 선형 구조에서 앞,뒤로 구분한 것과 비슷하다. #include #include typedef int BTData; typedef struct _bTreeNode{ BTData data; struct _bTreeNode * left; struct _bTreeNode * right; }BTreeNode; //노드 생성,노드 초기화 BTreeNode * MakeTreeNode(){ BTreeNode * newNode=(BTreeNode*)malloc(sizeof(BTre..

트리는 스택,큐와 달리 비선형, 계층적 관계를 표현하는 구조이다. 트리는 데이터의 저장,삭제 보다는 표현에 초점을 두고 있다. terminal node : 아래에 다른 노드가 뻗치지 않은 최하위 노드 ex)H,I,J,F,G internal node: terminal node를 제외한 노드 ex)A,B,C,D,E 이진 트리와 서브 트리 이진트리란 1.루트 노드를 중심으로 두개의 서브 트리로 나뉜다. 2.나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다. 이 두 조건을 만족하는 트리이다. 위의 사진은 E가 2번 조건을 만족하지 못하니 이진 트리가 아니다라고 생각 할 수 있지만 사실 저 트리도 이진 트리가 맞다. E의 자식 노드로 J의 형제가 존재할 수 있기 때문에 공(empty) 노드로 남아 있다. 포화 ..

큐가 뒤로 넣고 앞으로 빼는 구조라면 덱은 앞,뒤로 넣고 앞,뒤로 뺄 수 있는 구조이다. 즉 양방향으로 넣고 뺄 수 있다. 그래서 덱이란 double-ended queue라는 의미로 스택과 큐의 특성을 모두 가지고 있다. 덱에서 구현되어야 할건 앞으로 넣기, 뒤로 넣기, 앞으로 빼기, 뒤로 빼기 덱은 이전의 스택, 큐와 달리 양방향 리스트로 구현한다. 앞뒤로 자유롭게 이동하기 위해 next와 prev로 방향을 정할 수 있다. 앞으로 넣기 스택과 비슷하게 head에 데이터를 추가한다. head앞에 새로운 데이터를 추가한 뒤 새로운 데이터를 head로 지정한다. 뒤로 넣기 tail 뒤에 새로운 데이터를 추가한 뒤 새로운 데이터를 tail로 지정한다. 앞으로 빼기 head의 next를 head로 지정한 뒤 원..

출처 : 윤성우의 열혈 자료구조 햄버거 가게에서 손님대기를 위한 큐를 만든다. 1시간 동안 고객이 15초당 1명씩 주문을 한다. 분당 4명*60분 = 240명 버거를 만드는 시간은 치즈버거 12초, 불고기버거15초, 더블버거 24초이다. 큐 넉넉하지 않아도 되고, 꽉 차는 상황이 발생해야 한다. 큐의 크기 30 : 안정적일 확률 50% 큐의 크기 50 : 안정적일 확률 70% 큐의 크기 100 : 안정적일 확률 90% 큐의 크기 200 : 안정적일 확률100% 안정적이라는 의미는 10회 시뮬레이션 결과 대기 고객 전부를 수용하는 것이 불가능한 상황이 몇회 발생했는가 이다. 50%는 10회중 5회 발생 했다는 의미이다. #include #include #include #define CUS_COME_TERM..

원형 큐를 구현했다. 원형 큐는 다음과 같이 f(front),r(rear)이 있는데 F는 시작부분을 나타내고 R은 끝을 나타낸다. 처음엔 f와r이 같은 곳에 위치해 있다. 그리고 데이터가 push되면 그곳에 데이터를 저장하고 r을 다음 칸으로 옮긴다. 데이터를 계속 저장하다 큐가 꽉차게 되면 f와 r은 다시 같은 곳에 위치하게 된다. 하지만 이런 상황은 맨 처음 큐가 비었을 때와 동일하기 때문에 큐가 꽉찬 상태인지 비어 있는 상태인지 구분할 수가 없다. 따라서 맨 처음 f를 비운 상태로 시작해야 한다. 데이터를 push할 땐 r 위치를 다음 칸으로 옮긴 뒤 r에 데이터를 push한다. 이런 식으로 f위치는 비워두고 r위치에 데이터를 push한다. pop을 해야할 땐 f위치를 다음 칸으로 옮겨 pop할 데..