알고리즘 용어

1. In-place algorithm (인플레이스 알고리즘)

인플레이스 알고리즘(In-place) input을 어떤 보조의 데이터구조 사용없이 변경이되는 알고리즘을 말한다.
하지만, 작은 용량의 여분의 공간은 보조의 공간을 허용하는 편이다.
한마디로,  알고리즘을 위해서 메모리공간의 사용을 최대한 적게 사용하는 것이 목적이다.


아래의 wiki의 예제를 보면 input 배열을 reverse 두개의 함수가 존재한다.

  https://en.wikipedia.org/wiki/In-place_algorithm

• reverse function 

1. reverse는 Array이 즉, 메모리에 동일하게 할당한다
2. Time complexity O(n) = T(n) = n

• reverse_in_place function 

1. 기존의 Array에서 swap하면서 변경을 한다.
2. Time complexity O((n-1)/2) = T((n-1)/2) = n


상위 두함수를 비교를 해보면,

reverse 함수는 array를 reverse하기 위해, 동일하게 memory를 할당하여 두배를 사용한다.
reverse_in_place 의 경우는 input의 array를 이용하고, swap을 위한 변수만을 이용하여 이를 memory의 최소사용을 한다.


이 알고리즘과 반대되는 알고리즘은 not-in-place or out-of-place 라고 한다.


2. Divide and Conquer algorithm (분할 정복)

이 알고리즘의 목표는 복잡한 문제를 지속적으로 작은 문제로 분할을 하면서 해결하면서 해결을 하려고 하는 것이다.
이 복잡한 문제에서 분할(Divide)을 진행하면서 작은문제로 변경을 하고 이를 정복(Conquer), 즉 해결해 나가는 방식이다.

결론적으로 보면 top-down 방식으로 문제를 해결해 나간다고 생각하면 되겠다.

예를 들어보자면 Quick sort 인경우 data중에서 pivot 선택하여 기준을 정하고 item들을 pivot과 비교하여 위치변경한다
이것이 작은문제로 선정한것이다. 그리고, 매번 pivot정하고, 정렬할 범위를 정하고 위작업을 반복한다.

  https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
  https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm


3. 재귀 (Recursion)

자료구조와 알고리즘에서 흔히 많이 사용되는 방식이며 이는 많은 장점과 단점을 포함하고 있다.

• 기본동작방식 

Function 안에 Input을 변경하여 자신을 재호출하고,
Return 값을 받아 계산하여, 적용을 한다.


3.1 일반 재귀의 장점

흔히들 O(n) 같은 것을 O(1)으로 변경이 가능하다.
(한 함수내에서 보면 그렇지만 전체적으로 보면 O(n) 반복문인것은 동일하다)

함수의 내부 Stack를 기본적으로 이용하기에 Stack의 특성가진 LIFO Programming 쉽게 이용 가능하다.
상위 Divide and conquer algorithm에 적용이 쉽게 가능하며,
Dynamic programming에서 보면, 이는 Top-down 접근이나, Bottom-Up 접근이 용이하다.

3.2 일반 재귀의 단점 

함수의 내부 Stack를 이용하기때문에 사용량이 증가하면 Stack의 overflow는 발생 가능성이 높고,
성능이 저하되며, 속도역시 떨어질것이다.
그리고, 위에서 언급했듯이 지속적으로 공간이 두배식 확장되며서 Memory 문제도 발생한다.

  https://en.wikipedia.org/wiki/Recursion       
  https://ko.wikipedia.org/wiki/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98

• 공간문제 (Space complexity)

Function 안에서 자신을 재 호출하고 그 Return값을 기다리기 때문에 ,예를 들면,
1st function , 2nd function , 3rd function 호출 된다고 하자.
1st는 2nd을 Return을 , 2nd는 3rd의 Return을 기다려야 하기 때문에
함수의 사용공간 및 함수 내부 Stack 은 지속적으로 확장이 된다.
 

3.3 꼬리재귀 (Tail Call or Tail Recursion)

• 일반재귀의 특성 

위에서 설명한 재귀의 기본특성을 가지고 있지만, 재귀와 꼬리재귀의 차이는 무엇일까?

일반적으로, 함수를 호출을 하면 위에서 설명했듯이 함수를 호출하기 위해 call stack 이 존재한다.
그리고, 함수가 호출 되고 종료가 되면, CPU는 이 주소를 보고 원래 호출 장소로 상태로 되 돌아간다.
이를 call stack이라고 한다. Function, 함수들을 위한 stack인 것이다.


기본 Process 구조 or Program의 구조는 아래와 같이 구성이 된다.

1. CODE 영역
2. DATA 영역
3. STACK 영역
4. HEAP  영역

그리고, DATA 영역에는 초기화된 전역변수(bss)와 비초기화된 전역변수 존재하며,
STACK 영역에는 함수의 argument와 내부변수 및 위의 call stack이 저장이 된다.

HEAP 아시다시피 malloc 으로 잡힌 영역으로 말하지만,좀 더 깊이 들어가면 이부분도 복잡해진다.
(이부분은  추후 시간이 된다면 설명하겠다)

*참고사항

link script 에서 개별영역의 특성을 살펴볼수 있다.
본인이 좀더 깊게 공부하기를 원한다면, ARM용 ABI (aplication binary interface)를 한번 보기를  권한다.

  https://sourceware.org/binutils/docs/ld/Scripts.html#Scripts

• 꼬리재귀의 특성 

일반 재귀는 이 STACK 영역을 이용을하며, stack 관련 programming도 쉽게 가능하다.
일반재귀와는 다르게 꼬리재귀는 이 call stack이 매번저장할 필요가 없다고 한다.

1. 사실 내부적으로 어떻게 저장하고 어떻게  동작하는지 너무 궁금했다.
2. 왜 opimization 필요한가 ? 

원문)
For tail calls, there is no need to remember the place we are calling from – instead, we can perform tail call elimination by leaving the stack alone (except possibly for function arguments and local variables[3]) and the newly called function will return its result directly to the original caller.

간단히 해석하자면, 꼬리재귀는 call stack 필요는 없지만, 대신에  stack을 남기면서 꼬리재귀제거(tail call elimination) 수행을을 한다고한다. 이 stack에는 함수의 argument와 local variable을 제외되었다고 한다. 그리고, 내부에서 새롭게 호출되어지 함수는 결과 값을 돌려주는데, 이 것은 원래의 함수에 집적에 돌려준다고 한다.

이는 일반재귀와 동작방식이 근복적으로 다르며, 무작정 메모리공간을 두배식확장해가는 것이 아니라,
Tail call elimination을 위해 별도의 메모리 구성하며 호출하는 것이다.
이는 memory 절약뿐만 아니라, 속도에도 크게 향상을 보일 것이다.

아래의 사이트 해석대로라면, 일반재귀처럼 꼬리재귀는 막복사하여 만들어내지는않는 것 같다.

  https://en.wikipedia.org/wiki/Tail_call     ( Description 보면 자세한 설명)

• 사용예제 사이트 

본인은 간단히 함수 구현만 했으며,  TEST를 일일이 못했지만, 아래에 사이트들에서
너무자세히 잘해주었기에 그냥 TEST를 하지 않기로 하였다.

  http://yumere.tistory.com/69
  http://bozeury.tistory.com/96
  http://hanmomhanda.github.io/2015/07/27/%EC%9E%AC%EA%B7%80-%EB%B0%98%EB%B3%B5-Tail-Recursion/

• 관련 구현 

4. 알고리즘의 성능측정 

알고리즘의 성능측정을 객관적으로 표시하기 위해서 Big-O, Little-O, Theta, Omega, 기타 같은 방법이 존재하지만,
가장 많이 사용되는 것은 Big-O이며, 이 기준으로

우선 Time complexity가 성능의 우선순위에서 측정하기도 쉽고, 알기도 쉽다.

이를 먼저생각 한 후 그 후 Space complexity를 두 번째 조건으로 측정하는 것 같다. 

물론 Memory에 따라 변경이 될수 있겠지만, 대체적으로 그렇게 되는 것 같다. 

• Time complexity ( 시간의 복잡도)

이전에도 설명했듯이 Big O notation 기반으로 대부분 Worst Case 기반으로 측정을한다.

O notation 과 Time complexity에 관련 내용을 보면 쉽게 이해를 할 수 있다. 

• Space complexity (공간 복잡도)

Algorithm에서 Time complexity 이외에도 Space complexity도 존재하지만,
정확한 Memory의 사용량을 측정하기는 힘들다.
가장 간단한방법은 process의 전체 memory 사용량을 아는 것이겠지만,
이는 정확하지도 않고, 분석하기도 그렇다.
정확한 공간 복잡도는 별도의 Debugging Tool이 필요하며, 그나마,

공간복잡도를 쉽게 계산가능 한것은 함수 호출 횟수를 계산 할때의 Memory 증가성이다.
일반 재귀인 경우 Time complexity를 Space complexity로 변경이 가능하며
이를 time-space-tradeoff 말하는 것 같다.

  https://en.wikipedia.org/wiki/DSPACE 
  http://www.leda-tutorial.org/en/official/ch02s02s03.html

Data structure 기본 및 Algorithms (알고리듬) 기본 이해

1. 전체 학습관련내용

최근 다시 Data structure와 Algorithm을 학습하기 위해 찾은 Site가 아래의 사이트이며,
책은 현재 C로 구현한 알고리즘 및 기타 책으로 보고 다시 확인을 하고 있다.
기본적으로 한글 번역서는 영어 용어와 가끔 혼동이 있어,
이를 가끔적 영어를 사용하려하고 표기하려고 한다.


  정말 아래의 사이트 진심으로 감사 할뿐이다.
  https://www.tutorialspoint.com/data_structures_algorithms/index.htm


2. Data Structure 의 기본 학습 

한글로 하면, 데이타의 구조이며, Data 구조의 특성을 나타내는 것인 것 같다.
간단하게는 int, float, char 부터 C언어의 array가 될 수도 있고,
복잡하게 들어간다고 하며, C언어에서는 structure문으로 구성하여 data를 저장하고
간단한 저장방식을 제공하는 연산이 필요한 Linked List , Set ,Stack, Queue가 이에 포함되겠다.

Data Structure 기반으로 어떻게 구현 어떻게 효율적으로 동작하게 하는 것이 알고리즘이 되겠다.

2.1 Data Structure 관련 용어

• interface  

각 data structure 는 interface를 가지고 있으며 data structure 지원하는 동작들이라고 표현하겠다.
interface는 오직 지원되는 동작 기능중 지원하며, interface가 사용가능한 parameter 받고 return을 해준다.

예를 들면, LIFO, FIFO, Single Linked List , Double Linked list interface가 아닐까 싶다.

• Implementation

한글로 하면 구현이며, 이는 data structure를 대표해주는 것이며, 알고리즘에게 data structure 동작을 제공을 해준다.

예를들면, Data structure의 구현된 전체 구조를 말하며, Linked List,  Set , Stack, Queue 같은 구현물이 아닐까 싶다.


2.2 Data Structure의 특성

• Correctness 

한글로 하면 정확성이며, Data structure Implementation은 그 그것의 interface로 정확하게 구현해야만 한다.
Linked List나 Set , Stack은 보면 알수 있겠지만, 당연한 말 같다.

• Time Complexity

실행시간 중 data structure 의 operation 사용시간을 말하며, 작을 수록 좋다.

• Space Complexity

실행시간중, data structure의 operation 사용 중인 memory 말하며, 작을 수록 좋다.
             
  https://www.tutorialspoint.com/data_structures_algorithms/data_structure_overview.htm


2.3  Data Structure 의 기본 

Data structure의 Data Type은 두가지로 구분이 되며,

• Built-in Data Type (기본적 Data Type)

    Compiler에서 제공해주는 기본 integer, string, charter , Boolean 이 되겠다.

• Derived Data Type (파생된 Data Type)

1. List    : Linked List를 말하는 것 같다. 
2. Array  : Built-in Data or Structure의 단순 Array 방식 
3. Stack  : Array or Linked List
4. Queue: Array or Linked List 
5. Graph : Graph도 내부적으로 보면, Set or Matrix로 표현이 가능한데, 
6. Set :    Linked List로 구현 가능 
7. Tree:   Binary Tree or Tree는 Set으로 구현 가능 

• Basic Operation 설명 

처음 Traversing와 Searching을 혼동을하였으며, 둘이 비슷한 기능인 줄 알았다.
아래와 같이 Tree기준으로 보면 간단히 설명을 하면, 아래와 같은 Operation들이 존재하며,
구지 Tree가 아니라도, 기본적인 Operation들은 거의 유사하다.

1. Traversing : 순회, Tree에서 자주사용이 되며 Tree를 전체 순회를 하는것이다.   
2. Searching : 찾기, Tree에서 자주사용이 되며, 비교하여 하나를 선택하여 찾는방식 
3. Insertion: 삽입, Item을 삽입하는 방식 
4. Deletion: 삭제 , Item을 삭제하는 방식 
5. Sorting : 정렬,  Item들을 대소를 비교하여 정렬을 한다.  
6. Merging: 합치기, Tree에서 자주 볼수 있지만, Set에서도 볼수 있다. 

 사실 위 Operation 때문에, Algorithm 과 Data Structure의 구분이 약간 모호 한 것 같다.
 Tree or Graph 는 Data structure 이고, 기본 Operation을 제공을 하며 움직인다.
 여기까지는 Data structure이지만, 최소신장 Tree 처럼 Tree를 이용하여 다시 새로운
 Operation을 하는 것이 이런 부분이 알고리즘으로 구분이 되는 것 같다.

  https://www.tutorialspoint.com/data_structures_algorithms/data_structures_basics.htm
  https://www.tutorialspoint.com/data_structures_algorithms/array_data_structure.htm

3. Algorithms analysis 알고리즘 기본분석

이 사이트에서 책보다 새롭게 Data structure와 Algorithm의 구분이 명확하게되었다.
일단 Algorithm은 Data structure 기반으로 구성이 되어있으며, 이 관점에서 본다면,
아래의 다섯가지로 나누어진다.

알고리즘은 Data structure 기반으로 움직이는 방식으로 보면되겠다.
물론 이 방식이 여러 방식이 존재 하겠지만, 이에 따라 알고리즘역시 변경이 되겠고,
동일한 Data structure를 가지고, 다른 알고리즘을 사용하여 비교 할수도 있겠고,
Data structure를 변경하여 , 동일한 알고리즘을 사용해도 되겠다.
그러기에 알고리즘(Algorithms)은 자료구조(Data Structure) 와 분리 하기는 어렵겠다.

왜냐하면, 알고리즘의 목표는 성능인데, 자료구조 역시 성능에 영향을 미치기 때문이다.

기본적으로 알고리즘의 성능분석은
Time Complexity의 거의 촛점이 맞추어져 있으며,
더불어 측정을 한다면, Space Complexity도 이용하여 알고리즘의 성능분석하자.

3.1 Asymptotic Analysis (접근식 분석방법) 

Data structure와 Algorithm를 분석할때 , 매번 같은 분석이 나올 수가 없을 경우가 많다.
이럴 경우, 아래와 같이 나누어서 살펴보자.

1. Best Case       : 거의사용되지 않는다고 한다. 
2. Average Case  : 평균의 상황 , 이는 측정이 어렵고, 정확하지가 않다. 
3. Worst Case     : 최악의 상황  

이 분석에서 가장 중요한 것은 Worst Case이다.
대부분의 알고리즘이 Worst Case에 근사하게 움직이며 동작하기이라고 한다.

그리고, Average Case도 사용이 되지만 측정이 어렵고, 정확하지가 않다.
하지만, 예외사항 같이 확률적으로 적용할 경우, 이야기는 좀 달라진다.
Quick Sort 같이 정확한 확률적으로 계산적용을 한다면,  Average Case가 중요하다.
그래도, Worst Case를 절대 간과해서는 안된다.

내 개인적인 생각으로는 통계치 기반으로 된 데이타기반으로 된 경우에는
Best Case 인 경우는 알고리즘을 적용하고 한다면 아주 중요하게 될 것 같다.
이것은 내 개인적인 생각이다.


이를 표시하는 방법도 다양하지만, 거의 Big O Notation을 사용한다.
다른 것은 생략하며 아래 사이트를 참고하자.

  https://www.tutorialspoint.com/data_structures_algorithms/algorithms_basics.htm
  https://www.tutorialspoint.com/data_structures_algorithms/asymptotic_analysis.htm


4. WEB 에서 기본 TEST 환경

현재 내가 가장 익숙한 언어는 C 언어이며, Java와 여러 언어를 경험을 했지만,
그래도 C가 가장 익숙하고 편한다.

만약 현재 Build 환경이 구축이 되지 않았다면, 아래의 사이트에서 Compile 및 결과를 확인가능하다.
아래사이트는 Memory 사용량을 계산을 해주기때문에, 너무 감사하다.

  http://ideone.com/

C언어의 연산자 설명 (Bit 관련설명)

1. C의 연산자 관련 설명 (Bit 중심 )

C언어에서 Bit 관련 연산자는 주로 아래의 6개로 구성이 된다.

•  비트 관련 연산자  

1. <<          : 1 bit left Shift 
2. >>          : 1 bit right Shit 
3. |             :  OR 
4. &            :  AND 
5. ~            :  NOT 
6. ^            :  Exclusive OR  (둘 다 다르면 1이고, 동일하면 0)

AND , OR , NOT 연산자는 잘 알겠지만, XOR 매번 헷갈린다. 

그래서 아래와 같이 적어놓는다. 

XOR truth table

Input		Output
A	B
0	0	0
0	1	1
1	0	1
1	1	0

  https://en.wikipedia.org/wiki/Exclusive_or

• 논리 연산자 

1. && :  logical-AND
2. ||    :  logical-OR 

논리연산자는 if 문 이나 while 문  비교하는 곳에 사용이 되며,
연산자의 우선순위가 낮기 때문에 아래와 같이 두개의 비교가 끝난 후,
결과 값이  (a > 0) => 1 ,  ( b < 0) => 1  일 경우 이 값을 기준으로 논리적으로 AND OR 연산을 한다.

if ( a> 0 && b <0 a="" nbsp="" while=""> 0 || b < 0) 


2. C 언어의 BIT 연산자 활용

아래와 같이 매크로로 선언하여, 간단히 정의해서 사용할 수 있다.

#define BSET(n)        (1<<(n))

#define BUNSET(n)     ~(1<<(n))

/* set n-th bit in x */
#define B_SET(x, n)      ((x) |= (1<<(n)))

/* unset n-th bit in x */
#define B_UNSET(x, n)    ((x) &= ~(1<<(n)))

/* set n-th bit in x */
#define B_ALLSET(x, n)      ((x) |= (n))

/* unset n-th bit in x */
#define B_ALLUNSET(x, n)    ((x) &= ~(n))


/* test if n-th bit in x is set */
//#define B_IS_SET(x, n)   (((x) & (1<<(n)))?1:0)
#define B_IS_SET(x, n)   ((x) & (1<<(n)))

/* toggle n-th bit in x */
#define B_TOGGLE(x, n)   ((x) ^= (1<<(n)))

혹은 mask로 이용하여 and 연산으로  if 문 안에 넣어 사용한다.

mask = 0x1FFF; // 0 bit ~ 28bit 만 check 하고 싶을 경우

if (  n & mask )