기록하는 습관 "기습"

이진 탐색 트리 Binary search tree 이진 검색 트리라고도 하며, 이진 트리에 탐색을 위한 조건을 추가한 자료구조다. 조건은 다음과 같다. 모든 원소는 유일한 키값을 갖는다. 왼쪽 서브 트리의 원소 키들은 그 루트의 키보다 작다. 오른쪽 서브 트리의 원소들은 그 루트의 키보다 크다. 왼쪽 오른쪽 서브트리도 모두 이진 탐색 트리다. 그림의 예를 보자. 그림의 맨 위, 루트노드의 키값은 5이다. 오른쪽 자식노드의 키값 7이며 5보다 크다. 왼쪽 자식 노드의 키값은 3이며 5보다 작다. 이번엔 왼쪽 서브트리를 보자. 왼쪽 자식 노드의 키값은 1이며 3보다 작다. 4는 부모노드의 키값 3보다 크기 때문에 오른쪽으로 가게 된다. 이진 탐색 트리 - 검색 키값이 x인 값을 찾으려 한다. 이진 탐색 트리..

트리 Tree 1대1 관계를 갖는 선형 linear 구조와 달리 1대 多 관계를 갖는 비선형 자료구조(Nonlinear data structure)이다. 이뿐만 아니라 원소들 간의 계층관계를 가지는 계층형 자료구조(Hierarchical data structure)이다. 트리의 용어설명 노드Node : 원소이다. 트리는 이들이 모인 결과의 집합이다. 차수degree : 연결된 자식노드의 수이다. 트리의 차수 : 트리 내의 노드의 차수 중에 가장 큰 값이다. 아래 그림에서는 노드 A D의 차수가 3과 같다. 간선Edge : 부모와 자식노드의 연결선. 높이Height or level : 높이에 따른 계층구분. 트리의 높이는 그 트리의 높이 중에서 가장 큰값이 된다. 아래 그림을 예시로 들면 레벨 3이다. 루..

새 데이터를 맨 위에 두고 가장 먼저 사용하는 후입선출(Last-In-First_Out) 유형의 자료구조이다. 스택이 저장된 원소는 top이라는 곳에서만 접근 가능. 이는 데이터를 저장하면 할수록 같이 올라간다. 스택은 순차자료구조나 연결자료구조로 구현할 수 있다. 순차자료구조로 스택을 구현할 때는 크기가 고정된 배열이므로 비어있는 공간이 생겨서 낭비될 수 있으며 크기 변경이 불가하다는 단점이 있다. 물론, 연결 자료구조로 이러한 단점들을 해결할 수 있다. 스택이 empty 상태라면 top은 -1의 값을 갖는다. 스택의 연산 삽입 : push 삭제 : pop 스택 맨 위 값 알아보고 리턴 : peek 스택의 응용 push와 pop을 이용하여 역순 문자열을 만들 수 있다. 프로그램에서 호출과 복귀에 따른 ..

순차 자료구조의 문제점 연산 시간의 문제: 삽입 삭제 후에 연속적으로 원소들을 이동시키는 작업이 필요한데, 삽입 삭제하는 양이나 애당초 배열의 크기가 클수록 연산량이 많아져 성능의 문제가 발생한다. 저장공간의 문제: 배열 자체의 메모리 비효율성 문제로 동적으로 변해야 하는 경우 낭비가 발생한다. 앞서 이유로 인해 대안으로 연결 자료구조 방식이 있다. 다만 순차 자료구조가 문제의 특성에 따라서는 연산에서나 저장공간에서나 이득일 수도 있다. 연결(linked) 자료구조 방식 논리적 순서와 물리적 순서가 일치하지 않는 자료구조 방식이다. 원소들 저장할 때 다음 원소의 주소도 함께 저장해놓는다. 크기 변경이 유연하고, 원소를 삽입/삭제할 때마다 원소를 이동시킬 필요가 없다. 연결 방식에 따른 리스트 구분 더보기..

데이터 구조화의 가장 기본적인 방법은 데이터를 나열하는 것이다. 이에 '리스트'는 죽 나열한 데이터를 의미한다. 선형리스트(Linear list 혹은 순서 리스트 Order list) 나열한 자료들 간에 앞뒤 관계가 1대1인 리스트를 의미한다. 리스트는 앞서 표현하며, 원소를 나열한 순서는 원소들 자체의 순서가 된다. 덧붙여서, 공백 리스트, 즉 원소가 하나도 없는 리스트도 엄연히 리스트이다. 더보기 리스트 연산 더보기 리스트를 관라하기 위해서는 연산이 필요하다. 다음은 연산 작업의 예이고, 이러한 연산 목록은 필요에 따라 더하거나 뺄 수 있다. 리스트의 두 가지 구현 방식 순차(sequential) 자료구조 방식과 연결(linked) 자료구조 방식이 있다. 장단점이 분명하기에 상황에 맡게 쓴다. 연결 ..

고정소수점(fixed point): 왼쪽밖에 소수점이 고정된 것으로 표현. -다만 이는 표현할 수 있는 자리수가 적음. 0.0000000101에서 맨 뒤 101과 소수점 앞은 빠지게 됨 부동(floating point): 소수점의 위치가 변함. 부호, 지수부, 가수부로 나뉨. -0.001234=-0.1234*10(지수-2) 1(부호,음수이기에 1) -2((지수부, 소수점 오른쪽으로 2칸) 1234(가수부) -10진수는 2진수표현으로 정확히 나타내지 못함. 이때문에 java에서는 bigdecimal class를 이용해 10진수 소수 계산을 할 수 있음. 10진수 실수(존과 팩 형식) 10진수의 2진수 실수표현은 근복적으로 부정확한 표현법. 이를 위해 10진수 실수법으로 표현. 존 형식(zoned decim..