Kwin's Development Diary.

힙(heap) - 완전 이진트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해 만든 자료구조 - 최대 힙(max heap) ㄴ 키 값이 가장 큰 노드를 찾기 위한 완전 이진트리 ㄴ 부모 노드 키 값 ≥ 자식 노드 키 값 ㄴ 루트 노드 : 키 값이 가장 큰 노드 - 최소 힙(min heap) ㄴ 키 값이 가장 작은 노드를 찾기 위한 완전 이진트리 ㄴ 부모 노드 키 값 ≤ 자식 노드 키 값 ㄴ 루트 노드 : 키 값이 가장 작은 노드 힙 삽입 연산 1단계 : 완전 이진트리를 유지하면서 노드를 확장하여, 삽입할 원소를 임시 저장 ㄴ 노드가 n개인 완전 이진트리에서 다음 노드의 확장 자리는 n+1번의 노드 ㄴ n+1번 자리에 노드를 확장하고, 그 자리에 삽입할 원소를 임시 저장..

이진 탐색 트리 (Binary Search Tree) - 이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조 - 정의 ㄴ 모든 원소는 서로 다른 유일한 키를 가짐 ㄴ 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작음 ㄴ 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 큼 ㄴ 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리 - 연산 ㄴ 루트에서 시작 ㄴ 탐색할 키 값을 루트 노드의 키값과 비교한다 ▶ 키 값 = 루트 노드의 키 값 : 원하는 원소를 찾았으므로 탐색 연산 성공 ▶ 키 값 루트 노드의 키 값 : 루트 노드의 오른쪽 서브 트리에 대해 탐색 연산 수행 ㄴ 서브 트리에 대해 순..

트리 (tree) - 원소들 간 1 : 多 관계를 가지는 비선형 자료구조 - 원소들 간 계층 관계를 가지는 계층형 자료구조 - 상위 원소에서 하위 원소로 내려가면서 확장되는 나무 모양의 구조 ex) ☞ 노드 - 트리의 원소 : A, B, C, D, E, F, G, H, I, J, K, L ☞ 루트 노드 - 트리의 시작 노드 : A ☞ 간선 - 노드를 연결하는 선(= 부모 노드와 자식 노드를 연결하는 선) ☞ 형제 노드 - 같은 부모 노드의 자식 노드들 : (B, C, D), (E, F), (H, I, J), (K, L) ☞ 조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 : K의 조상 노드 = F, B, A ☞ 서브 트리 - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 :..

큐 (Queue) - 스택과 마찬가지로 삽입과 삭제의 위치가 제한된 유한 순서 리스트 - 선입선출 구조(FIFO, First-In-First-Out) : 삽입 순으로 나열되어 가장 먼저 삽입한 원소가 가장 먼저 삭제된다. 삭제 ← front rear 삽입 ← 큐의 연산 과정 - 삽입 : enQueue 더보기 ① 공백 큐 생성 : 큐가 생성되지 않은 최초 상태에서만 실행 Q [0] [1] [2] ↑ front == rear == -1 ↑ ② 원소 A삽입 : enQueue(Q, A); Q [0] [1] [2] A ↑ front == -1 ↑ ↑ rear == 0 ↑ ③ 원소 B삽입 : enQueue(Q, B); Q [0] [1] [2] A B ↑ front == -1 ↑ ↑ rear == 1 ↑ - 삭제 :..

스택(stack) - 스택에 저장된 원소는 top으로 정한 곳만 접근이 가능하다. ㄴ 후입 선출 구조(LIFO, Last-In-First-Out) : 마지막에 삽입한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제된다. 스택의 연산 - 삽입(push) ① top의 위치를 하나 증가(∵ top은 스택에서 마지막 자료를 가리키기 때문) 이때, 만약 top의 위치가 스택의 크기보다 커지면 오버플로우가 발생하므로 연산 수행하지 않고 종료. ② 스택의 top이 가리키는 위치에 삽입 -①-> -②-> ←top C ←top B ←top B B A A A - 삭제(pop) ① 스택이 공백이 아니라면 top이 가리키는 원소를 먼저 반환 ② 스택의 top의 위치를 그 아래의 원소로 변경(top 위치 하나 감소) -①-> -②..

이중 연결 리스트(doubly linked list) - 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트 - 이중 연결 리스트의 노드 구조 ㄴ 두 개의 링크 필드와 한 개의 데이터 필드로 구성 ㄴ llink(left link) 필드 : 왼쪽 노드와 연결하는 포인터 ㄴ rlink(right link) 필드 : 오른쪽 노드와 연결하는 포인터 llink data rlink ● ● // 노드 구조에 대한 구조체 정의 public class DblNode { DblNode llink; String data; DblNode rlink; }; - 리스트의 이중 연결 리스트 구성 1 ● → 1 → ← 2 null data1 2 ● 1 ● data2 null - 원형 이중 연결 리스트 1 ● ➥ ☇ 1 → ← 2 ..

리스트(List) - 자료를 나열한 목록 ex) 분식 = ['떡볶이', '김밥', '순대', '핫도그', '튀김', '어묵'] 수능 = ['국어', '수학', '영어', '사회', '과학', '외국어'] 나라 = ['대한민국', '미국', '중국', '일본'] 선형 리스트(Linear List) - 순서 리스트(Ordered List) - 자료들 간 순서를 갖는 리스트 선형 리스트의 저장 - 원소들의 논리적 순서와 같은 순서로 메모리에 저장 - 순차 자료구조의 원소 위치 계산 - 선형 리스트가 저장된 시작 위치 a - 원소의 길이 : l - i번째 원소의 위치 = a + (i-1) x l 선형 리스트에서의 원소 삽입 - 중간에 원소 삽입시 그 뒤 원소들은 한 자리씩 뒤로 이동하여 물리적 순서와 논리적 순..

행렬 (matrix) - m x n 행렬 ㄴ m : 행의 개수 ㄴ n : 열의 개수 ㄴ 원소의 개수 : (m xn) 개 행렬 A = a11 a12 ... a1n a21 a22 ... a2n . . . . . . . . am1 am2 ... amn 전치 행렬 - 행렬의 행과 열을 서로 교환하여 구성한 행렬 - 행렬 A의 모든 원소의 위치(i, j)를 (j, i)로 교환 - mxn 행렬을 nxm 행렬로 변환한 행렬 A'는 행렬 A의 전치 행렬 ex) A = 1 2 3 4 5 6 7 8 9 10 11 12 전치 행렬 변환↓ A' = 1 5 9 2 6 10 3 7 11 4 8 12 행렬의 순차 자료구조 표현 - 2차원 배열 사용 : mxn행렬을 m행 n열의 2차원 배열로 표현 ex) A = 1 2 3 4 5 6..

다항식 - ax^e 형식의 항들의 합으로 구성된 식 a : 계수 (coefficient) x : 변수(variable) e : 지수(exponent) - 지수에 따라 내림차순으로 항을 나열 - 다항식의 차수 : 가장 큰 지수 - 다항식 항의 최대 개수 = (차수 + 1) 개 다항식의 표현 - 각 항의 지수와 계수의 쌍에 대한 선형 리스트 ex) A(x) = 4x^3 + 3x^2 + 2 ☞ p1 = ((3, 4), (2, 3), (0, 2)) - 1차원 배열 이용 ex) P(x) = 4x^3 + 3x^2 + 2 차수(인덱스) x^3 x^2 x 0 계수(값) 4 3 0 2 - 2차원 배열 이용 ex) P(x) = 4x^1000 + 3x^2 + 2 차수 계수 1000 4 2 3 0 2 단순 연결 리스트를 이용..

코드의 재사용 - 개발비용을 줄이고 신뢰성과 생산성을 높임 - 객체 재사용 : 기존 객체의 인터페이스를 맞추어 새로운 프로그램에서 재사용 - 상속(inheritance) : 새로 필요한 객체*가 기존 객체**와 유사한 경우, 기존 객체의 코드를 상속받고 추가되는 부분만 작성하여 객체를 생성하는 방법 *새로 필요한 객체 : 자식 객체(child object), 하위 객체(sub object) **기존 객체 : 부모 객체(parent object), 상위 객체(super object) 자바의 캡슐화 - 캡슐화된 클래스를 조합하여 프로그램 구성 (class 키워드) - 클래스 내부의 멤버들을 캡슐화하기 위해 접근 제어자 사용 > public - 모든 클래스에서 접근 가능 > protected - 같은 패키지의..