Do it! 자료구조와 함께 배우는 알고리즘 입문

문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합가령 최댓값을 구하라는 문제가 주어졌다고 가정해보자.우리는 문제를 해결할 일련의 로직, 즉 논리적인 흐름을 작성하고 그에 맞는 입력을 받은 후 출력을 행할 것이다.그 일련의 로

자료구조란 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계를 말한다.자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법을 말한다.멤버는 객체 자신만의 속성이자 특징이므로 외부에 공개하는 것이 반드시 좋은 것은 아니다.객체의 멤버에 대한 접근을 제한할

소수는 2부터 n-1까지의 어떤 정수로도 나누어 떨어지지 않는다. -> 일반적인 소수의 개념소수는 2부터 n-1까지의 어떤 소수로도 나누어 떨어지지 않는다. -> 알고리즘 개선(1)1부터 n까지의 소수를 계산한다고 했을 때, 배열의 초기 요소로 2를 주고 소수를 발견하

검색 알고리즘 배열 검색 1) 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행한다. 2) 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행한다. 3) 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른

데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO)이다.스택에 데이터를 넣는 작업을 푸시라고 하고, 스택에서 데이터를 팝이라고 한다.푸시와 팝을 하는 위치를 탑, 스택의 가장 아랫부분을 바텀이라 한다.자바에서 메서드를

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다.두 정수의 최대공약수는 두 정수를 변으로 하는 직사각형을 위의 방법처럼 채워나가다보면 정사각형만으로 구성되게 할 수 있다. 이 정사각형의 길이가 최대공약수이다.recur(4)를 구

정렬이란 이름, 학번 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말한다.키 값이 작은 데이터가 앞쪽에 있는 것이 오름차순, 반대로 있는 것이 내림차순이다.정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입이며 대

일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘이다.시간 복잡도는 평균적으로 n log n이지만, 최악의 경우 O(n^2)이다.피벗이라고 부르는 기준이 될 임의의 값을 선택한다.피벗 이하의 그룹, 피벗 이상의 그룹으로 나눈다.두 그룹에서 다시 각각의 피벗을 선정하고

3장에서 이진검색에 사용했던 binarySearch 메서드는 java.util.Arrays 클래스의 클래스 메서드로 제공한다.이 클래스는 배열을 정렬하는 클래스 메서드 sort도 제공한다.sort 메서드는 퀵 정렬 알고리즘을 개선한 것으로 안정적이지 않다.자연정렬 :

요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다.도수 분포표가 필요하기 때문에 최솟값과 최댓값을 미리 알고있는 경우에만 사용할 수 있다.안정적이다.10점 만점의 테스트에서 학생 9명의 점수를 나타내는 배열 a가 있다.10점 까지의 점수 내에서 해당

명확한 조건을 만족하는 자료의 모임을 의미한다. 자료구조로 표현할 수 있다.요소들이 중복되지 않는다.순서가 없다배열로 집합을 표현하려면, 위의 특징과 더불어 집합의 요소 개수와 배열의 요소 개수는 항상 같아야한다.즉, 집합의 상태를 표현할 데이터가 필요하다.set에 배

문자열 검색이란 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고 들어있다면 그 위치를 찾아내는 것을 말한다."STRING"에서 "IN"을 검색하면 3(인덱스)을 반환한다.순서대로 하나하나씩 비교하는 방법이다.java.lang.String 클래스는 문자열을 검색하는

리스트란 데이터를 순서대로 나열한 자료구조이다.데이터를 순서대로 나열해 놓은 리스트를 선형 리스트 또는 연결 리스트라고 한다.리스트의 데이터는 노드 또는 요소라고 부르며, 각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있다.처음과 끝에 있는 노드를 각각

루트 : 트리의 가장 윗부분에 위치한 노드이다.리프 : 트리의 가장 아랫부분에 위치한 노드이다. 물리적으로 가장 아래부분에 위치한다는 의미가 아닌, 더 이상 뻗어나갈 수 없는 마지막에 노드가 위치한다는 말이다.안쪽 노드 : 루트를 포함하여 리프를 제외한 노드를 말한다.

해시법은 검색과 더불어 데이터의 추가와 삭제도 효율적으로 수행할 수 있는 방법이다.정렬된 배열에 새로운 값을 추가하려면, 먼저 삽입할 위치를 찾은 후 위치 이후의 값들을 한칸씩 밀고 삽입해야한다.배열의 키 값을 요솟수로 나눈 나머지를 해시 값이라고 하며, 이 해시 값은