뻔뻔한블로그

트리 알고리즘을 공부하다 보니까 

공부한것을 이용해 보고싶다는 생각이 들었다.

그래서 유니티로 트리구조를 가시적으로 보이도록 구현해봤다.

이진트리와 AVL 트리를 구현했다.

둘다 기본적인 구조는 이진트리이다.

삽입된 노드는 root노드부터 비교하면서 자신의 값보다 현재

위치한 노드가 크면 왼쪽 삽입된 노드가 크면 오른쪽으로 이동한다. 

바이너리(이진)트리

 AVL 트리

트리의 균형도가 절대 값1이 넘어 갈 경우 자동으로 균형 회전을 하도록 구현했다.

콘솔로만 구현하기는 인터넷에도 많고 구현도 잘되어 있다.  트리구조에 따라 UI오브젝트도 움직이는 이려면 추가적으로 자료구조 구현이 필요하다.

사실 실제 데이터가 움직이는 트리구조와 이미지박스가 움직이는 것은 아예 상관이 없이 움직인다고 생각하면 된다. 별도로 움직여야 한다.

내가 구현한 코드에 노드는 Key는 int비교를 하기 위한 변수로 사용하고

Value는 오브젝트를 움직이기 위한 변수를 같이 담고 있다. (키 값을 통해 오브젝트를 불러오기 위함)

먼저 오브젝트의 위치를 움직여주고 그 다음에  트리구조에 데이터 구조를 변경하도록 한다.

그래프 알고리즘

그래프는 정점과 간섭의 집합이다.

정점 :  일반적으로 이름을 가지는 원으로 표시 ( 0 ,1 ,2, 3...)

간섭 : 두 정점간을 연결하는 선으로 표현 (0과1을 이어주는 선,1과 4를 이어주는 선...)

정점의 위치는 의미가 없고, 정점간의 연결 상태만이 중요하다.

경로 : 정점x로부터 정점y에 이르는 간선으로 연결된 정점들의 순서 집합이다.

단순경로 : 처음 정점 외에 중복된 정점이 없는 경우를 의미( 그래프 G1에서 정점 A에서 정점 C까지의 경로 중 (A-B-C)는 단순 경로이고 A-B-D-A-B-C는 단순 경로가 아니다)

회로(cycle) :  첫 정점과 끝 정점이 같은 경우 (G1에서 A-B-C-D-A)

신장 나무 : 어떤 그래프의 부분 그래프로서 정점의 집합V는 원래의 그래프와 같은 나무 구조를 말한다. 즉 회로(cycle)가 없는 그래프

나무구조는 정점이 v개일 경우 간선은 v-1개 정점개수가 v라면 트리구조일 수 가 없다 => 회로가 존재

무향 그래프 : 간선의 방향성이 없는 그래프

방향 그래프 : 간선의 방향성이 있는 그래프

가중 그래프 : 간선의 방향성과 가중치까지 표현한 그래프

네트워크 : 가중 그래프이면서 방향 그래프 인것

정점에 이어진 간선의 수로 차수를 결정한다. 무향 그래프일 경우 단순하게 차수라 할 수 있지만 방향이 있는 방향 그래프인 경우는 나가는 선과 들어오는 선을 구분 할 필요가 있다.

외차수 : 정점으로 부터 나가는 간선의 수 ( 정점 V1에 e2,e3)

내차수 : 정점으로 들어오는 간선의 수 (정점 V1에 e1,e5)

학습 참고

1) c로배우는 알고리즘 

2) https://ko.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

3) https://m.blog.naver.com/PostView.nhn?blogId=k97b1114&logNo=140163248655&proxyReferer=https%3A%2F%2Fwww.google.com%2F

알고리즘을 공부하던중 재미있는 알고리즘을 발견해서 공부해보았다.

그것은 허프만 알고리즘.

허프만 알고리즘 Huffman

사용하는 빈도수의 따라 bit를 할당

자주쓰이는 문자에 가장 작은 bit를 할당

예를들어

HAN HA

이라는 문자열을 받으면

가장 많이 사용된 ‘H’에 0이라는 1bit를 부여하고

A에게 10, N에는 11을 할당한다.

(0)(10)(11) (0)(10)

당연히 중복된 문자가 많기 때문에 용량이 클수록 압축률은 올라간다.

코드부분

FileStream 부분

.txt 파일을 읽어 드리는 FileStream부분이다.

Header h = Compressor.Compress(bytes); 압축과정을 거친 후

h.Write(bf); 출력

압축과정

딕셔너리에 추가하면서 문자중복이라면 nVal(빈도수 )을 증가 시킨다.

노드를 만들어주는 과정 노드 빈도수의 합을 가지고 트리구조를 만듬

코드할당 부분 (01010) 왼쪽은 '0' 오른쪽 '1'

출력 코드 부분은 생략

보헤미안 랩소리 노래 앞부분을 txt파일에 넣음

빈도 수

사실 노래앞부분만 넣었을 경우 내용이 짧기 때문 압축이 되지 않았다. 

같은 문자를 여러번 복사해야 헤더가 물고있는? 문자들이 많이지기 때문에 압축률이 올라간다.

문제

'@'문자 이후에 문자들을 출력하는 문제이다.

처음 '@'나온 이후부터 구조체에 넣어서 출력하면 될 줄 알았는데

위 테스트 문제처럼 '@'가 여러개인 경우도 있다.

풀이 : 내가 작성한 코드

for문을 통해 '@'문자가 나온 후 그 이후에 문자들을 문자열 s에 넣는다.

그런 뒤 한번더 '@'문자가 나올 경우를 체크하고 만약 '@'가 또 나온다면 s 문자열을 비우고

다시 '@'이후 문자 들을 담는다.

풀이 : 다른 사람 코드

게임개발에는 사용하기 힘들지만 강력한 기능 LinQ.

Split('@').Last()로 한번에 구할 수가 있었다.

문제

bishop이 pawn을 대각선으로만 이동해서 잡을수 있다.

잡을 수 있으면 true / 못 잡으면 false

풀이 : 내가 작성한 코드

(bishop[0] + bishop[1]) % 2 == (pawn[0] + pawn[1]) % 2 :

문자열의 알파벳과 숫자의 합이 짝수 이거나 홀수로 두 문자열이 같아야한다.(홀이거나 짝수)

bishop[0] != pawn[0] : 문자 앞 알파벳이 같으면 대각선이 아니므로 체크

풀이 : 다른 사람이 작성한 코드

알파벳끼리 빼고 숫자끼리 뺀값은 결국 대각선으로 증감되는 값이 나온다. 

ex )

(a1,b2) : (a-b)==(1-2)

(a1,c3) : (a-c)==(1-3)

....

문제

문자열을 받고 그 문자열에 연속된 숫자를 출력하는 문제이다. 

처음 문자가 비었다면 return : Empty

풀이 : 내가 작성한 코드

if(inputString.Length==0) : 문자열이 없을 때 비어있는 문자열 리턴

if(char.IsDigit(val) : 숫자인지 체크하고 숫자가 아닐 경우 break로 반복문 빠져나온다.

ss += val : 숫자일경우 문자열을 완성시킨다. 

풀이 : 다른 사람 코드

if( c.Equal("  ") || !Char.IsNumber(c))  : 첫문자열이 비어있거나, 숫자가 아니면 return

문제

'abcdc'를 뒤집어도 똑같은 문자열이 나오는 최소조건을 만드는 문제이다.

최소조건이란 최대한 적은 문자를 사용하라는 말이다.

풀이

처음에 문자열을 맨앞과 맨뒤를 비교하면서 같으면 넘어가고 다를 경우 기존 문자열에 추가하면 될거라고

생각했지만 하나의 문자열의 같은 문자가 반복되는 경우가 있기 때문에 정답이 될 수 없었다. 

다른 자료구조가 필요했다.

int pos : 문자열의 역순으로 들어갈 인덱스번호(pos번째까지)

int Length = st.Length;  :  문자열의 길이

예로 'abcdc'를 입력한다고 하자

if(st[iif (st[i] != st[j]) : 

{

 i = ++pos;
 j = Length - 1;

}

문자열의 맨앞과 맨뒤를 비교해서

다를 경우 맨앞의 문자열의 인덱스( pos증가 )를 한 칸 이동한다.

계속 해서 i를 증가시켜 맨 뒤 문자와 비교하다가 같은 문자가 나오면

맨 뒤를 가리키는 인덱스도 앞으로 이동해준다.

앞 뒤 문자가 같다는 말은 뒤집었을때 최소조건이 될 수도 있다는 말이다.

여기서 for문 조건을 통해 i가 h를 넘었다면 반복문을 종료한다.

하지만 종료조건이 아니라면 계속해서 내가 처음 생각했던 구조처럼

같은 문자가 반복되는 경우가 있기 때문에 계속 비교를 이어나가면 된다.

입력받은 문자열에 앞에서 부터 pos번째까지가 뒤집었을때 최소조건을 충족하는 문자들이 된다.

AVL나무

왼쪽 작은 나무의 높이와 오른쪽 작은 나무의 높이가 같거나 하나 차이나는 나무를 말한다.

AVL나무의 각 노드는 균형도라는 수치를 가지고 있는데 이는 왼쪽 작은 나무의 높이에 오른쪽 작은 나무의 높이를 뺀 값을 의미하며, 이 값의 절대 값이 클수록 나무 모양이 불균형하다는 뜻이 된다.

결국 AVL트리는 이진 검색트리이면서 동시에 균형을 유지하고 있는데, 균형이란 왼쪽과 오른쪽 높이의 차이가 1이하인 상태이다. (-1, 0 ,1)

이런 균형적인 구조를 지켜야 검색 시의 효율성을 보장할 수 있기 때문이다.

위에서 설명한대로 

[균형도 = 왼쪽노드 레벨 - 오른쪽 노드 레벨]

식으로 계산하여 균형도는 절대값이 0과 1사이에 이어야 한다.

두 번째 그림처럼 균형이 무너진 유형중 하나인 LL구조이다.

AVL 불균형 구조는 회전방향과 회전 횟수에 따라 4가지로 구분된다.

1. LL : 균형도가 2인 경우

2. RR : 균형도가 -2인 경우

LL반대로 코드는 생략

3. RL :

4. LR

문제

정수 k에 따라 배열에 연속된 요소들의 합이 가장 큰 값을 출력하는 문제이다.

예를 들어 배열 [2,3,5,1,6] 일 때 k가 2일 경우 3+5=8 이 가장 크다. 

풀이 : 내가 작성한 코드

for(int i=0; i<inputArray.Length-k+1; i++) :

배열의 길이 - k +1인 이유는 아래 sum에 K만큼 연속된 요소를 더하기 위함이다. 

for(int j=i; j<k+i; j++) :

k+j로 요소길이 만큼 범위를 변경해준다,

풀이 : 다른 사람 코드

for(var i=0; i< k; ++i) : 처음 0부터 k번째까지의 요소의 합

Math.Max(maxSum, currentSum) 0이상 수중 큰 수를 리턴(if문을 안 씀)

for(var i=k; i <inputArray.Lenght; ++i) : k만큼의 요소를 더하는데 

배열 [2, 4, 10, 1] k가 2일 때 

currentSum += inputArray[i] - inputArray[i-k]; :

inputArray[0] + inputArray[1] += inputArray[2] - inputArray[0] 

= inputArray[1] + inputArray[2]

 6 += 8   = 14 (두 번째 k길이 만큼의 요소합)

이렇게 이미 currentSum에서 전에 더한 요소가 있기 때문에 그것을 제외한 다음요소만

더해서 다음 k번째 길이만큼의 요소의 합을 구해준다.

내가 작성한 코드보다 연산횟수가 적다.

배열의 길이가 4, k가 2일 때 

내가 작성한 코드보다 for문을 5번더 적게 돈다.

이분검색

이미 정렬된 배열에 대해서 검색하는 알고리즘이다. 순차 검색과 달리 자료를 정렬이라는 방법으로 조직한다. 그래서 검색은 간단하지만 자료를 삽입하거나 삭제할 때는 자료의 구조를 깨뜨리지 않아야 하는 어려움이 있다.

이분검색방법

1. 자료의 집합은 크기순으로 정렬되어 있어야한다.

2. 이미 정렬된 자료 집합에 대해 이분 검색법은 자료의 중간값을 우선 검사한다. 이 자료의 중간값이 찾는 키값이 아니라면 중간값과 키값의 크기를 비교하여 왼쪽 구간이나 오른쪽 구간을 선택한다.

3. 그리고 그 구간에 대해서 똑같은 방법으로 중간값과 키값의 크기를 비교한다.

검색

[탐색 방법]

① 구간의 중간값을 구한다.

② if(중간값 < 키값) 오른쪽 구간또는 왼쪽 구간을 선택한다.

삽입

[삽입 방법]

① key가 들어갈 위치를 찾는다.

② 삽입할 공간을 만든다

③ 공간에 자료를 삽입하고 자료수를 증가시킨다.

삭제방법은

순차검색알고리즘 삭제방법과 동일

이분 검색은 삽입과 삭제의 어려움 때문에 삽입과 삭제가 적은 거의 고정적인 자료집합에 유리하다.

검색알고리즘

검색이란?

특정한 구조로 구성되어 있는 자료의 집합에서 주어진 키에 해당하는 레코드를 찾아내는 것

단순히 자료를 찾는 것에만 국한되는 것이 아니라 자료가 새로 추가되고 삭제될 때 어떻게 이 자료들의 특정한 구조를 계속 유지하느냐하는 문제도 포함되어있다.

순차검색(선형검색)

주어진 자료 파일에서 처음부터 검색키에 해당하는 레코드를 순차적으로 비교하여 찾는 가장 단순한 검색 방법

장점 : 데이터를 따로 조작할 필요가 없어 단순

단점 : 리스트의 길이가 길면 비효율

시간의 복잡도 : O(n)

1. 별다르게 조직화가 필요없다.

2. N개의 자료에 대해서 평균적으로 N/2번의 비교를 해야한다.

검색

[검색 방법]

① 첫 번째 원소부터 시작하여 마지막 원소까지 순서대로 키 값이 일치하는 원소가 있는지를 비교하여 찾는다.

② 키 값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지를 반환한다.

③ 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없으면 찾은 원소가 없는 것이므로 검색 실패

개선 :검색한 키를 선두로 옮기는 과정

삭제

[삭제 방법]

① 삭제하려는 키가 어디에 있는지 탐색한다.

② 찾으려는 키가 나올때 까지 한칸씩 당기고 배열의 자료수를 하나 감소 시킨다

삽입

[삽입 방법]

① 배열의 인덱스를 하나 증가하고 배열의 제일 뒤에 key를 덧 붙인다.

② 그런 뒤 삽입위치를 리턴

문제

문자열을 받으면 몇 종류의 문자(char)가 있는지 체크하는 문제이다.

풀이 : 내가 작성한 코드

첫 번째 요소를 리스트에 넣고 두 번째 요소부터 리스트자료 집합에 있는 문자인지

체크하도록 했다. 함수와, 리스트를 새로 만들었고 문자를 계속 비교하는 과정이 효율적이지 않은 것 같다.

풀이 : 다른 사람 풀이

int 배열을 생성하고 두번 째 for문에서 비교가 끝난 문자에는 '1'을 넣어

중복 비교를 하지 않게 만들면서 중복요소를 체크한다.

문제

문자열 중 요소중 가장 인덱스가 가장 빠른 숫자를 리턴해야 하는 문제

풀이 : 내가 작성한 코드

내가 작성한 코드는 int.TryParse 숫자로 변환이 가능하면 true를 리턴하는 함수를 사용하여

숫자를 구분했다. ToString( )도 사용하고 사용하지 않는 int result로 선언하기도 해서 

그닥 좋아보이지 않다.

풀이 : 높은 순위에 있는 코드

char.IsDigit 10진수인지 판별하는 함수를 사용하여 숫자를 찾고있다.

몰랐던 함수였다.

퀵정렬

빠른속도와 간단 원리

연속적인 분할에 의해서 정렬한다.

축값을 중심으로 왼쪽은 이 축값보다 작은 값으로 오른쪽은 모두 이 축값보다 큰 값으로 배열시키는 것이다.

이 과정을 분할의 크기가 1이 될 때까지 반복하면 전체적으로는 정렬이 완료된다.

퀵 정렬의 전략

<퀵 정렬 알고리즘 (a, N)>

1.만약 n > 1이면

1.1 N의 크기의 a 배열을 분할하여 축값의 위치를 mid로 넘긴다.

1.2 퀵 정렬 알고리즘(a,mid)

1.3 퀵 정렬 알고리즘(a+mid+1,N-mid-1)

왼쪽구간 부터 우선적으로 분할을 하고, 그 다음에 오른쪽 부분에 대해서 분할을 시작한다.

쉘 정렬 처럼 멀리 떨어져 있는 요소끼리 교환을 하기 때문에 빨리 정렬된 상태로 변화된다.

난수나, 반쯤 정렬된 배열에 대해서는 빠른 속도를 보이지만 이미 정렬된 배열이나 역순 배열에 대해서는 성능이 매우 떨어진다.
(빠른 알고리즘이란 최대한 적은 비교와 교환이다. 퀵정렬은 피벗에 모두 순차적으로 비교하게 되므로)

퀵소트 비재귀 버전

쉘정렬

삽입정렬은  정렬된 배열에 대해서는 매우 뛰어난 성능을 보이지만 그렇지 않은 경우에는 속도가 매우 느리다

ex) 역순 배열의 경우 제일 작은 키값이 제일 뒤에 있으므로 N번의 비교와 이동을 해야한다.

이 문제를 해결하기 위해 h만큼의 간격으로 떨어진 레코드를 삽입하는 정렬

4중 루프가 된 것을 제외하고는 삽입 정렬과 비슷하다.

쉘 정렬의 개선

h = (h-1)/3은 풀어쓰면 h = h/3 -1/3이 되며 1/3으로 취급하기 때문에 h = h/3

<결과>

쉘정렬은 O(NlogN)을 가지는 알고리즘들에 비해서는 속도면에서는 약간 떨어지지만 10,00이하의 자료 정도라면 쉘 정렬이 오히려 더 빠를 수가 있다.

O(NlogN)을 가지는 다른 알고리즘처럼 추가적인 메모리가 필요 하지 않는다.

학습참고 : C로배우는 알고리즘

삽입정렬

많은 비교와 적은 교환으로 특징인 선택 정렬과 반대로 적은 비교와 많은 교환이 이루어지는게 특징이다.

삽입 정렬의 전략

이미 정렬이 된 부분에 새로운 키를 적절한 장소에 삽입하는 동작을 반복적으로 하는 정렬 방법이다.

[루프안에 a[i]보다 t를 쓰는것이 더 빠르다(단순히 t의 값만 읽어 오기 때문)]

삽입정렬은 안정성이 있는데, 항상 그런것은 아니다. (>=t 경우)

이미 정렬된 배열일 경우 매우 빠른 속도를 가진다.

이미 정렬된 경우에는 삽입 정렬의 실행 시간은 N에 비례하는 선형적인 특성을 가진다.

둘째로 삽입 정렬은 역순의 경우 최악의 경우가 된다. 이동과 비교의 횟수는 N*(N-1)/2가 되어서 선택 정렬보다 속도가 떨어진다.

삽입 정렬의 최적화

a[0]값에 -1을 집어넣고 실제 값들은 이후의 저장하도록 하자

그러면 while문에 루프의 판단문에서 j>0과 같은 비교문을 하나 없앨 수 있다.

이런 방법을 사용하게 되면 정렬의 실행시간이 약간 단축되고 N이 클 경우 더 단축

(키값의 최소값을 정하지 못하는 경우가 있기 때문에 신중히 사용해야한다.)

간접정렬

교환이 많은 삽입정렬이기에 간접정렬이 고려된다.

레코드의 배열은 전혀 손대지 않고 따로 만든 인덱스의 배열을 조작하는 방법

비교는 실제 배열a이 하지만 while루프 내의 교환 작업은 index배열을 사용한다.

a에는 아무 변화가 없지만 index배열에는 정렬된 순서가 저장되어 있다.

제일 첫 번째 레코드가 무엇인지 알려면 a[index[0]]와 같이 접근 하면 알 수 있다.

실제로 a 배열을 정렬 하려면 아래와 같은 함수가 필요할 것이다.

학습참고 : C로배우는 알고리즘

정렬알고리즘

정렬이란 임의의 순서대로 배열되어 있는 자료의 집합을 일정한 순서대로 재배열하는 것을 의미

정렬의 방법론

= > 판단과 교환을 어떻게 적절히 조합하는가에 대한 방법론.

정렬을 하는 대상을 파일이라고 하며, 이 파일은 정보의 단위인 레코드의 나열이다.

아래 정보를 가지고 있는 인사기록 카드를 정렬하려고 했을 경우 카드 각 한장은 레코드, 레코드의 정보를 가지고 있는 사번, 성별,나이 등은 필드라고 한다.

정렬을 하려면 키가 있어야한다. ‘비교’의 대상이 되는 것은 레코드 중에서 키값이며, ‘교환’의 대상이 되는 것은 레코드 자체가 된다. 사원번호 정도가 ‘키’가 될 수 있겠다.

선택 정렬(Selection Sort)

순서대로 정렬하는 가장 간단한 정렬 알고리즘.

선택 정렬 알고리즘

선택정렬 특징:

첫 번째  배열의 앞 부분부터 정렬을 차례로 해나간다.

두 번째 정렬을 아직 하지 않은 부분은 n의 변함이 없다.

선택 정렬의 비교 횟수는 최소값을 찾기 위해서 N2/ 2 정도로 많지만 교환 횟수는 많아야 N번이다.

안정성 문제

안정성이란 같은 키의 상대적 순서가 정렬 후에도 변함이 없음을 뜻한다.

하지만 선택 정렬은 안정성이 없다.

인접한 배열 요소를 교환하는 것이 아닌 뚝 떨어진 요소와도 교환이 되기 때문이다.

문제

a 배열의 요소를 X로 생각하고 모든 요소들에 차를 절대값으로 만든 뒤 그 뺀 값을 더한 값중

가장 작은 값을 가지는 배열의 요소를 출력하는 문제이다.

(값이 같다면 가장 배열의 요소중 가장 작은 값을 출력) 

풀이 : 내가 작성한 코드

코드만 봐도 대충 어떤 문제인지 알 수 있다. 

각 모든 요소를 비교해서 'sum'이 가장 작은 배열의 요소를 출력한다.

코드 시그널은 문제를 해결하면 다른 사람들이 푼 답을 볼 수가 있는데 

밑에는 가장 작은 글자수로 문제를 해결 한 사람의 풀이다...

풀이 : 다른 사람이 작성한 코드

이게 어떻게 가능하지 생가했는데 정확히 원하는 값을 가지는 제일 작은 요소를 출력한다.

포문2개나 쓴 내 코드는....;;

같은 문제를 가지고 이렇게도 생각을 할 수 있구나 라고 생각이 들었다.

문제

가리키는 셀의 색상이 같으면 true를 리턴해주는 문제이다.

a1,a3,a5,a7 ...
b2,b4,b6,b8 ...
c1,c3,c5,c7 ...

위 셀들은 같은 색상(진한색)이다.

풀이

a1,a3,a5,a7 ...
b2,b4,b6,b8 ...
c1,c3,c5,c7 ...

(진한색)

a2,a4,a6,a8 ...
b1,b3,b5,b7 ...
c2,c4,c6,c8 ...

(옅은색)

보면 문자의 알파벳 다음인 숫자는 일정한 규칙으로 증가한다.

고로 색상이 같다는 것은 비교하려는 2개의 문자가 10진수로 변환하여 짝수인지

체크해주면 된다.

문제

true 조건

1. 알파벳 a~z(A~Z)과 특수문자 '_', 숫자가 포함되어야한다.

2. 문자열 처음은 숫자가 오면 안된다.

풀이

if((int.TryParse(name[0].Tostring( ), out int a))) : 문자열 첫번째 문자가 int형인지 아닌지 체크한다 2번조건

for, if문 : 모든 문자를 비교하여 true 조건 체크

테스트

04.01