본문 바로가기

분류 전체보기215

이진 트리의 레벨 순회 레벨 순회(level order)- 각 노드를 레벨 순으로 검사- 루트 노드의 레벨은 1, 아래로 내려갈수록 레벨 증가- 큐 사용 - 큐에 노드가 하나라도 있으면 계속 반복- 큐에 있는 노드를 꺼내어 방문한 다음, 그 노드의 자식 노드를 큐에 삽입하는 과정이 한 번의 반복- 이러한 반복을 큐에 노드가 존재하지 않을 때까지 계속1. 루트 노드인 +가 큐에 입력된 상태에서 순회 시작2. 큐에서 하나를 삭제하면 +가 pop3. 노드 +를 방문한 다음 노드 +의 자식 노드인 *와 /를 큐에 삽입4. 다시 반복의 처음으로 복귀 전체 코드#include #include #include typedef struct TreeNode { int data; struct TreeNode* left, * right;} Tree.. 2024. 8. 19.
이진 트리의 반복적 순회 스택을 이용한 반복적 순회 구현- 스택에 자식 노드들을 저장하고 꺼내면서 순회- 순환 호출도 시스템 스택을 사용하고 있으므로 별도의 스택을 사용하면 순환 호출과 동일한 기능을 구현 가능 전체 프로그램#include #include #include typedef struct TreeNode { int data; struct TreeNode* left, * right;} TreeNode;#define SIZE 100int top = -1;TreeNode* stack[SIZE];void push(TreeNode* p) { if (top = 0) { p = stack[top--]; } return p;}void inorder_iter(TreeNode* root) { while (1) { for (; root.. 2024. 8. 19.
이진 트리의 순회 순회(traversal): 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것- 스택, 큐, 덱 등은 데이터를 선형으로 저장하므로 자료에 순차적으로 순회하는 방법이 한 가지뿐- 트리는 여러 가지 순서로 자료에 접근 가능이진 트리 순회 방법루트 방문: V왼쪽 서브 트리 방문: L오른쪽 서브 트리 방문: R1. 전위 순회(preorder traversal): VLR- 루트 → 왼쪽 서브 트리 → 오른쪽 서브 트리 순으로 방문※ 왼쪽 서브 트리와 오른쪽 서브 트리도 하나의 이진 트리이므로, 전체 트리와 똑같은 방식으로 서브 트리를 방문∴ 왼쪽 서브 트리의 루트 방문 → 왼쪽 서브 트리의 왼쪽 서브 트리 방문 → 왼쪽 서브 트리의 오른쪽 서브 트리 방문 → ... 2024. 8. 19.
백준 1463: 1로 만들기(java) 문제풀이 3개의 경우(3으로 나누어떨어짐, 2로 나누어떨어짐, 둘 다 아님) 중 어떤 경우에 어떤 연산을 고려해야 하는지 결정하는 것이 중요한 문제이다. 크게 4가지 케이스로 나눌 수 있다.3과 2로 모두 나누어떨어질 때: 3으로 나누기/2로 나누기/1 빼기 中 연산 횟수 적은 것 택 13으로만 나누어떨어질 때: 3으로 나누기/1 빼기 中 연산 횟수 적은 것 택 12로만 나누어떨어질 때: 2로 나누기/1 빼기 中 연산 횟수 적은 것 택 11~3 중 해당사항 없을 때: 1 빼기예제 2의 경우, N=10일 때 3번 케이스이므로, 2로 나누어 10→5→4 →2 →1로 진행할지(연산 횟수: 4) 1을 빼 10 →9 →3 →1(연산 횟수: 3)로 진행할 지 선택해야 한다.if(arr[N]==null) { if(N.. 2024. 8. 9.
이진 트리의 표현 이진 트리를 컴퓨터 프로그램 내에서 표현하려면배열을 이용하는 방법포인터를 이용하는 방법위 2가지 방법을 사용할 수 있음배열 표현법- 주로 포화 이진 트리나 완전 이진 트리에서 자주 사용(그 외 이진 트리에서도 사용 가능)- 저장하고자 하는 이진 트리를 완전 이진 트리라 가정, 이진 트리의 깊이가 k이면 최대 2ᵏ-1개의 공간을 연속적으로 할당한 다음 완전 이진 트리의 번호대로 노드들을 저장- 이때 인덱스 0은 사용되지 않음- 완전 이진 트리가 아닌 일반적인 이진 트리의 경우, 배열 표현법으로 표현하면 기억공간의 낭비 有- 부모와 자식 인덱스 간 아래와 같은 공식 성립- 노드 i의 부모 노드 인덱스 = i/2- 노드 i의 왼쪽 자식 노드 인덱스 = 2i- 노드 i의 오른쪽 자식 노드 인덱스 - 2i + 1.. 2024. 8. 7.
백준 1874: 스택 수열(java) 문제문제를 이해하기만 하면 스택을 사용해 쉽게 풀이할 수 있는 문제인 듯 하다. 예제를 기준으로 설명해 보자. 4를 입력받았을 때 1부터 4까지 스택에 오름차순으로 push하고, 이때 스택의 top에 만들어야 하는 수열의 요소인 4가 있으므로 pop한다. 다음으로 3이 입력되지만, 앞선 입력으로 3까지의 수는 이미 스택에 삽입된 바 있기 때문에 이번에는 1부터 3까지 오름차순으로 push하는 작업 없이 바로 스택 top에 3이 있는지 확인한다. top에 3이 있으므로 이를 pop하고 다음 입력으로 넘어간다. 6을 입력받아 이전에 삽입된 적 없는 5와 6을 push하고 위와 같은 과정을 반복해 주면 예제와 같은 출력이 완성된다. 도식적으로 표현하면 아래와 같다.풀이 직전에 push한 요소의 다음 요소부터 .. 2024. 8. 7.

티스토리툴바