전체 글

Heap Sort

What is Heap? 최대값이나 최소값을 찾아내는 연산을 빠르게 찾아내기 위해 고안된, 완전이진트리 를 기본으로 한 자료구조이다. 완전이진트리는 노드의 맨 마지막 리프 부분을 제외하고는 모든 level이 완전하게 채워져 있으며, 가능하면 왼쪽부터 채워진 구조이다. 그리고 Heap에는 Min-Heap과 Max-Heap이 있다. Min-Heap은 부모 노드에 자신보다 작은 값을 둬서 트리의 루트에는 가장 작은 값이 오게 한다. 반대로 Max-Heap은 부모 노드에 자신보다 큰 값을 둬서 트리의 루트에는 가장 큰 값이 오게 한다. Min-Heap에 대해서 알면 Max-Heap의 구현도 간단해지니 Min-Heap을 한 번 살펴보자. Min-Heap에 노드 삽입하기 우선 완전이진트리의 맨 끝에 추가한다. 추가..

Insertion Sort

Insertion Sort 개념 마치 손에서 카드 놀이를 하는 듯한 간단한 정렬 Algorithm이다. Insertion Sort에서 배열은 정렬된 부분과 정렬되지 않은 부분으로 나누어서 본다. 정렬되지 않은 부분에서 값을 하나씩 꺼내와서, 정렬된 부분에서 해당 값이 있을 수 있는 올바른 위치에 배치한다. 배열의 길이가 n인 배열을 오름차순으로 정렬하기 위한 세부적인 작동은 다음과 같다. arr[1]부터 arr[n]까지 반복 꺼내온 값(key)과 정렬된 부분 배열의 값들을 뒤쪽부터 차례대로 비교 key 값이 비교 대상보다 작은 경우, 정렬된 부분에서의 보다 앞의 값들과 계속해서 비교 Java 구현 class InsertionSort { void sort(int arr[]) { int n = arr.len..

Selection Sort

Selection Sort 개념 배열을 돌면서 가장 작은 값을 찾아내면서 맨 앞으로 옮기는 정렬 방식이다. 초기의 가장 작은 값은 시작값으로 지정하고, 배열을 loop하면서 보다 작은 값이 있으면 가장 작은 값으로 지정한다. 그리고 찾아낸 가장 작은 값을 배열의 맨 앞 요소와 교체해준다. 이런 식으로 배열의 길이만큼 반복하며 정렬해준다. 가장 작은 값을 찾아내기 위한 배열 내 loop를 다시 배열의 길이만큼 찾아내야 하기 때문에 O(n²) 의 시간복잡도를 가진다. 한 번 배열을 돌 때마다 정렬해야 하는 요소도 하나씩 줄어들지만, 그래도 square의 절반의 면적이 나오기 때문에 O(n²) 시간복잡도를 가진다고 말한다. Java로 구현하기 public class Test { public static voi..

Bubble Sort

Bubble Sort 개념 앞에서부터 2개씩, 인접한 요소들끼리 비교해서 작은 값을 앞으로, 큰 값을 뒤로 배치한다. (맨 뒤에서부터 시작하는 것도 가능하다.) 이 작업을 배열의 끝까지 도달하면서 정렬하는 방법이다. 그렇게 한번 배열의 끝까지 도달하는 과정을 거쳤다면 해당 배열의 맨 마지막 요소는 해당 배열에서 가장 큰 값이 된다. 한번 loop를 돌 때마다 끝 쪽에 요소 하나씩은 정해지니, 하나씩 비교하는 loop 자체를 배열의 길이만큼 돌려야 한다. 배열 내 요소의 갯수만큼 반복하는 작업을 다시 배열 내 요소의 갯수만큼 순회하게 되니 이 작업은 O(n²) 의 시간복잡도를 가진다. 물론 인접 요소끼리 비교하는 loop를 한번 돌 때마다 비교해야 하는 요소가 하나씩 빠지기는 하지만, 결국 square에서..

Hash Table에 대해 알아보고 Java로 구현해보기

Hash Table의 간단한 활용 사례 만약 어떤 사람이 유튜브 영상을 불법 복제하여 자기 계정으로 업로드를 시도하게 되면, 유튜브는 '중복되는 동영상'이라며 거절하게 된다. 전 세계 유튜브 동영상이 얼마나 많은데 이런 작업이 가능한걸까? 바로 Hash Table이 이와 같은 문제를 해결해주는 것이다. Hash Table의 작동 원리 F(key) → Hash Code → Index → Value 우선 검색하고자 하는 key 값을 입력받아서, 해쉬 함수를 돌려 Hash Code를 얻어낸다. 이 Hash Code를 배열의 Index로 환산해서 데이터에 접근하는 방식의 자료구조이다. 여기서 key 값은 숫자나 문자열, 혹은 File이 될 수도 있다. 그리고 해쉬 함수는, 특정한 규칙을 이용해서 입력받은 key..

Algorithm 핵심 개념들

Algorithm은 '문제를 어떤 식으로 푸는 것이 최선인가' 로 정의될 수 있다. Time Complexity Algorithm 문제들을 풀 때는 문제에 대한 해답을 찾는 것도 중요하지만 '더 효율적인 방법은 없을까?'에 대한 고민도 중요하다. 효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것과 같다. 그리고 시간 복잡도를 고려한다는 것은 한 문장으로 정리하자면 다음과 같다. 입력값의 증가 및 감소에 따라 시간이 얼마만큼 비례하여 증가 및 감소하는가? Big-O 표기법 시간 복잡도를 표기하는 방법 중에는 다음과 같은 방법들이 있다. Big-O Big-Ω Big-θ 위 표기법들은 각각 최악, 최선, 평균의 경우 입력값의 증가에 따라 시간 복잡도가 얼마나 증가하는지 표기하는 방법들이다. 이 중에..

Data Structure 핵심 개념들

"자료 구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것" 데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다. 우리의 이름, 나이, 키, 집 주소, 목소리 혹은 유전자 DNA까지 데이터로 분류할 수 있다. 그러나 데이터는 그 자체만으로 어떤 정보를 가지기 힘들다. 예를 들어 나이라는 데이터만 알고 있다면, 사람의 나이인지 나무의 나이인지 알 수 없다. 이처럼 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다. 뿐만 아니라 데이터를 사용하려는 목적에 따라 형태를 구분하고, 분류하여 사용할 수 있다. 전화번호부를 작성할 때, 숫자를 3개 또는 4개씩 묶음짓고 하이픈(-)으로 합친다. 이 숫자의 묶음에 이름을 붙여 보관해야 한다면, 해당 데이터를 꺼낼..

AOP의 간단한 개념들

AOP는 흩어진 Aspect를 모듈화할 수 있는 프로그래밍 기법이다. 클래스들이 비슷한 메소드, 필드, 코드 등을 사용하고 있다면, 개발자가 한 클래스를 수정하려고 할 때 연관된 모든 클래스를 찾아가서 또다시 수정을 진행해야 할 것이다. 이렇듯, 클래스마다 겹치고 반복되는 코드를 Crosscutting Concerns(흩어진 관심사) 라고 부른다. 이는 AOP를 활용해서 해결해야 한다. 위 이미지를 보면 흩어져 있는 부분들을 Aspect를 활용해서 모듈화한 모습을 볼 수 있다. 이처럼 모듈화한 Aspect를 클래스의 어떤 곳에서 사용해야 하는지 정의해주면 된다. 결론적으로, Aspect를 모듈화하고 핵심적인 비즈니스 로직에서 분리하여 재사용하겠다는 것이 AOP이다. 주요 개념 Aspect : 모듈화한 클..

Spring Boot 핵심 개념들

Spring Boot 주요 어노테이션 @SpringBootApplication : @Configuration, @EnableAutoConfiguration, @ComponentScan 등의 어노테이션을 합친 것으로, 주로 메인 클래스 위에서 사용 @EnableAutoConfiguration : 미리 설정해놓은 Java 설정 파일들을 빈으로 등록 @ComponentScan : @Component 어노테이션이 붙어있는 클래스들을 찾아서 빈으로 등록 @Component : 선언된 클래스를 빈으로 등록 @Controller : Spring MVC의 Controller로 사용되는 클래스 선언 @GetMapping, @PostMapping, @PutMapping, @DeleteMapping, @PatchMappin..