저번 포스팅에선 트리, 이진 트리에 대해 알아보았다. [비선형 자료구조] 트리 링크 더보기 트리(1) - 이진 트리(Binary Tree) 트리(3) - AVL 트리 트리(4) - Red-Black 트리 이번 포스팅에서는 이진 탐색 트리에 대해 알아보자. 이진 탐색 트리(Binary Search Tree = BST) 이진 탐색 트리는 이진 트리의 종류중 하나로 다음과 같은 특징을 가지고 있다. 왼쪽 자식 노드의 키는 부모 노드의 키보다 작다. 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다. 각각의 서브트리도 이진탐색트리를 유지한다. 중복된 키를 허용하지 않는다. 중위순회(왼중오)하면 오름차순으로 (탐색)나온다. 기존 이진트리에 비해 탐색이 빠르다.(하지만 균형 유지가 필요하다.) 이진 트리는 규칙없이..
[비선형 자료구조] 트리 링크 더보기 트리(2) - 이진탐색트리 트리(3) - AVL 트리 트리(4) - Red-Black 트리 트리(Tree) 트리는 노드와 링크로 구성된 자료구조다. 그래프의 일종으로 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph) 또는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류 이다.(Acyclic = cycle이 존재하지 않는 그래프) 계층적 구조(계층 모델)를 나타낼 때 사용한다. 조직도, 가계도, 폴더(디렉토리, 서브 디렉토리)와 같은 파일시스템 구조나 계층적으로 저장할 때 많이 쓰인다. 구조상 데이터 저장보다는 저장된 데이터의 효과적인 탐색을 위해 사용된다. 선형 자료구조는 정렬이 되어있지않은 상태에..
복잡도는 알고리즘 성능을 나타내는 척도이다. 크게 시간복잡도와 공간복잡도로 나눠볼 수 있으며, 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시한다. 일반적으로 시간복잡도와 공간복잡도는 trade-off관계에 있다. 즉, 시간복잡도를 줄이려면 공간복잡도(메모리 사용량)가 늘어나고, 공간복잡도를 줄이려면 시간복잡도가 늘어나는 그런 관계라는 뜻이다. 시간복잡도(Time Complexity) 작성한 알고리즘 코드가 입력값에 비례해서 어느정도의 연산량을 필요로 하는지 그 연산횟수를 말한다.(알고리즘 필요 연산 횟수) 시간 복잡도(Time Complexity)는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을..
지수(Power)와 로그(Logarithm) 지수와 로그에 대해 간단히 알아보자. 지수의 정의는 아래와 같다. 여기서 a를 밑, b를 지수라고 표현한다. 로그의 정의는 아래와 같다. 지수와 로그(java) 지수와 로그는 자바의 Math 클래스를 이용해 구할 수도 있고, 직접 구할 수도 있다. 간단한 개념이니 어떤 함수가 있는지만 알아보자. 제곱 : Math.pow(밑, 지수) 제곱근 : Math.sqrt(수) 혹은 Math.pow(수, 1.0/2)이다. 직접 제곱근 구하는 방법은 수식적으로 몇가지 있다. 대표적으로 바빌로니아 방법과, 뉴튼 방법 등이 있다. 절댓값 : Math.abs(수)이다. e : Math.E; (자연상수) 지수 함수(자연 지수 함수) : Math.exp(수) = e^수 로그 : Ma..
최대공약수, 최소공배수의 간단한 정의를 알아보자. 약수 : 어떤 수를 나누어 떨어지게 하는 수이다. 공약수 : 어떤 두 수를 동시에 나누어 떨어지게 하는 수이다. 최대공약수(Greatest Common Devisor, GCD) : 두 수의 공약수 중 가장 큰 수를 말한다. (재귀함수로도, 그냥으로도 구현해보자) 공배수 : 어떤 두 수의 공통된 배수이다. 최소공배수(Least Common Multiple) : 두 수의 공배수 중 가장 작은 수를 말한다. 최대공약수를 먼저 구한 다음에 두 수를 곱하고 최대공약수로 나눠주면 최소공배수가 나온다.(A*B/최대공약수) 대부분의 경우, 수학적으로 계산할 때 최대공약수와 최소공배수는 소인수분해를 이용하는 방법으로 구하게 된다. 하지만 컴퓨터를 이용해 최대공약수를 찾을..
문제 입력 출력 코드( python ) n,m,a = map(int, input().split()) print(pow(m, n-1, 1000000007)) 코드( java ) import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long answer = 1L; int n = sc.nextInt(); int m = sc.nextInt(); int a = sc.nextInt(); int h = sc.nextInt(); for(int i = 0; i < n-1; i ++){ answer = (answer * m)%1000000007; } System.ou..
학교에서 분명 배웠던 것 같은데, 수열과 순열은 항상 헷갈리고, 조합 계산식도 기억이 안난다. 그럼 정리해보자. 수열(Sequence) 수열 a이란 정의역이 순서수(ordinal number) α ∈ ON인 함수를 말한다. a:α→S 뭐라는지 모르겠는가? 필자도 그렇다. 쉽게 다가가보자. 쉽게 말하자면 수열은 어떤 규칙에 따라서 숫자들을 늘어놓은걸 말한다. (규칙이 없어도 수열이라고는 하지만 그건 몰라도 된다.) 수열은 일반적으로 aₙ, bₙ 이런식으로 표현된다. 여기서 a, b는 수열의 이름, n은 항의 번호를 나타낸다. (n은 자연수) 항이란 수열에서 나열한 하나하나의 수를 의미한다. 예를 들어, aₙ = 1,2,3,4,5,6... 이면 a₁ = 1, a₂ =2, a₃ = 3 이라는 뜻이다. 즉, a..
집합(Set) 집합표현방법엔 원소나열법(tabular form), 조건제시법(set-builder form), 벤 다이어그램(Venn diagram) 등이 있다. 조건제시법 - B = {2B | B는 정수, 1 ≤ B ≤ 5}면 {2, 4}인 집합을 말하듯이 조건을 제시해서 표현하는 방법이다. 집합의 크기는 집합의 원소의 개수를 의미한다. 대표적인 집합의 종류에 대해 아주 간단히만 알아보고 넘어가자. 집합에는 교집합, 합집합, 차집합, 여집합 등이 있다. 교집합(Intersection) : A ∩ B = {x | x∈A and x∈B} 합집합(Union) : A ∪ B = {x | x∈A or x∈B} 차집합(Difference of sets) : A - B = {x | x∈A and x∉B} 여집합(C..
연결리스트는 데이터를 링크로 연결해서 관리하는 자료구조다. 자료의 순서는 정해져 있지만 메모리상의 연속성은 보장되지 않는다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전, 다음 노드와의 연결을 담당한다. 연결리스트에서 사용되는 용어는 다음과 같다. node : 데이터 저장 단위로 값과 포인터로 구성된다.(내부 부품이기에 외부에 노출되지 않는것이 좋다. private) pointer : 다음 노드나 이전 노드의 연결 정보(다음 혹은 이전 노드의 주소(정보)값)(Next) head : 가장 처음에 위치하는 노드를 일컫는다. tail : 가장 마지막에 위치하는 노드를 일컫는다. 노드를 가리키는 포인터는 C에서는 포인터변수가 있었지만 여기서는 그냥 같은 타입으로 해서 연결해주면 된다. no..
ADT(Abstract Data Type) ADT(Abstract Data Type)은 추상자료형, 구현방법을 명시하지 않고 자료구조의 특성들과 어떤 Operation이 있는지를 설명하는 자료구조의 한 형태이다. 대표적으로 스택과 큐가 있다. 어떻게 구현되는지가 추가되면 DS로써의 스택과 큐가 된다. 자바 기준으로는 interface가 ADT, class가 DS이다. 스택이 어쩌고 저쩌고 -> ADT 관점, 그래서 스택을 어떤 구현체를 써서 구현했어 -> DS 관점이다. 선형(Linear) 자료구조, 비선형(Nonlinear) 자료구조 선형 자료구조는 하나의 자료 뒤에 하나의 자료가 존재하는 것이다. 자료간의 1:1 관계가 유지되는 것이다. 스택, 큐, 배열 등이 이에 해당한다. 비선형 자료구조는 하나의..
