분류 전체보기
-
알고리즘...55일지 2021. 9. 15. 01:46
노드를 연결하는 막대 그리기 이전 계산을 통해 노드 사이의 간격을 알고 있으므로 막대는 다음과 같이 그릴 수 있다. 막대의 경우 현 노드가 왼쪽 자식인지, 오른쪽 자식인지에 따라 처리가 달라지게 된다. 먼저 왼쪽 자식의 처리는 다음과 같이 진행한다. 노드와 동일한 공백 입력 노드의 크기의 절반 만큼 공백 추가 오른쪽 아래 막대 추가 노드의 크기의 절반 만큼 가로 막대 추가 공백의 절반 - 1 만큼 가로 막대 추가 위로 향하는 막대 추가 오른쪽 자식의 처리는 다음과 같이 진행한다. 위로 향하는 막대 추가 공백의 절반 - 1 만큼 가로 막대 추가 노드의 크기의 절반 만큼 가로 막대 추가 왼쪽 아래 막대 추가 노드의 크기의 절반 만큼 공백 추가 BinarySearchTree.h /// /// 연결 자료구조를 ..
-
JUNGOL...137일지 2021. 9. 14. 22:02
Intermediate_Coder/자료구조/색종이(고) 문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 도화지에서 검은색 직사각형을 잘라내려고 한다. 직사각형 또한 그 변이 도화지의 변과 평행하도록 잘라내어야 한다. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 과 같은 모양으로 붙였다. 에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 22×5=110이 된다. 반면 에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 8×15=120이 된다. 검은색 색종이의 수와 각 색종이를 붙..
-
알고리즘...54일지 2021. 9. 14. 18:57
노드를 그려야 하는 크기를 정한 뒤 노드를 배치하는 방법 노드가 서로 동일한 간격으로 떨어져 있기만 하면 깔끔하게 정리가 가능할 것이라는 생각이 들었다. 아이디어는 다음과 같다. 다음과 같은 이진 검색 트리가 있다고 하자. 이에 대해 깊이 별 노드의 최대 개수는 다음과 같다. 깊이가 1인 경우 = 2^0 = 1 개 깊이가 2인 경우 = 2^1 = 2 개 깊이가 3인 경우 = 2^2 = 4개 일반화 하면 깊이가 n 일때 노드의 최대 개수는 2ⁿ - ¹ 개가 된다. 가장 하단의 노드 사이 간격을 노드의 크기와 동일하게 한다고 가정했을 때 필요한 공백의 개수는 노드의 개수 + 1이 되므로 필요한 넓이는 다음과 같다. 공백의 개수 + 노드의 개수 * 노드의 크기 이를 이용해 노드를 출력하는 코드를 작성한다. B..
-
JUNGOL...136일지 2021. 9. 13. 01:44
Intermediate_Coder/자료구조/색종이(고) 문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 도화지에서 검은색 직사각형을 잘라내려고 한다. 직사각형 또한 그 변이 도화지의 변과 평행하도록 잘라내어야 한다. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 과 같은 모양으로 붙였다. 에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 22×5=110이 된다. 반면 에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 8×15=120이 된다. 검은색 색종이의 수와 각 색종이를 붙..
-
알고리즘...53일지 2021. 9. 13. 01:28
노드의 크기에 따른 공백 확인 먼저 노드의 크기가 1인 경우와 2인 경우에 대해 중간 정렬을 하지 않는다고 가정하고 적절한 공백으로 그림을 그려보자면 다음과 같게 그릴 수 있다. 다만 이렇게 할 경우 왼쪽 공백과 중간 노드와 노드 사이의 공백에 대해서 따로 계산을 해 줘야 하는 문제가 생긴다. 그런데 그렇다고 한 쪽에만 공백을 추가하는 경우에는 깊이가 커짐에 따라 심각하게 모양이 무너지게 된다. 최대한 문제를 단순화하기 위해 막대의 모양은 생각하지 않고 노드의 좌, 우에 동일한 공백을 넣는다고 가정하고 다시 생각해 봐야 할 필요가 있다.
-
JUNGOL...135일지 2021. 9. 10. 18:12
Intermediate_Coder/자료구조/색종이(고) 문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 도화지에서 검은색 직사각형을 잘라내려고 한다. 직사각형 또한 그 변이 도화지의 변과 평행하도록 잘라내어야 한다. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 과 같은 모양으로 붙였다. 에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 22×5=110이 된다. 반면 에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 8×15=120이 된다. 검은색 색종이의 수와 각 색종이를 붙..
-
알고리즘...52일지 2021. 9. 10. 15:54
노드의 크기에 따른 출력 함수 제작 노드의 크기가 주어지고 데이터가 주어질 때 가운데 정렬이 된 상태의 스트링을 반환하는 함수를 만든다. 가령 노드의 크기가 5이고 노드의 값이 1이라고 하면 가운데 정렬을 위한 공백의 개수는 다음과 같다. 공백의 개수 = (노드의 크기 - 노드의 값의 길이) / 2 이때, 나눠지는 값이 홀수 인 경우 글자를 오른쪽에 치우쳐서 출력하기 위해 우측 공백을 추가로 준다고 하면, 왼쪽과 오른 른쪽 공백은 다음과 같이 구할 수 있다. 왼쪽 공백의 개수 = 공백의 개수 오른쪽 공백의 개수 = 공백의 개수 + (노드의 크기 - 노드의 값의 길이) % 2 정확한 공백을 확인하기 위해 ' ' 대신 '_'를 사용해 구현해 보면 다음과 같다. BinarySearchTree.h /// ///..
-
알고리즘...51일지 2021. 9. 9. 17:01
이진 검색 트리 출력 함수 제작 함수가 복잡해 지고 있으니 다시 기본으로 돌아와서 생각을 해보자. 기본 적으로 깊이가 1인 경우엔 하나의 노드만 출력하고 종료한다. 깊이가 2가 된 경우 깊이가 2인 경우엔 각 노드를 출력하고 노드를 공백으로 구분한다. (노드의 크기가 일정하게 존재해야 하며 숫자는 가운데 정렬이 될 수 있어야 한다.) 깊이가 3이 된 경우 중간의 길이는 더 길어지고 왼쪽 공백은 일정하게 증가한다. (가장 왼쪽 노드의 깊이별 공백은 (최대 깊이 - 현재 깊이) * 노드의 크기 만큼 존재해야 한다.) 노드가 비어있는 경우엔 노드의 길이 만큼 공백을 삽입해야 한다. 노드와 노드 사이의 공백은 (최대 깊이 - 현재 깊이) * 노드 * 2 + 1 만큼 존재해야 한다.