공부방

수식 트리 수식을 표현하는 이진 트리 수식 이진 트리라고 부르기도 함 연산자는 루트 노드이거나 가지 노드(internal node) 피연산자는 모두 잎 노드(external node) 힙 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 최대힙 부모 노드의 키 값>=자식 노드의 키 값 루트 노드 : 키 값이 가장 큰 노드(최대 값) 전체의 노드/2=부모의 노드 개수 최소힙 부모 노드의 키 값 1) { swap(cur, cur / 2); cur = cur / 2; } break; case 2: if (lastidx == 0) { System.out.print("-1" + " "); break; } System.out.print(arr[1] +..

비선형 구조 원소들 간에 1(부모):N(자식) 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 한 개 이상의 노드로 이루어진 유한 집합 노드 중 최상위 노드를 루트(root)(부모X 자식만 있고 부모는 없다.)라고 한다. 나머지 노드들은 n(>=0)개의 분리 집합 T1,...,TN으로 분리될 수 있다.(간선을 끊을 수 있다.) 이들 T1,...TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라 한다. 트리 용어 leaf노드(external node) : 부모만 있고 자식이 없는 노드 internal node : 자식의 수가 1개 이상있는 노드 노드: 트리의 원소 트리 T의 노드-A,B,C,D,E,F,G,H,I,J,K 간선 : 노드를 연결하는 선, 부모 노..

자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적이 자료구조를 이룬다. 링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다. 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능하다. 노드 연결 리스트에서 하나의 원소에 필요한 데이터(주소값)를 갖고 있는 자료단위 구성 요소 데이터 필드 원소의 값을 저장하는 자료구조 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용함 링크 필드 다음 노드의 주소를 저장하는 자료구조 헤드 리스트의 처음 노드를 가리키는 레퍼런스 단순 연결 리스트 연결 구조 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가..

원형 큐 초기 공백 상태 front=rear=0 Index의 순환 front와 rear의 위치가 배열의 마지막 인덱스인 n-1을 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야함 이를 위해 나머지 연산자 mod를 사용 front 변수 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠. 선형 큐 원형 큐 front / rear 가장 첫번째 원소 한 칸 앞 idx / 가장 마지막 원소 초기 값 front->-1 / rear->-1 front->0 / rear->0 가장 첫번째 삽입 원소 idx 0 1 enQueue rear++ arr[rear]->item rear->(rear+1)%arr.length arr[rear]-..

스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조 선입선출구조(FIFO) 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입(first in)된 원소는 가장 먼저 삭제(first out)된다. 큐의 시작과 끝이 같다면 큐는 비어 있는 것 머리는 꼬리와 같이 원소를 가리키는 것이 아니라 첫번째 원소 앞에 -1을 처음에는 가리킨다. enQueue->rear++ deQueue->front++ 선형큐 1차원 배열을 이용한 큐 큐의 크기=배열의 크기-size() front : 마지막으로 삭제된 인덱스=배열에서 큐의 첫번째 원소의 idx-1 rear : 저장된 마지막 원소의 인덱스 상태 표현 초기 상태 : front=rear=-1 공백 상..

중위 표기식의 후위 표기식 변환 방법 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다. 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다. 괄호를 제거한다. 재귀 호출 자기 자신을 호출하여 순환 수행되는 것 함수 호출은 메모리 구조에서 스택을 사용한다.(이름만 같은 다른 메서드) 간단한 문제에 대해서는 반복문에 비해 메모리 및 속도에서 성능저하가 발생한다. 일반적으로 기본 부분(Base case), 재귀 부분(Recursive case)로 구성된다. Base case : 재귀 호출에서 빠져 나가기 위한 조건 Recursive case : 자신을 호출하는 부분 (Base case로 유도한다.) 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다. pac..

선형구조를 갖는다. 선형 구조 : 자료 간의 관계가 1대1의 관계를 갖는다. 비선형 구조 : 자료 간의 관계가 1대N의 관계를 갖는다.(예 : 트리) 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조이다. 스택에 자료를 삽입하거나 스택에 자료를 꺼낼 수 있다.(위에서만 삽입하고 꺼낸다.) 마지막에 삽입한 자료를 가장 먼저 꺼낸다. 후입선출이라고 부른다. ex) 스택에 1,2,3 순으로 자료를 삽입한 후 꺼내면 역순으로 즉 3,2,1순으로 꺼낼 수 있다. 스택에서 마지막 삽입된 원소의 위치를 top이라고 부른다. 처음 top은 -1로 초기화 top=-1 ->스택이 비어있음 top=0~n-1 ->스택이 차 있음 top=n-1->스택이 꽉 참 연산 삽입 : 저장소에 자료를 저장한다. 보통 push라고 부른..

문자로 정수형 나타내기 package test1; public class test1 { public static void main(String[] args) { int zero = '0' - '0'; int one = '1' - '0'; int two = '2' - '0'; } } 문자열(String)로 숫자 입력받고 숫자(Int) 배열로 나타내기 package test1; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import org.omg.CosNaming.IstringHelper; public class test2 { public s..

2차원 배열 package test01; public class Test1_ArrayTest { public static void main(String[] args) { int[][] arr = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int n = arr.length; int m = arr[0].length; // 1. 행 우선 순회 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { System.out.printf("%3d", arr[i][j]); } System.out.println(); } System.out.println(); // 2. 행 역우선 순회 for (int i = 0; i < n; i++) {..

완전검색 완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다. Brute-force 혹은 Generate-and-Test 기법이라고도 불리운다. 모든 경우의 수를 테스트한 후, 최종 해법을 도출한다. 일반적으로 경우의 수가 상대적으로 작을 때 유용하다. 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다. 자격검정평가 등에서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다. package test01; public class test1순열 { public static void main(String[] args) {..