이진탐색트리(Binary Search Tree)

Queue 큐

큐는 스택과 다르게 앞뒤가가 뚫린 긴통이라고 보면 된다. 즉 입구와 출구가 다르다.

뒤에서 넣고 앞에서 꺼낸다. 그래서 먼저 들어간 것이 제일 먼저 나오는 FIFO구조이다.

큐를 조작하는 방법에는 put동작과 get동작이 있다.

put  : 뒤에서 넣음

get  :  앞에서 꺼냄

사진 : 위키백과

큐 구현방법에는 배열구현과 연결리스트 구현이 있다. 

큐노드 클래스

큐 초기화(이중연결 리스트)

Put

K의 값은 가지는 노드를 만들어 꼬리의 앞에 삽입한다. 

Get

큐가 비었는지 확인하고(머리노드 다음이 꼬리이면 꺼낼 노드가 없다)

C++같은 메모리 직접 관리가 가능한 언어는 당연히 메모리를 삭제했으니 메모리해제과정이 필요하다.

출력

확인

맨처음 put한 데이터가 맨 위에있다.

Get테스트

이진트리 구현

순회종류의 맞게 출력결과를 보기 위해 테스트해봤다.

트리는 목적/구성에 따라 맞는 순회방법을 결정해주어야한다.

테스트예제

레벨그림

결과

트리

어떤 요구조건을 만족하는 정점과 선분들의 비어있지 않는 집합

정점은 또한 노드라고도 표현한다.

노드 : 동그라미 하나하나 트리의 요소를 나타냄

루트노드 : 부모노드의 최상단

단말노트 : 자식이 없는 노드

서브트리 : 트리안에 존재하는 트리

트리의 높이 : 가장 최상단부터 레벨을 1,2,3이라 매긴다.

트리의 성질

트리에는 어떤 두 노드를 연결 하는 경로는 한개다. (부모-자식간 양방향의 경로가 있어도 경로는 한개)

어떤 두 노드는 최소 공통 선조를 지님.

루트가 최소공통선조가 되거나 근의 자식들중의 부분트리에 두 노드가 속하게 되므로 최소 공통선조는 항상 존재

각 노드가 최소공통 선조에 이르는 경로를 연결하면 두 노드간 최소 경로가 된다.

이진트리(Binary tree)

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 가지는 트리 구조로,

 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

이진트리 순회방법

목적/구성에 따라 순회하는 방법이 다르다.(기준은 루트노드 기준)

1. 전위순회(Preorder) - 루트 -> 왼쪽서브트리 -> 오른쪽 서브트리

F, B, A, D, C, E, G, I, H (root, left, right)

2. 중위순회(Inorder) - 왼쪽서브트리 -> 루트 -> 오른쪽서브트리

A, B, C, D, E, F, G, H, I (left, root, right)

3. 후위순회(Posterorder) - 왼쪽서브트리 -> 오른쪽서브트리 -> 루트

A, C, E, D, B, H, I, G, F (left, right, root)

Tree구조

naver

트리는 2차원적 비 선형구조이다. 

나무의 모양을 거꾸로 뒤집어 놓은 모양이다. 

뿌리가 가장 위에 있으며 가지(link)들은 밑으로 벌어지며 향한다.

트리구조에서 쓰는 용어

트리의 성질

-나무 구조에서 한 노드에서 다른 노드로 가는 경로는 유일하다.

(나무를 타는 경로가 중복되지않고, 되돌아감이 없다면)

나무구조의 임의의 두 노드는 최소 공통 선조(두 노드가 갖는 가장까운 부모 노드)를 갖는다. 

-N개의 노드를 갖는 나무는 N-1개의 링크를 가진다.

트리구조는 뿌리 노드를 제외하고 모든 노드가 자신의 선조를 향해 하나의 링크를 갖는다.

그래서 N개의 노드를 가진 나무는 N-1개의 링크를 가진다

-꽉 찬 이진트리는 레벨이 d라고 할때 노드의 수는 N이 다음과 같은 조건을 만족한다.

병합정렬(merge sort)

병합의 개념 : 두개 이상의 정렬된 자료집합을 하나의 정렬된 자료집합으로 합치는 것

병합의 방법 : 대상 자료집합이 정렬된 상태이므로 순차적으로 작은 자료를 뽑아서 놓으면됨

데이터의 분포에 영향을 덜 받는다.

즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)

실제로 숫자들이 정렬되는 과정

거품 정렬

배열의 인접 요소를 비교하여 교환하는 모양이 보글보글하다고 해서 붙여진 이름이다.

거품 정렬은 인접한 배열의 요소를 비교 교환하여 전체적으로는

대충 정렬을 하면서 최대값을 배열의 제일 뒤로 보내는 것을 반복한다.

거품 정렬의 개선

아래 함수를 추가하여 정렬이 되어있는 체크

정렬이 되어 있다면 바로 빠져 나오도록

(but 정렬이 되어있을때는 시간이 적지만 그렇지 않을 경우는 더 시간이 느려진다.

s=0과 if s인지 판단하는 문장이 추가 됐기 때문)

재귀호출

자기자신을 호출한다.

재귀적으로 문제를 해결함은 또 문제를 점점 더 작은 단위로 쪼개어 해결함을 의미한다.

잘못된 재귀 호출

문제 해결에 변화없는 호출

무한루프 -> 시스템 내부의 스택에 복귀주소와 인자를 저장해야 하기 때문에

스택에는 자료가 쌓인다.

재귀 호출의 요건

1. 거듭제곱을 구하는 재귀 함수

N의 거듭 제곱은 N!이라고 표현한다.

ex) 4를 넣었을때

4 x(3 x(2 x(1 ))) = 24

//0! 되면 재귀함수 탈출

2. 피보나치 수열 구하는 재귀 함수

한 함수 내에서 한번만 이루어져야 하는 것은 아니다.

한 함수 내에서 두 번 혹은 그 이상도 자기자신을 호출할 수 있다.

3. 하노이의탑

세 개의 기둥과 서로 다른 크기의 N개의 원반으로 구성된다. 이 원반들은 세 개의 기둥 중의 하나에 반드시 꽂혀 있어야하며, 자신보다 작은 원반 위에는 그 원반을 놓을 수 없다.

즉 원반은 아래에 가장 큰 것이 와야하며, 자신보다 큰 원반은 자기 위에 놓을 수 없다.

N이 3일때

1. 기둥 1의 원반을 기둥 3으로 옮긴다

2. 기둥 1의 원반을 기둥 2로 옮긴다.

3. 기둥 3의 원반을 기둥 2로 옮긴다.

4. 기둥 1의 원반을 기둥 3으로 옮긴다.

5. 기둥 2의 원반을 기둥 1로 옮긴다.

6. 기둥 2의 원반을 기둥 3으로 옮긴다.

7. 기둥 1의 원반을 기둥 3으로 옮긴다.

재귀적 표현

1. 기둥 1에서 N-1개의 원반을 기둥 2로 옮긴다.

2. 기둥 1에서 1개의 원반을 기둥 3으로 옮긴다.

3. 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다.

<결과>

문제

int형 배열과 정수 k를 입력받는데, 배열 요소에 정수 k를 더 했을 경우 k를 더하지 않은 요소들과 비교해가장 큰 수가 될 경우를 카운팅해서 출력하는 문제이다. 

예를 들어 2,3,5,2 배열이 주어지고 정수 3이 주어지면 첫 번째 요소( 2 )에 정수k인 3을 더하면 5가 되는데 나머지 요소와 비교했을 때 가장 큰 수가 아니기 때문에 카운트하지 않게 된다.

이렇게 차레대로 비교를 하면 되는데 요소 3일 경우와 5일 경우는 정수 k를 더했을 때 요소중 가장 큰 수가 되기 때문에 출력 결과는 2를 출력하면 된다.

조건 : 요소 비교 중 값이 같을 경우는 가장 큰수가 될 수 없다.

풀이

처음 생각하기에는 처음 요소를 다른 요소와 비교하면서 가장 크다고 판단되면 카운트해서 그 카운트가 배열의 길이에서 1을 뺀 수와 같으면(자기 자신을 제외한 다른 요소들의 개수) 가장 크다고 판단하여 그 개수를 출력하려고 했지만.. 

위에 경우 처럼 배열의 길이에서 1을 뺀 값을 나를 제외한 나머지 요소들의 개수라고 판단해버리면 배열 요소 중 자신과 같은 값을 갖고 있는 요소가 있게 되면 요소에 k를 더한 후 비교할 때 동점인 경우는 체크하지 않기 때문에 카운트 값이 맞지 않는다.

반대로 생각해보면  k를 더한 요소보다 더하지 않은 요소중에 더 큰 경우가 있다면? 더 비교할 필요도 없이 그 요소는 배열의 요소중 가장 큰 요소라고 할 수 없다. 

if(i!=j && vote[j] >= max) : 자기 자신과의 비교는 제외하고, 배열의 요소중 더 큰 값이 있다면 break 키워드로 반복문을 빠져나온다.

if(cnt ==0 ) : cnt가 0인 경우가 자기 자신이 가장 큰 경우(k를 더했을 때)이기 때문에 cnt가 '0'인 요소일 때 resscent를 증가시키고 최종적으로 반환한다.

cnt를 bool 플래그로 쓴 것이다.

arcde46