티스토리챌린지

병합 정렬   리스트를 균등하게 분할하고, 병합하면서 정렬하는 방법이다. 분할 정복 알고리즘의 대표적 예시 중 하나이다. 합병 정렬이라고도 한다.정렬은 데이터를 크기가 1이 될때까지 분할하고 다시 병합하면서 일어난다. 병합할 때 분할된 왼쪽 부분 리스트와 오른쪽 부분 리스트의 첫번째 값부터 차례대로 읽으면서 작은 값을 임의의 리스트에 넣어 정렬하는 것이다. 그렇게 병합이 된다면, 다시 상위의 부분 리스트와 병합하여 정렬하고, 다시 상위의 부분 리스트와 병합하여 정렬하여 최종적으로 분할된 모든 리스트를 병합하면 정렬이 끝난다. 이때 분할에서 재귀가 사용된다.새로운 리스트를 만들어서 병합 과정에서 사용하기 때문에 별도의 메모리 공간이 필요하고, 각 분할을 재귀로 구현해야하기 때문에 스택 메모리도 많이 사용한..

삽입 정렬  차례에 해당하는 수를 앞쪽 올바른 자리에 삽입하는 정렬 방식이다. 이미 정렬되어 있다면 정렬된 것을 확인하고 정렬이 종료된다는 장점이 있다.정렬은 두번째 자리의 값부터 확인한다. 두번째 자리의 값의 바로 앞 값이 자신보다 크다면 그 값을 교환한다. 그 후 세번째 자리의 값을 선택하여 자신의 앞의 값과 비교하고 자신보다 크다면 교환한다. 만약 교환되었다면 다시 자신의 앞의 값과 비교하고, 크다면 교환한다. 이를 끝까지 반복하면 정렬이 완료된다.따라서 만약 자신의 앞의 값이 자신보다 작다는 것이 확인된다면 정렬되어 있다는 뜻이기 때문에 따로 교환이 일어나지 않고 넘어간다. 즉 이미 정렬되어 있다면 모든 값이 정렬되어 있다는 것을 확인하고 정렬 알고리즘이 종료되기 때문에 버블 정렬, 선택 정렬이 ..

선택 정렬  작은 수를 선택해서 앞쪽에 배치하는 정렬 방식이라 선택 정렬이다. 효율적이지는 않지만, 버블 정렬과 함께 구현이 쉽고, 가장 쉽게 생각할 수 있는 정렬 방식이다.정렬은 가장 앞 수를 선택한 후 자신보다 작은 수가 나오면 교환하는 방식으로 진행된다. 끝의 수까지 비교하고, 작을 때 교환했다면 가장 앞에는 리스트에서 가장 작은 수가 올 것이다. 이제 두번째 수를 선택하고 다시 비교, 교환하고, 그 후에는 세번째 수를 선택하고, ... 반복하여 마지막 수 직전에 도달하면 모든 수가 정렬된다. 예시 예를 들어 위와 같은 리스트를 정렬한다고 해보자.먼저 위와 같이 가장 앞을 선택하고 그 다음 수와 비교한다. 선택된 수인 9가 비교 대상인 2보다 크다.그러므로 두 수를 바꿔준다. 그 후 아래와 같이 다..

버블 정렬  정렬할 때 큰 수를 뒤로 미루는 것 때문에 거품이 올라오는 것 같아 이름 붙여진 정렬 방식이다. 효율적이지는 않지만, 구현이 쉽고, 가장 쉽게 생각할 수 있는 정렬 방식이다.정렬은 인접한 두 수를 선택한 후 비교하고, 큰 수가 앞에 있다면 두 수를 교환하는 방식이 반복되며 일어난다. 첫번째 수와 두번째 수를 선택한 후 비교, 교환하고, 두번째 수와 세번째 수를 선택한 후 비교, 교환하고, ... 반복하여 마지막 수에 도달한다면 가장 큰 수가 가장 마지막 자리에 도달하게 된다.이제 다시 첫번째 수와 두번째 수를 선택한 후 비교, 교환하고, 두번째 수와 세번째 수를 선택한 후 비교, 교환하고, .. 반복하여 마지막 수 앞 칸에 도달하면 뒤 두 수가 정렬된다. 앞선 정렬을 통해 마지막 수가 정렬되..

행렬표현 일반적으로 $ n $ 차원 벡터공간 $ V $ 에서 $ m $ 차원 벡터공간 $ W $ 의 선형변환을 행렬변환으로 나타낼 수 있고, 이는 좌표벡터를 통해 확인해볼 수 있다.$ n $ 차원 벡터공간 $ V $ 의 순서 기저를 $ S = \{ \mathbf{x_1}, \mathbf{x_2}, \cdots, \mathbf{x_n} \} $ 이라 하고, $ m $ 차원 벡터공간 $ W $ 의 순서 기저를 $ R = \{ \mathbf{y_1}, \mathbf{y_2}, \cdots, \mathbf{y_m} \} $ 이라 하며, $ T: V \to W $ 를 선형변환이라 하자. $ \mathbf{x_i} \in S $ $(i = 1, 2, \cdots, n) $ 에 대하여 $ T(\mathbf{x_i})..

선형변환 벡터공간 $ V $ 의 각 벡터 $ \mathbf{v} $ 를 벡터공간 $ W $ 의 벡터 $ \mathbf{w} $ 에 대응시키는 함수를 $ T $ 라 하면 이를 다음과 같이 나타낸다.$$ T : V \to W $$이때 $ \mathbf{w} $ 를 $ T $ 에 의한 $ \mathbf{v} $ 의 상(image)이라 하고 $ \mathbf{w} = T(\mathbf{v}) $ 로 나타낸다. 그리고 $ V $ 를 $ T $ 의 정의역(domain)이라 한다.만약 이 $ T $ 가 다음 조건을 만족하면 $ T $ 를 선형변환이라 한다.모든 $ \mathbf{v_1} , \mathbf{v_2} \in V $ 에 대하여 $ T(\mathbf{v_1} + \mathbf{v_2}) = T(\mathbf..

예외 모든 프로그래밍 코드는 오류가 발생할 가능성이 있다. 그냥 실수로 오타를 낼 수도 있고, 잘 모르고 문법에 안 맞게 코드를 짤 수도 있으며, 예상하지 못한 값이 들어오며 오류가 발생할 수도 있다. 이러한 오류는 Throwable 클래스(참고 링크)의 하위 Error 클래스(참고 링크)와 Exception 클래스(참고 링크)에 정의되어 있다.오류(error)는 메모리 부족(OutOfMemoryError), 스택오버플로우(StackOverFlowError)처럼 JVM이나 하드웨어 등 시스템의 문제로 발생하는 것이다. 그러므로 개발자가 다루기 힘들고, Error가 발생하면 프로그램은 종료된다.그러나 예외(exception)는 발생하자마자 프로그램을 종료하지 않는다. 즉 개발자가 예외를 처리할 수 있다. ..

곡선적합 특정 실험을 통해 측정값을 얻었다면 이를 설명하는 함수를 구할 수 있다. 즉 $ (x_0, y_0) $, $(x_1, y_1) $, $ \cdots $, $(x_n, y_n) $ 과 같은 자료가 주어졌을 때 이 모든 점을 지나면서 이를 대표하는 곡선, 혹은 함수식 $ y = f(x) $ 을 찾을 수 있는데, 이를 곡선적합이라 한다.$$ y = f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^{n-1} $$위와 같은 $ n $ 차 다항식에 대하여 점 $ (x_i, y_i ) $ 가 곡선 $ y = f(x) $ 위에 있다 가정하면, $ f(x_i) = y_i $ 이다. 이를 $ n + 1 $ 개의 미지수 $ a_0, a_1, \cdots, a_n $ 를 가진 선형방..

정규직교집합 내적공간의 원소 $ \mathbf{x} $ 와 $\mathbf{y} $ 에 대하여 $ \left = 0 $ 일 때 두 벡터가 직교한다고 정의하였다. 만약 $ V $ 가 내적공간일 때 $ \mathbf{x_1}, \mathbf{x_2}, \cdots, \mathbf{x_n} \in V $ 에 대하여 $ S = \{ \mathbf{x_1}, \mathbf{x_2}, \cdots, \mathbf{x_n} \} $ 을 가정하자. 이때 $ S $ 의 서로 다른 두 벡터가 모두 직교한다면 $ S $ 를 직교집합(orthogonal set)이라 한다. 또한 직교집합 $ S $ 의 벡터가 모두 단위벡터이면 $ S $ 를 정규직교집합이라 한다.즉 다음이 정의된다.$ S \text{ } \text{ is or..

인터페이스 인터페이스란 기본적으로 코드 수행부가 없는 추상 메소드로 구성된 것이다. 상속 가능한 추상 클래스와 유사하지만, 추상 메소드만 선언되어 있다는 점, 이 때문에 상속과 같이 클래스에 구현(일종의 상속)이 가능하고 이를 통해 다중 상속이 불가능한 자바에서 인터페이스를 통한 일종의 다중 상속이 가능하다는 점이 특징이다. 이를 통해 다형성과 유연성에 이점을 가진다.기본적인 선언 문법은 아래와 같다.access_modifier interface Name { abstract public return_type method_name(parameter); ...}이때 인터페이스에 포함되는 추상 메소드는 자동으로 abstract와 public의 속성을 가지며, 따라서 생략할 수 있다.앞서 말한 바와 ..