devonuu/boj-java

BOJ-JAVA

백준 알고리즘 / 프로그래머스 문제풀이 소스 저장소

BOJ > 재귀 ( recursion )

• 하노이 탑 이동 순서
• 압축
• 이진 검색 트리
• 괄호의 값

Num11729

하노이 탑 이동 순서

• 가장 밑에 원판이 목적지에 가려면 그 원판을 제외한 나머지 원판들은 순서대로 목적지가 아닌 다른 곳에 쌓여 있어야 한다
• 재귀는 두가지로 분기 된다.
  1. 가장 밑 (N번째) 원판이 목적지로 가는 재귀
  2. 그 다음번째 원판들( 1~(N-1) )이 목적지로 가는 재귀
• 가장 큰 원판이 움직일 수 있도록 나머지 원판들이 경유지로 비켜주고 가장 큰 원판이 움직인다.
• 포인트는 각 재귀의 깊이 마다 목적지와 경유지가 바뀐다는 사실을 인지하는 것이다.
• 원판의 개수가 짝수인지 홀수인지에 따라서도 처음 움직이는 원판의 위치도 달라진다.

Num1662

압축

• K(Q) 패턴의 반복이기 때문에 재귀를 통해 해당 패턴을 반복할 수 있도록 만들어주면 되지 않을까..?
• K(Q) 패턴을 만드려면 여는 괄호(의 INDEX와 닫는괄호)의 INDEX를 가지고 있어야 범위를 정할 수 있겠다 싶다.
• 재귀는 여는 괄호(를 만났을때 깊어진다. 여는 괄호 다음부터 닫는 괄호가 나올때까지 내부 문자열의 개수만큼 더해주고 괄호가 닫히면 반복문을 종료한 후 괄호안의 문자개수를 return 해준다.
• 한쌍의 괄호 안에 또다른 괄호가 몇개든 상관없이 여는 괄호 다음에 마주치는 닫는 괄호는 무조건 한쌍이기 때문에 괄호 하나 단위로 재귀의 깊이를 더해준다.

Num5639

이진 검색 트리

• 조건

  1. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
  2. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
  3. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

• 전위 순회 = 루트 -> 왼쪽 -> 오른쪽

• 후위 순회 = 왼쪽 -> 오른쪽 -> 루트

• 출력 양식

  1. 전위 순회한 결과를 후위 순회한 결과로 변경한다.

발상
전위 순회한 결과를 바탕으로 트리구조를 만들고 해당내용을 다시 후위 순회로 탐색하면 될듯

1. 전위 순회한 결과를 바탕으로 트리구조를 만든다.

• BTree class 생성
  • field
    1. int value - 값을 저장하는 변수
    2. Btree left - 왼쪽 자식트리 reference
    3. Btree right - 오른쪽 자식트리 reference
  • method
    public BTree createTree (Btree tree, int value)
    1. 트리가 비어있을 경우 새로운 트리를 할당한다.
    2. 현재 레벨의 트리의 값이 파라미터로 전달받은 value보다 작은경우 우측에, 클경우 좌측에 새로운 트리를 만드는 createTree를 재귀적으로 호출한다.
    3. 호출이 완료되어 반환받은 tree를 조건에 맞게 좌우에 할당한다.

2. 해당내용을 다시 후위 순위로 탐색한다.
   1. 좌 -> 우 -> 루트 순으로 순회한다.
   2. 트리의 좌측이 null이 아닐경우 null이 나오는 시점까지 재귀적으로 탐색한다.
   3. 트리의 우측이 null이 아닐경우 null이 나오는 시점까지 재귀적으로 탐색한다.
   4. 좌, 우 노드가 둘다 null인 경우는 단말 노드이기 때문에 현재 레벨의 노드의 값을 StringBuilder에 저장한다.

Num2504

괄호의 값