안 쓰던 블로그

그래프 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조 그래프 G는 객체를 나타내는 정점(V)와 객체를 연결하는 간선(E)의 집합이다 G=(V,E) 종류 무방향 그래프 두 정점을 연결하는 간선에 방향이 없는 그래프 (Vi, Vj)로 표현한다 V정점은 ABCD E간선은 AB, AD, BC, BD ,CD 방향이 없음 방향 그래프 =다이그래프 간선에 방향이 있는 그래프 Vi->Vj를 로 표현한다 는 A->B 는 B->C 완전 그래프 각 정점에서 다른 모든 정점이 연결된, 최대로 많은 간선 수를 가진 그래프 정점이 n개인 무방향 그래프에서 최대 간선 수: n(n-1)/2개 정점이 n개인 방향 그래프에서 최대 간선 수: n(n-1)개 G5의 간선 수: 정점의 개수는 4개고 무방향 그래프이므로 완전 그래..

HEAP 완전 이진 트리에 있는 노드 중에서 특정 노드(키 값이 가장 큰 노드나 가장 작은 노드)를 찾기 위해서 만든 자료구조 최대 힙 max heap 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 (이진 트리: https://foxtrotin.tistory.com/184 ) {부모 노드의 키 값>자식 노드의 키 값} 루트 노드: 키 값이 가장 큰 노드 최소 힙 min heap 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 {부모 노드의 키 값 삽입 원소의 키값} 관계가 성립되지 않으면 서로 자리를 바꾸면서 제 자리를 찾는다 예를 들어 17을 삽입하는 경우 완전 이진 트리의 무게를 맞출 수 있는 곳인 오른쪽 맨 아래 노드에다가 17짜리 노드 추가 값 비교 하면서 17이 있어야 할 자리로 옮긴..

트리 개념, 이진 트리, C로 트리 구현: https://foxtrotin.tistory.com/184 자료구조-트리 순회(전위 순회, 중위 순회, 후위 순회) https://foxtrotin.tistory.com/187 자료구조-이진탐색트리 BST https://foxtrotin.tistory.com/190 AVL트리가 왜 필요한가? 이진탐색트리 탐색의 특징 때문에 편향 트리에서 탐색 시간이 비효율적 예를 들어 저번 글의 코드에서 입력값이 이랬다 이런 경우 이쁘게 트리가 완성이 되어서 80을 찾는 데 50->70->80을 지나 3번만 탐색하면 된다 근데 아래 코드와 같은 입력일 경우 #include #include typedef struct node { int key; struct node* left,..

트리 개념, 이진 트리, C로 트리 구현: https://foxtrotin.tistory.com/184 자료구조-트리 순회(전위 순회, 중위 순회, 후위 순회) https://foxtrotin.tistory.com/187 이진 탐색 트리 이진 트리를 탐색용 자료구조로 쓰기 위해 원소 크기에 따라 노드 위치를 정의한 트리 -모든 원소는 서로 다른 유일한 키를 갖는다 -왼쪽 서브 트리에 있는 원소의 키는 루트의 키보다 작다 -오른쪽 서브 트리에 있는 원소의 키는 루트의 키보다 크다 -왼쪽/오른쪽 서브 트리도 이진 탐색 트리다 이진 탐색 트리의 탐색 연산 1. 루트에서 시작한다 2. 탐색할 키 값 x과 노드의 키 값을 비교 2-1. (x==루트 노드의 키 값)인 경우: 찾음 2-2. (x루트 노드의 키 값)인..

트리 개념, 이진 트리, C로 트리 구현: https://foxtrotin.tistory.com/184 이진 트리 순회 모든 원소를 빠뜨리거나 중복하지 않고 처리하는 연산 이진 트리의 순회를 위한 세부 작업 1. 현재 노드를 방문하여 처리 2. 현재 노드의 왼쪽 서브 트리로 이동 3. 현재 노드의 오른쪽 서브 트리로 이동 순회 종류 1. 전위 순회 2. 중위 순회 3. 후위 순회 1. 전위 순회 작업 순서: 현재 노드->왼쪽->오른쪽 이런 트리가 있다면 순회 경로는 A-B-D-H-E-I-J-C-F-G-K 수식에 대한 전위 순회 A*B-C/D 라는 수식을 전위 순회로 트리를 만들면 위와 같다 순회 경로: -*AB/CD -를 킵해두고 A*B 계산, C/D 계산. 두 값으로 -계산 2. 중위 순회 작업 순서:..

트리 원소들 간에 1:n 관계를 가지는 비선형 자료구조 원소들 간에 계층 관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양 구조 노드: 트리의 원소 -트리 A의 노드: A,B,C,D,E,F,G,H,I,J,K,L 루트 노드: 트리의 시작 노드, 레벨0 -트리 A의 루트 노드: A 간선: 노드를 연결하는 선, 부모-자식 노드 연결 형제 노드: 같은 부모 노드의 자식 노드들 -B,C,D는 형제 노드 조상 노드: 간선을 따라 루트 노드까지 경로에 있는 모든 노드들 -K의 조상 노드: F, B, A 서브 트리: 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 -각 노드는 자식 노드의 개수 만큼 서브 트리를 가짐 -D를 부모로 가지는 H,I,J는 D라는 서브 트리 자손 노드..

1. 다음 프로그램의 실행결과를 예측해 보시오 # include void fun(int x) { x = 30; } int main() { int y = 20; fun(y); printf("%d", y); return 0; } 더보기 답: 20 값에 의한 호출로 main안의 y변수 값은 바뀌지 않는다 2. 다음 프로그램의 실행결과를 예측해 보시오 # include void fun(int* ptr) { *ptr = 30; } int main() { int y = 20; fun(&y); printf("%d", y); return 0; } 더보기 답: 30 주소에 의한 호출로 main안의 y변수 값이 바뀐다 3. 다음 프로그램의 실행결과를 예측해 보시오 #include int main() { int* ptr; ..