// Codepad 에서 sin() 을 인식못함... 그래서 실행은 안 걸어둠

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INPUT_FILE_NAME		"input.txt"

#include <stdio.h>
#include <string.h>

#define MAX_STRING_LENGTH		100
#define MAX_MATCH_STRING_LENGTH	20

#include <stdio.h>

#define MAX_STRING_LENGTH		100
#define MAX_MATCH_STRING_LENGTH		20

class Rule
  attr_reader :rule_name, :lhs_list, :rhs
  
  def initialize(rule_name, lhs_list, rhs_str)
    @rule_name = rule_name

/*
	HW 1 - Problem 7
	
	Merge Sorting(non-recursive)
	

=begin
Context-Free Grammar - Sentences Generator
=end

class ContextFreeGrammar

class String
  def digit_sum
    match_data_arr = self.scan(/[0-9]/)

    return 0 if !match_data_arr

class BinaryTreeNode
  attr_accessor :left_child, :right_child, :parent, :data

  def initialize(data)
    @left_child = @right_child = @parent = nil

def compare_items_element(item1, item2, elem_idx)  
  ch_item1 = item1[elem_idx]
  ch_item2 = item2[elem_idx]

  if !ch_item1 && !ch_item2

def compare_items_element(item1, item2, elem_idx)  
  ch_item1 = item1[elem_idx]
  ch_item2 = item2[elem_idx]

  if !ch_item1 && !ch_item2

#define MAX_VALUE 10
#define MAX_STACK_SIZE 10

class MazeStack 
{ 

=begin
분리 집합(DisjointSet) 을 구현한다

=end

=begin
수식 트리 만들고 계산하기
후위 수식을 받아서 트리를 만들고 계산한다
중위 수식을 후위 수식으로 변경하는 것은 생략

=begin
N-Queen Problem

=end

=begin
Backtracking 을 이용하여 미로 탈출

=end

=begin
Divide & Conquer 를 이용하여 n 번째 피보나치 수열의 수를 구하기

http://dev.heartsavior.net/288
=end

=begin
Divide & Conquer 를 이용하여 거듭제곱 구하기

http://dev.heartsavior.net/287
=end

=begin
Divide & Conquer 를 이용하여 n 번째 피보나치 수열의 수를 구하기

우리에게 많이 알려진 재귀함수로 피보나치를 구하면 피보나치 재귀에서 엄청난 중복이 생긴다.
피보나치 수열을 아래와 같이 행렬식으로 변환하면 n번의 제곱으로 수를 구할 수 있다.

=begin
거듭제곱 의 점화식

  c^n = c^(n/2) * c^(n/2), n is even
        c^((n-1)/2) * c^((n-1)/2) * c, n is odd

=begin
거듭제곱 의 점화식

  c^n = c^(n/2) * c^(n/2), n is even
        c^((n-1)/2) * c^((n-1)/2) * c, n is odd

# :title: Modified Title
# \:title: Modified Title -> Set Page title to 'Modified Title'
#
# :main: lib/test_rdoc_3.rb
# \:main: lib/test_rdoc_3.rb -> Set start page to 'lib/test_rdoc_3.rb' 's RDoc document page

# :title: Modified Title
# \:title: Modified Title -> Set Page title to 'Modified Title'
#
# :main: lib/test_rdoc_3.rb
# \:main: lib/test_rdoc_3.rb -> Set start page to 'lib/test_rdoc_3.rb' 's RDoc document page

class TestRDoc2
  def fred
    line = 'Line'
    address = 'Address'

#_class_ <b>comment</b> +test+
#  Indenting...
#woowang, \+good\+ method_1
#--
#Normal Comment, so it does not include to rdoc

# C/C++ 로 배우는 자료구조론 연습문제 7.33

class CircularQueue

  def initialize(size)

# C/C++ 로 배우는 자료구조론 연습문제 7.32

class CircularQueue

  def initialize(size)

# C/C++ 로 배우는 자료구조론 연습문제 7.25

class CircularQueue

  def initialize(size)

# C/C++ 로 배우는 자료구조론 연습문제 7.24

class CircularQueue

  def initialize(size)

# C/C++ 로 배우는 자료구조론 연습문제 6.34

class DropOutStack

  def initialize(size)

# C/C++ 로 배우는 자료구조론 연습문제 6.29

class DualStack

  def initialize(size)

# C/C++ 로 배우는 자료구조론 연습문제 6.28

class Stack

  def initialize(size)

# C/C++ 로 배우는 자료구조론 연습문제 4.28

def func(num, n)
  puts num * n
  func(num, n * 2) if num * n < 3600

# C/C++ 로 배우는 자료구조론 연습문제 4.25

def ackermann(n, m)
  if 0 == n
    return m + 1

# C/C++로 배우는 자료구조론 연습문제 4.19

def gcd(num1, num2)
  return -1 if num1 < num2

# C/C++로 배우는 자료구조론 연습문제 4.18

def binary_search(array, left, right, find_num)
  return -1 if left > right
  

# C/C++로 배우는 자료구조론 연습문제 4.17

def get_sum(num_arr, size)
  return 0 if size == 0

# C/C++로 배우는 자료구조론 연습문제 4.15

def PrintDecimalReverse(n)
  if n == 0
    puts

# C/C++로 배우는 자료구조론 연습문제 4.11

def print1toN(n)
  print1toN(n-1) if n > 1
  print n

# C/C++로 배우는 자료구조론 연습문제 4.14

def WriteBackward(str_array, array_size)
  return if array_size < 1