알고리즘
-
이진 검색 트리 출력 함수 구현프로그래밍 기초/알고리즘 2021. 9. 21. 13:55
이진 검색 트리 출력 이진 검색 트리를 화면에 출력하는 함수를 구현한다. 노드 출력 알고리즘 노드를 동일한 간격으로 출력하기 위해 다음의 제약 사항이 존재해야 한다. 모든 노드는 동일한 크기를 갖는다. 최대 깊이의 노드 간의 간격은 노드의 크기와 같다. 최대 깊이에 빈 노드가 없다고 가정하여 최대 크기를 구한다. 구한 최대 크기를 모든 깊이에 사용하여 출력한다. 깊이가 n 일 때, 노드의 개수 및 공백의 개수는 다음과 같다. 노드의 수 2ⁿ - ¹ 개 공백의 수 n + 1 개 따라서 최대 깊이에서 출력에 필요한 크기는 다음의 식을 만족한다. 출력에 필요한 크기 = (공백의 수 + 노드의 수) * 노드의 크기 ※ 깊이에 따라 노드의 수가 달라지므로 공백의 크기는 출력에 필요한 크기 - (노드의 수 * 노드..
-
AVL 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 9. 20. 17:45
AVL 트리 이진 검색 트리를 기반으로 노드에 Balance Factor(이후 BF)를 추가하여 BF의 상태에 따라 트리의 균형을 유지한다. ※ AVL 트리는 노드의 수가 n일 때 최대 깊이가 Ο(logn)이 되게 된다. AVL 트리의 개념 기본적으로 삽입과 삭제는 이진 검색 트리의 알고리즘을 그대로 따르며 이후 BF에 따라 보정하는 작업을 진행하여 트리의 균형을 유지한다. BF는 노드의 왼쪽 서브 트리의 깊이와 오른쪽 서브 트리의 깊이의 차이이다. 정상 상태일 때 BF의 범위는 [-1, 1]이 되게 되며 노드의 삽입 혹은 삭제를 통해 이 범위를 넘게 되면 균형이 무너진 것으로 판단한다. AVL 트리의 회전 알고리즘 BF가 무너진 노드를 x, x의 자식을 c, c의 자식을 c²라 하면 회전이 필요한 경우..
-
레드 블랙 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 9. 19. 17:03
레드 블랙 트리 이진 검색 트리를 기반으로 노드에 색상을 추가하여 색상 규칙을 기준으로 트리의 균형을 유지한다. ※ 레드 블랙 트리는 노드의 수가 n일 때 최대 깊이가 Ο(logn)이 되게 된다. 레드 블랙 트리의 삽입 알고리즘 레드 블랙 트리의 삽입에서는 먼저 삽입하는 노드의 색상을 레드로 간주하고 삽입을 진행하며 삽입한 노드를 x, 부모 노드를 p, 형제 노드를 s라고 할 때 발생 가능한 모든 경우는 다음과 같다. p가 블랙인 경우 삽입 연산을 종료한다. s가 레드인 경우 p와 s를 블랙으로 바꾸고 p²을 레드로 바꾼다. 만약 p²가 루트면 p²를 블랙으로 바꾸고 종료한다. 연산 결과 p²이 레드이면 p²을 문제 발생 노드로 두고 재귀적으로 처리한다. s가 블랙인 경우 삽입된 위치에 따른 추가 연산을..
-
알고리즘...55일지 2021. 9. 15. 01:46
노드를 연결하는 막대 그리기 이전 계산을 통해 노드 사이의 간격을 알고 있으므로 막대는 다음과 같이 그릴 수 있다. 막대의 경우 현 노드가 왼쪽 자식인지, 오른쪽 자식인지에 따라 처리가 달라지게 된다. 먼저 왼쪽 자식의 처리는 다음과 같이 진행한다. 노드와 동일한 공백 입력 노드의 크기의 절반 만큼 공백 추가 오른쪽 아래 막대 추가 노드의 크기의 절반 만큼 가로 막대 추가 공백의 절반 - 1 만큼 가로 막대 추가 위로 향하는 막대 추가 오른쪽 자식의 처리는 다음과 같이 진행한다. 위로 향하는 막대 추가 공백의 절반 - 1 만큼 가로 막대 추가 노드의 크기의 절반 만큼 가로 막대 추가 왼쪽 아래 막대 추가 노드의 크기의 절반 만큼 공백 추가 BinarySearchTree.h /// /// 연결 자료구조를 ..
-
알고리즘...54일지 2021. 9. 14. 18:57
노드를 그려야 하는 크기를 정한 뒤 노드를 배치하는 방법 노드가 서로 동일한 간격으로 떨어져 있기만 하면 깔끔하게 정리가 가능할 것이라는 생각이 들었다. 아이디어는 다음과 같다. 다음과 같은 이진 검색 트리가 있다고 하자. 이에 대해 깊이 별 노드의 최대 개수는 다음과 같다. 깊이가 1인 경우 = 2^0 = 1 개 깊이가 2인 경우 = 2^1 = 2 개 깊이가 3인 경우 = 2^2 = 4개 일반화 하면 깊이가 n 일때 노드의 최대 개수는 2ⁿ - ¹ 개가 된다. 가장 하단의 노드 사이 간격을 노드의 크기와 동일하게 한다고 가정했을 때 필요한 공백의 개수는 노드의 개수 + 1이 되므로 필요한 넓이는 다음과 같다. 공백의 개수 + 노드의 개수 * 노드의 크기 이를 이용해 노드를 출력하는 코드를 작성한다. B..
-
알고리즘...53일지 2021. 9. 13. 01:28
노드의 크기에 따른 공백 확인 먼저 노드의 크기가 1인 경우와 2인 경우에 대해 중간 정렬을 하지 않는다고 가정하고 적절한 공백으로 그림을 그려보자면 다음과 같게 그릴 수 있다. 다만 이렇게 할 경우 왼쪽 공백과 중간 노드와 노드 사이의 공백에 대해서 따로 계산을 해 줘야 하는 문제가 생긴다. 그런데 그렇다고 한 쪽에만 공백을 추가하는 경우에는 깊이가 커짐에 따라 심각하게 모양이 무너지게 된다. 최대한 문제를 단순화하기 위해 막대의 모양은 생각하지 않고 노드의 좌, 우에 동일한 공백을 넣는다고 가정하고 다시 생각해 봐야 할 필요가 있다.
-
알고리즘...52일지 2021. 9. 10. 15:54
노드의 크기에 따른 출력 함수 제작 노드의 크기가 주어지고 데이터가 주어질 때 가운데 정렬이 된 상태의 스트링을 반환하는 함수를 만든다. 가령 노드의 크기가 5이고 노드의 값이 1이라고 하면 가운데 정렬을 위한 공백의 개수는 다음과 같다. 공백의 개수 = (노드의 크기 - 노드의 값의 길이) / 2 이때, 나눠지는 값이 홀수 인 경우 글자를 오른쪽에 치우쳐서 출력하기 위해 우측 공백을 추가로 준다고 하면, 왼쪽과 오른 른쪽 공백은 다음과 같이 구할 수 있다. 왼쪽 공백의 개수 = 공백의 개수 오른쪽 공백의 개수 = 공백의 개수 + (노드의 크기 - 노드의 값의 길이) % 2 정확한 공백을 확인하기 위해 ' ' 대신 '_'를 사용해 구현해 보면 다음과 같다. BinarySearchTree.h /// ///..
-
알고리즘...51일지 2021. 9. 9. 17:01
이진 검색 트리 출력 함수 제작 함수가 복잡해 지고 있으니 다시 기본으로 돌아와서 생각을 해보자. 기본 적으로 깊이가 1인 경우엔 하나의 노드만 출력하고 종료한다. 깊이가 2가 된 경우 깊이가 2인 경우엔 각 노드를 출력하고 노드를 공백으로 구분한다. (노드의 크기가 일정하게 존재해야 하며 숫자는 가운데 정렬이 될 수 있어야 한다.) 깊이가 3이 된 경우 중간의 길이는 더 길어지고 왼쪽 공백은 일정하게 증가한다. (가장 왼쪽 노드의 깊이별 공백은 (최대 깊이 - 현재 깊이) * 노드의 크기 만큼 존재해야 한다.) 노드가 비어있는 경우엔 노드의 길이 만큼 공백을 삽입해야 한다. 노드와 노드 사이의 공백은 (최대 깊이 - 현재 깊이) * 노드 * 2 + 1 만큼 존재해야 한다.