본문 바로가기

컴퓨터공학/알고리즘 ˙ 자료구조11

[자료구조] B-tree와 B+tree 이진트리 종류 정이진트리 Full Binary Tree 트리의 모든 노드가 0개 혹은 2개의 자식을 가지는 경우 (한국의 교재에선 포화이진트리라고 번역된 게 있는데 둘은 다른 개념이다.) 포화이진트리 Perfect Binary Tree 말 그대로 마지막 레벨까지 노드가 꽉 찬 트리, (2^N-1)개의 노드를 가진다. 완전이진트리 Complete Binary Tree 마지막 레벨을 제외한 모든 레벨에서 순서대로 노드가 꽉 찬 트리, 마지막 레벨은 왼쪽부터 채워져야 한다. 균형이진트리 Balanced Binary Tree 말단 노드들의 레벨 차이가 최대 1레벨까지만 나는 트리, 균형이 깨지면 별도의 로직을 통해 다시 균형을 잡게 된다. 포화이진트리, 완전이진트리, 정이진트리는 이상적인만큼 현실에서 잘 찾아볼.. 2023. 4. 24.
[알고리즘] 2차원 배열 시계 방향 회전, 180도 회전, 전치 행렬 구하기 외우면 구현 빠른 알고리즘 시계 방향 회전 (90도 회전) // origin[ROW][COL] // rotated[COL][ROW] for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { rotated[j][ROW-1-i] = origin[i][j]; } } 반시계 방향 회전 (270도 회전) // origin[ROW][COL] // rotated[COL][ROW] for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { rotated[COL-1-j][i] = origin[i][j]; } } or 시계방향 * 3회 180도 회전 // origin[ROW][COL] // rotated[COL.. 2023. 4. 10.
[C++] 달팽이 알고리즘 정방향 행렬에서 시계 방향으로 탐색 시 N, N-1, N-1, N-2, N-2, ... , 2, 2, 1,1 순서로 값이 채워지는 규칙이 있다. 이 규칙을 이용하면 코드 축약에 도움을 준다. sign 을 사용하는 것은 x가 증가하는 쪽으로 변화하면 다음 y는 감소하는 쪽으로 변화하고, 반대로 y가 증가하면 x는 감소하기 때문이다. int size=N*N-1, sign=1; int x=0,y=0; // 초기 N번 한 번 for(int i(0) ; i0 ; i--){ for(int j(0) ; j 2023. 3. 22.

티스토리툴바