기억보단 기록을

다른게 어려운게 아니라, 트리를 구성후 leaf node에서 순서쌍을 통해 명제식을 검사하는데

순열알고리즘이 들어간다. (자료구조수업인데 ㅠ)

재귀함수를 통해 leafnode까지 내려간후, leafnode에는 true 혹은 false를 담게 된다.

이는 switch 문의 default값을 통해 처리하게되는데, testcase는 알파벳순으로 a,b,c... 입력되는 값에 맞추어

node->data - 'a'를 통해 인덱스값을 확인하게된다. (a는 0번인덱스, b는 1번인덱스 ... 이런식)

이렇게 값을 정해주고 root까지 거슬러 올라가며 이 순서쌍은 참인지 정하게 된다.

그렇다면 모든 순서쌍을 어떻게 구할까.

순열을 통해 모든 순서쌍을 구해준다.

물론 이진수개념인 비트마스크를 통해 구할수 있을것 같기도 하다.

앞서 inorder preorder postorder 방식은 다루었었다.

이번에는 스택에서 다룬 postfix expression을 한번 트리로 구현해보자.

input: AB/C*D*E+

원리는 먼저  연산자가 나올때까지 operand를 스택에 넣고, 연산자가 나온다면 pop해서 오른쪽자식, 왼쪽자식에 하나씩 넣어준다. 그러면 그 부모노드가 또 스택에 들어가 다음번 연산자의 자식으로 되기때문에 inorder traversal을 통해 infix notation을 얻을수 있다.

추가로 구현한 leverOrder traversal

트리는 구조체로써 leftchild와 rightchild를 가짐

트리의 모양을 유지하며 노드를 추가하기 위해선, 큐를 사용해야 한다.

먼저 들어오는 모든 노드에 대해 큐에 넣고, 큐의 front에 있는 노드의 왼쪽자식과 오른쪽자식이둘다모두 존재할때 비로소 ,delete 큐를 해준다. 그렇게 되면 자연스럽게큐의 front는 항상 부모노드가 되며, 이 부모노드의 자식이 모두있을경우 다음노드로 이동하게 된다.

트리의 순회방식

inorder :  왼쪽 방문 오른쪽

preorder :  방문 왼쪽 오른쪽

postorder : 왼쪽 오른쪽 방문

leverorder : 트리노드의 순서대로순회 (다음장에서 다룸)

이번에 해볼 문제는 러시안룰렛 게임이라고 부르는 요셉의문제이다.

총 게임에 임하는 인원수와 건너뛸 점프숫자를 입력받아 마지막 생존자가 나올때까지 인원을 줄여나가는 프로그램이다.

원형연결리스트(CIrcular Linked List)로 구현해보았다.

데이터가 많아지면 그룹 관리의 필요성 ---> 자료의 열거형 표현

- 배열 : 하나의 변수에 여러정보를 담기 가능, 반복문등과 결합해 처리 용이, 인덱스를 가지며

               따라서 자료의 빠른 조회가 가능하다. 자료의 접근에 시간복잡도 O(1)이다.

- 리스트 : 배열은 크기가 고정적이며, 값의 수정이 번거롭다.(수정시 수정인덱스 이후의 값의 인덱스를 조정해야함)

                위의 한계를 해결하는것이 연결리스트(Linked List). 값을 동적으로 생성된 노드에 저장해 자료들간의 연결관 계  구성.  공간적제                  약을 덜 받고 자료의 수정삭제가 쉽다. 하지만 자료의 접근성에있어 시간복잡도 O(N)을 띄게 된다.

연결리스트의 각노드에는 data값과 다음 노드의 주소를 가지게 된다.

head부분은 데이터가 있어도되고 없어도되며 없을경우가 코드를 구성하기 더 쉽다.

이경우 head는 어떤 기능도 하지않는 더미노드(dummy node)가 된다.

아래코드와 함께 살펴보자

먼저 연결리스트의 정의부분이다.

listNode라는 것을 구조체로 선언하는데 위에보면 listNode 형의 포인터인 listPointer가 선언된다.

이렇게 포인터변수를 하나 선언해놓으면 프로그램작성이 조금더 간단해진다고 할 수 있다.

struct listNode *= listPointer 이다.

먼저 프로그램은 임의의 수들을 파일입력으로 넣는데, 이를 오름차순정렬인 리스트로 만드는 프로그램이다.

find는 리스트 노드가 한개 들어갈때마다 들어갈 위치를 정해준다. 여기선 계속해서 link(=next)로 넘어가다가

자신보다 높은 값을 가진 노드를 만나면 그 앞에 넣으면 된다. 반환은 넣을위치 이전노드를 반환해야 insert가 쉽게

가능. 처음에는 first가 비었기때문에 NULL을반환.

더미노드를 만들지 않아, 상당히 까다로워졌다.

first가 맨첫 노드인데, 맨 첫노드를 넣을때 x가 null 이면 first가 첫노드로 생성, 또 x가 first라면 first다음에 노드를

넣어주기 위해 경우의수 하나를또 생성한다. 그 이후엔 반복문을 통해 할 수 있다.

delete를 통해 50이하의 항목들은 모두 지워보았다.

delete작업또한 first가 첫번째 항목이므로 이또한 예외처리를 해주었다.

물론 다른방식으로도 작성할 수있다. 이방식으로 하면 delete함수의 else함수가 쓸모없게된다.

더미노드 방식으로 하면 훨씬 간단해진다.

이전에 했던 많은 경우의수가 사라지고, 그냥 first다음부터 차례대로 넣어주면 된다.

우리가 알고있는 식, 즉 (A+B)*C 와같은 식들은 Infix notation, 즉 중위표기법이라 부른다.

후위표기식은 위의 식을 AB+C* 와 같이 표현한다. 

후위표기식으로 바꾸는 법은 모든 항에 괄호를 씌우고 큰괄호부터 지워나가며 연산자를 그의 오른쪽 괄호와 바꿔주면 된다.

ex) ((A+B)*C) --> (A+B)C* --> AB+C*

왜 이런식이 존재할까.

후위표기식은 계산을 할때 괄호가 없어도 계산 순서가 일정하여 중위표기법 계산보다 후위표기법이 빠르다.

계산기나 컴퓨터 내부에서도 스택을 활용하여 중위표기법을 후위표기법으로 변환하여 연산한다.

아래는 컴퓨터 내부의 후위표기식을 중위표기식으로 계산하는 원리이다.

typedef enum 이라는 열거형 자료형으로 멋들어지게(?) 표현해놓았다.

간단히 말해 피연산자(즉,숫자)는 스택에 들어가게되며, 연산자의 경우 앞선 두개의 숫자를 POP 하여 계산을 하면된다.

이번에는 중위표현식을 입력받아 후위표기식으로 바꾸는 프로그램을 만들어보자.

중위 표기식에는 후위표기식과 다르게 우선순위라는것이 존재한다.

가령 4*2+3 이란 식이 들어왔을때

operand 라면 바로 출력하고, operator 라면 스택에 넣는데

4출력 ->2출력 ->3출력

스택 : * +

이렇게 하면 423*+ 가 된다. 따라서 이식의 결과는 4+2*3이다. 처음 들어온 식과 다르다.

결론적으로 스택에 우선순위가 더 높은 operator 가 있다면 pop해서 출력해야한다.

또 lparen, 즉 개괄호의 경우 우선순위가 스택안(isp)에서와 밖(icp)에서가 다른데, 개괄호는 스택에 들어올때는 우선순위를 가장 높게 만들어 무조건 스택에 들어갈수있게하고, 스택안에서는 오히려 우선순위를 낮게해 폐괄호가 나오기 전까지는 스택에서 나가지 못하게해 다시말해 괄호연산자의 우선순위를 보장하는 것이다.