전체 글
-
스택의 활용 - 스택 계산기 (괄호 제외)C 자료구조/3. 스택( Stack ) 2020. 6. 24. 10:18
아래에서 중위 표기법을 후위 표기법으로 변경하는 방법을 알아봤다. designatedroom87.tistory.com/23?category=868809 스택의 활용 - 중위 표기법에서 후위 표기법으로 변환(괄호 제외) 중위 표기법에서 후위 표기식으로 바꾸는 알고리즘. 1. 중위 표기법 배열을 왼쪽에서 오른쪽으로 탐색. 2. 만약 피 연산자(숫자)를 만나게 되면, 바로 후위 표기 배열에 저장. 3. 연산자를 만나게 designatedroom87.tistory.com 이번에는 이 후위 표기법으로 가지고 계산기를 만들어 보자. 스택에 저장할 테이터의 타입은 float이다. 계산 알고리즘 후위표기법 배열을 왼쪽에서 오른쪽으로 탐색하면서 피 연산자(숫자)이면 스택에 저장. 연산자이면 숫자를 스택에서 꺼내 연산을 ..
-
스택의 활용 - 중위 표기법에서 후위 표기법으로 변환(괄호 제외)C 자료구조/3. 스택( Stack ) 2020. 6. 24. 09:44
중위 표기법에서 후위 표기식으로 바꾸는 알고리즘. 1. 중위 표기법 배열을 왼쪽에서 오른쪽으로 탐색. 2. 만약 피 연산자(숫자)를 만나게 되면, 바로 후위 표기 배열에 저장. 3. 연산자를 만나게 되면, 연산자 우선 순위를 판단하여야 함. 3 - (1). 스택에 존재하는 연산자가 현재 처리중인 연산자보다 우선 순위가 높으면, 일단 스택에 있는 연산자들을 먼저 후위배열에 저장하고 나서 나중에, 현재 처리중인 연산자를 스택에 넣어야 한다. 3 - (2). 만약 우선 순위가 같다면, 일단 스택 상단의 요소를 꺼내 후위배열에 저장하고 나서 현재 처리중인 연산자를 스택에 저장 중위 표기법은 후위 표기법으로 변경하는 함수 메인 함수 프로그램 실행 결과 아래는 소스 파일 아래는 스택 라이브러리를 이용한 중위 표기..
-
Stack의 활용 - 문자열에 들어있는 괄호의 짝 검사C 자료구조/3. 스택( Stack ) 2020. 6. 22. 22:57
프로그램에서는 여러 가지 타입의 괄호들이 같은 타입으로 쌍으로 존재하여야 한다. 프로그램에서는 대괄호, 중괄호, 소괄호 등이 사용된다. 괄호의 검사 조건은 다음의 3가지 이다. 조건 1 : 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. 조건 2 : 같은 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 조건 3 : 서로 다른 타입의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 된다. 에러의 종류를 살펴보자. { A[ ( i + 1 ) ] }
-
Quick SortC 자료구조/Sort Advanced 2020. 6. 22. 17:57
퀵 정렬도 분할 정복 방법에 근거한다. 여기서 정렬방식은 오름차순 기준이다. 퀵 정렬은 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각 각의 부분 리스트를 다시 퀵 정렬하는 전형적인 분할 정복 방법을 사용한다. 그러나, 병합 정렬과는 달리 퀵 정렬은 리스트를 다음과 같은 방법에 의해 비 균등하게 분할한다. 먼저, 리스트 안에 있는 한 요소를 피봇으로 선택한다. 여기서는 리스트의 첫 번째 요소를 피봇으로 하기로 한다. 피봇보다 작은 요소들은 모두 피봇의 왼쪽으로 옮겨지고 피봇보다 큰 요소들은 모두 피봇의 오른쪽으로 옮겨진다. 결과적으로 피봇을 중심으로 왼쪽은 피봇보다 작은 요소들로 구성되고, 오른쪽은 피봇보다 큰 요소들로 구성된다. 이 상태에서 피봇을 제외한 왼쪽 리스트와 오른쪽 리..
-
1. Merge SortC 자료구조/Sort Advanced 2020. 6. 21. 18:11
간단한 도식화 그림을 살펴보자. 위의 도식화 그림을 설명하면 아래와 같다. 위의 그림과 같이 정렬할 배열이 주어졌다고 가정하면, 1. 분할 : 정렬할 배열을 27 10 12 20 과 25 13 15 22의 2개의 부분 배열로 나눈다. 2. 정복 : 부분 배열을 정렬하여 10 12 20 27 과 13 15 22 25를 얻는다. 3. 결합 : 부분 배열을 통합하여 10 12 13 15 20 22 25 27 을 얻는다. 각 각의 부분 배열들을 어떻게 정렬하여야 할까? 정답은 부분 배열들을 정렬할 때도 합병 정렬을 순환적으로 적용하면 된다. 즉, 위의 예에서 부분 배열인 27 10 12 20을 정렬할 때도 합병 정렬의 개념을 다시 적용한다. 이는 합병 정렬 함수의 순환적인 호출을 이용하여 구현하면 된다. 위의 ..
-
4. AVL 트리의 Rebalance 함수C 자료구조/7. Binary Search Tree Advanced - AVLTRee 2020. 6. 19. 23:06
앞에서 균형 인수는 다음과 같이 정의한다고 했다. '균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리 높이' 그리고 트리에서 트리의 높이를 구하는 함수 또한 만들었다. 1. 균형 인수를 구하는 함수 2. 트리의 균형 여부를 판단하고, 트리를 균형 트리로 만드는 함수 그리고, 트리가 비 균형 상태일 때, 균형 상태로 만들어주는 함수를 Rebalance 라 하고 이를 만들어 보자. 우선 트리가 균형 상태 인지 아닌지를 먼저 확인을 한다. 비 균형 상태이면, 균형 상태로 만들면 된다. 앞에서 말했듯이, 균형이 깨지는 경우는 4가지의 경우가 있다고 했다. 각 경우를 파악하고, 각 경우 맞게 회전시키면 된다. 그리고 앞에서, 균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 이유는 노드의 삽입과 삭제 ..
-
3. AVL 트리의 RL회전, LR회전C 자료구조/7. Binary Search Tree Advanced - AVLTRee 2020. 6. 19. 19:03
1. RL회전 RL타입은 조상 노드 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 노드가 추가됨으로해서 발생한다. RL회전은 균형 트리를 만들기 위해서 2번의 회전이 필요하다. LL회전을 한 다음에, RR회전을 하면 된다. 아래 [ 그림 2 ]과 같이 AVL 트리의 노드 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 새로운 노드를 추가하면 비균형 트리가 되고, 이를 바로 잡기 위해서는 LL회전과 RR회전의 2번의 회전이 필요하다. 아래의 그림과 같이 트리가 있다고 하자. [ 그림 1 ] 위의 트리에서 데이터의 삽입이 이루어졌다고 가정하자. 그러면 아래의 그림이 된다. [ 그림 2 ] 위에서 데이터의 삽입이 이루어짐과 동시에 균형 트리를 맞춰야 한다. 먼저, LL회전 시키면, 아래의 그림이 된다. 그리고, RR회..