클래스 내에 선언되는 클래스. 두 클래스가 서로 긴밀한 관계에 있을 때 주로 사용한다.

class Outer{
    ...
    class Inner{
        ...
    }
    ...
}

내부 클래스의 장점

• 내부 클래스에서 외부 클래스 멤버들에 쉽게 접근 가능하다.
• 캡슐화를 통해 코드 복잡성을 줄일 수 있다.

내부 클래스의 종류

인스턴트 클래스 vs 스태틱 클래스

내부 클래스 중 스태틱 클래스만이 static 멤버를 가질 수 있다.
final static 멤버는 상수이기 때문에 모든 종류의 내부 클래스에서 사용 가능하다.

인스턴스 클래스는 외부 클래스의 인스턴스멤버를 객체생성 없이 바로 사용 가능하다. 스태틱 클래스는 외부 클래스의 인스턴스멤버를 객체생성 없이 사용 불가능하다.

다른 클래스에서의 내부 클래스 접근

외부 클래스가 아닌 다른 클래스에서 내부 클래스를 생성하고 내부 클래스에 접근할 수도 있다. 그러나 이런 경우가 발생한다면 내부 클래스로 선언하면 안 되는 클래스를 내부 클래스로 선언했다는 것을 뜻한다.

Spring에서의 내부 클래스?

이 글을 쓰게 된 주 원인이 다음 코드다. "hello-api"라는 get 요청에 대해 hello 객체를 response로 리턴해주고 있다. (이는 Jackson 등의 라이브러리를 통해 json 형태로 클라이언트에게 전송된다.)
Controller의 내부 클래스로 작성된 Hello 클래스는 static 클래스다. 나는 여기서 3가지 의문이 들었다.

• 내부에 static 멤버도 없는데 왜 Hello 클래스는 인스턴스가 아닌 스태틱 내부 클래스로 작성되었는가? 실제로 static 키워드를 지우고 실행해도 아무 문제가 없었다.
• static 내부 클래스인데, 왜 Hello 객체 생성 없이 Hello.setName()을 한다면 오류가 발생할까?
• 기껏 Hello 클래스를 static으로 선언하였으면서, helloApi 메소드에서는 왜 hello라는 객체를 만드는 것일까?

공부 결과 그 답은 다음과 같았다.

1번 질문에 대한 답변

• 내부 클래스에서 외부 클래스의 인스턴스를 쓰지 않는다면, 내부 클래스는 static으로 만드는 것이 좋다. 예시 코드에서 내부 클래스 Hello는 외부 클래스 HelloController의 멤버를 전혀 쓰지 않고 있다. 이럴 때 내부 클래스를 static으로 만드는 것이 좋은 이유는, '메모리 누수' 때문이다.
• 메모리 누수에 대해서, static 내부 클래스는 '자신의 인스턴스'와 '자신의 기본 생성자'에 대한 정보만을 가지지만, 인스턴스 내부 클래스는 '바깥 클래스 참조'까지 가지게 되며, '바깥 클래스 참조'가 메모리 누수의 원인이 된다.
• 인스턴스 내부 클래스는, 외부 클래스가 더 이상 사용되지 않더라도 그에 대한 참조가 존재하기 때문에 GC가 수행될 수 없다. 이에 따라 메모리 누수가 발생하며, 따라서 외부 클래스의 멤버를 사용하지 않는 내부 클래스의 경우 인스턴스가 아닌 static으로 선언하는 것이 바람직하다.
• 결론: 내부 클래스가 바깥 클래스와 독립적으로 작동한다면 내부 클래스를 static으로 정의하자.

2번 질문에 대한 답변 Hello 클래스는 static이지만, setName 메소드는 static이 아니다. 따라서 Hello 클래스의 인스턴스 객체가 요구된다. 만약 setName 메소드 역시 static이라면

Hello.setName(name);

과 같이 사용이 가능할 것이다.

3번 질문에 대한 답변 controller에서는 결국 mapping으로 받은 request에 대한 response를 리턴해주어야 한다. 그 리턴을 객체로 하기 위해서는 결국 클래스의 객체 생성은 필수적이다.

Model + View + Controller로 어플리케이션을 구분하는 디자인 패턴.
각 역할을 논리적으로 나눔으로써 유지보수가 쉬워지고 코드의 가독성이 높아진다.

Model

비즈니스 로직을 담당한다. DB와 연동하여 사용자가 입력한 데이터를 입력하거나, 사용자에게 출력할 데이터를 관리한다.

View

사용자 인터페이스를 담당한다. 즉 사용자의 입/출력을 관리한다.

Controller

Model과 View는 서로에 대한 정보가 없기 때문에 이 둘을 Controller가 중재한다. 즉 사용자의 요청을 Model을 통해 처리하고, 해당 결과를 View로 전달한다.

MVC의 규칙

• Model은 Controller와 View에 의존하지 않아야 한다. 즉 Model 내부에 Controller와 View에 관련된 코드가 있으면 안된다.
• View는 Model에만 의존해야 하고, Controller에 의존하면 안된다. 즉 View 내부에 Model의 코드만 있으며 Controller의 코드가 있으면 안된다.
• View가 Model로붜 데이터를 받을 때는, 사용자마다 다르게 보여주어야 하는 데이터에 대해서만 받아야한다. (동적 리소스)
• Controller는 Model과 View에 의존해도 된다. 즉 Controller 내부에는 Model과 View의 코드가 있어도 된다.
• View가 Model로부터 데이터를 받을 때는 Controller를 통해서 받아야 한다.

웹 어플리케이션은 크게 다음 2가지 과정으로 생성된다.

1. 서비스 제공에 필요한 데이터를 수집, 분석, 처리하고 사용자가 원하는 형태의 데이터를 가공한다.
2. 가공한 데이터를 사용자와 상호작용할 수 있도록 클라이언트, 즉 사용자의 웹브라우저에 보여준다.

   비즈니스 로직

   위 과정 중 1번 과정이 비즈니스 로직이다. 간단히 말하면, 어플리케이션이 어떤 일을 하는지를 말한다. 구체적으로, 하나의 프로젝트에서 데이터베이스와 사용자 인터페이스 사이의 정보 가공 및 교환을 처리하는 알고리즘을 의미한다. 웹 어플리케이션에서는 일반적으로 DB에 연결을 하고 서 데이터를 가져와서 적절한 가공을 한 후 페이지를 구성하고 사용자에게 페이지를 보여주는 등의 일련의 과정을 거친다. 이 때 가져온 데이터를 사용자가 원하는 데이터로 적절한 가공을 하는 과정이 비즈니스 로직이다.

사용자 인터페이스

위 과정 중 2번 과정이 사용자 인터페이스다. 비즈니스 로직에서 가공한 데이터를 사용자와 어플리케이션이 상호작용 할 수 있도록 하는 과정이다.

예를 들어, 지도에서 주변 맛집 위치를 알려주는 서비스가 있다면,

1. 사용자의 위치 정보를 입력받고, 해당 위치 기반으로 주변 가게들의 데이터를 얻어온 후, 평점별로 정렬하고 추천 알고리즘을 통해 적절한 가게를 도출하는 것이 비즈니스 로직이다.
2. 이후 도출된 가게들을 클라이언트, 즉 사용자 화면으로 구성하고 디자인하는 것이 사용자 인터페이스다. 단순히 생각하면 비즈니스 로직 == 백엔드, 사용자 인터페이스 == 프론트엔드 위주의 작업이라고 생각할 수 있다.

HyperText Transfer Protocol. 인터넷에서 데이터를 주고받을 수 있도록 하는 프로토콜. Application Layer 에 해당한다. HTTP는 클라이언트-서버 관계에서 다음과 같이 동작한다. 요청(request): client -> server 응답(reply): server -> client

이 과정에서 서버와 클라이언트 간에는 HTML, JSON, XML 등의 정보 파일이 교환된다.

HTTP의 특징

• 일반적으로 HTTP는 reliable transport를 지향하며 따라서 TCP/IP를 기반으로 한다.
• HTTP는 일반적으로 connectionless다. 즉, 클라이언트와 서버의 1회 연결 후, 클라이언트의 요청에 대한 서버의 응답이 완료되면 연결을 끊어버린다. 이로 인한 장단점은 다음과 같다.
  • HTTP는 인터넷에서 불특정 다수의 통신 환경을 지원하다. 만약 서버에서 특정 클라이언트들과의 연결을 지속한다면 이에 따라 많은 리소스 및 오버헤드가 발생한다.
  • 따라서 연결을 유지하기 위한 리소스를 줄여 더 많은 연결을 지원하기 위해 비연결적 특징을 가진다.
  • 그러나 서버와 클라이언트의 연결이 매번 끊어지는 특성으로 인해 서버는 클라이언트의 상태를 모르는, stateless가 된다.
  • 따라서 동일한 클라이언트의 모든 요청에 대해 매번 새로운 연결을 생성해야하는 오버헤드가 발생한다.
  • HTTP 1.1부터는 위의 문제점 해결을 위해 Keep-Alive 기능을 제공한다.
• connectionless는 자연스럽게 stateless로 이어진다. 따라서 서버는 클라이언트의 상태를 기억할 수 없으며, 다음과 같은 일이 발생할 것이다.

  쇼핑몰 사이트 접속 -> 로그인 -> 상품 클릭 -> 로그인 -> 주문 -> 로그인 -> ,,,

• 사용자 정보를 기억하지 못하고 위와 같이 매번 로그인을 해야한다면 매우 불편할 것이다. 이를 위한 해결법은 다음과 같다.
  • 쿠키: HTTP 헤더에 set-cookie를 설정하여 클라이언트가 쿠키를 유지하고, 서버가 이를 활용하는 방법.
  • 세션: 쿠키는 클라이언트에 저장되기 때문에 보안에 취약하다. 세션은 서버단에서 정보를 저장한다. 그러나 세션 역시 정보 탈취의 위험이 있으며 서버에 사용자의 정보를 저장하기 때문에 서버의 메모리를 차지하고 이는 곧 오버헤드로 이어질 수 있다.
  • 토큰: OAuth, JWT. 보호 대상의 데이터를 그대로 저장하는 것이 아닌, 토큰으로 치환하여 저장한다. 정보 탈취를 당하더라도 토큰으로부터 데이터를 얻을 수 없어 보안성이 높다.

HTTP의 버전

HTTP 1.0

• Connectionless. 따라서 동일한 클라이언트라도 새로운 요청에 대해 매번 새로운 연결(3-way handshake)을 생성해야 한다.
• 요청 / 응답에 대한 메타 데이터를 포함한 헤더 필드 제공 (Status Code, Content-Type 등)
• Method: Get, Head, Post

HTTP 1.1

• Keep Alive: 동일한 클라이언트의 요청마다 매번 3-way handshake가 요구된다면 이는 오버헤드를 유발한다. 이를 해결하는 것이 Keep-Alive다. 정해진 시간 또는 횟수만큼 연결을 유지하며, Htpp 헤더를 통해 설정할 수 있다.
• 그러나 Keep Alive가 항상 좋은 것은 아니다. 위에서 언급했듯, 연결을 지속하는 것 역시 오버헤드가 되며 사용자가 많다면 연결이 많아져 새로운 사용자를 수용하지 못할 위험도 있다.
• Pipelining: 기존의 HTTP 1.0의 경우, 요청에 대한 응답을 클라이언트가 받아야지만 다음 요청을 할 수 있었다. 따라서 요청 1에 문제가 생긴다면 요청 2, 요청 3 역시 진행되지 못한다. 파이프라이닝은 앞선 요청에 대한 응답이 오기 전에 추가적인 요청을 가능하게 함으로써 각 요청에 대한 각 응답을 개별적으로 받고 처리한다. 이로 인해 응답속도가 높아지고 페이지 뷰의 속도가 빨라진다.
• Host Header: 버츄얼 호스팅을 가능하게 한다. 즉 하나의 IP가 여러 도메인을 보유할 수 있다.
• Method: Get, Head, Post, Put, Delete, Trace, Options

HTTP 2.0

• HTTP 1.1의 클라이언트에서 응답 대기 없이 서버로 요청을 보낸다고 해도, 서버에서는 클라이언트의 요청 순서대로 응답을 해야한다. 이로 인해 HOL(Head of Line) 문제가 발생 가능하다. 즉 클라이언트에서 파이프라이닝을 적용했다고 해도 앞선 요청에 대한 처리 및 응답이 지연되면 뒤의 요청에 대한 처리가 지연될 수 있다.
• Multiplexed Streams: HOL blocking을 해결할 수 있다. 하나의 connection으로 동시에 여러 메시지를 주고 받을 수 있다. 따라서 응답 역시 순서에 상관 없이 stream으로 주고 받는다.
• Stream Prioritization: 응답에 대한 우선순위를 설정하여 우선순위가 높은 요청에 대해 먼저 응답한다.

응답 상태 코드

응답 상태 코드 (status code): 클라이언트의 요청에 대한 서버의 응답 (처리) 상태.

• 1xx (정보): 요청을 받았으며 작업을 계속 진행한다.
• 2xx (성공): 요청을 성공적으로 받고 처리하였다.
• 3xx (리다이렉션): 클라이언트는 요청을 마치기 위해 추가적인 작업이 요구된다.
• 4xx (요청 오류): 클라이언트에 오류가 있다. (잘못된 요청 등)
• 5xx (서버 오류): 서버에 오류가 있다. 즉 서버가 요청을 처리하지 못했다.

HTTP Method

• Get: 서버에게 리소스를 요청 (조회)
• Head: Get과 유사하지만, 서버는 body 없이 헤더만을 응답. 즉 헤더의 정보만을 요구할 때 사용
• Put: 서버가 요청의 body를 통해 데이터 추가(최초 1번) 또는 수정을 수행한다.
• Post: 서버가 요청의 body를 통해 데이터를 추가한다. (동일한 데이터의 경우에도 계속 데이터 추가)
• Delete: 서버가 요청받은 리소스를 삭제한다.
• Trace: 클라이언트-서버 사이의 모든 HTTP Application의 요청/응답을 따라가며 메시지의 이상 유무를 확인한다.
• Options: 서버에게 특정 리소스가 어느 메소드를 지원하는지 물어본다.

HTTP 헤더 구성

추후 작성 예정

a, b, c에서 오류가 발생한다. a: 참조형 b의 지네릭 타입 Object와 생성자 Box()의 지네릭 타입 String이 불일치한다. b: a의 문제점 + Object형의 객체를 Box<Object> 타입의 참조변수에 저장 불가하다. c: String만 받을 수 있는 Box<String> 클래스의 setItem(T item) 메소드에 Object를 넣으려 하고 있다.

c, d가 올바른 호출을 하고 있다. a, b: 지네릭 메서드가 요구하는 매개변수와 실제 대입되는 매개변수의 타입이 다르다. d: 지네릭 메서드의 타입 호출은 매개변수에서 유추 가능하기 때문에 생략 가능하다. e: Object는 T extends Fruit의 조건에 부합하지 않기 때문에 불가능하다.

c, d, g 가 틀렸다. c: Box는 지네릭 타입을 Fruit을 상속한 클래스로 한정한다. 따라서 ? 또한 "? extends Object"가 아닌 "? extends Fruit"을 뜻한다. d: Object 과 Fruit 타입 불일치 g:와일드카드 ?는 하나의 참조가 여러 타입의 지네릭 객체를 가리킬 수 있도록 돕는다. 객체의 생성을 하는 new와 같은 연산자에서는 사용 불가하다.

public static <T extends Product> ArrayList<T> merge(
    ArrayList<T> list, ArrayList<T> list2){
        ArrayList<T> newList = new ArrayList<>(list);

        newList.addAll(list2);

        return newList;
}

int i=0;
for (Card.Kind kind: Card.Kind.values()){
    for (Card.Number number: Card.Number.values()){
        cardArr[i++] = new Card(kind, number);
    }
}

이하 애너테이션 공부 후 풀이 예정

Collection(List, Set) 인터페이스에 저장된 데이터에 접근할 때 사용되는 인터페이스다. Iterator가 주로 사용되며, Enumeration은 Iterator의 구버전이다. (기능은 거의 동일하다) Iterator는 next로만 접근 가능하지만, ListIterator는 previous로의 접근도 가능하다. 컬렉션을 구현한 클래스는 LinkedList, ArrayList, HashSet 등 여러 종류가 있는데 이것들을 읽는 방법을 iterator를 통해 표준화하여 모두 동일한 방식으로 읽을 수 있다. ❗️Iterator는 1회성이다. (previous로 못가기 때문에 한번 순회한다면 새로운 iterator가 요구된다.)

hasNext()

컬렉션에 읽어올 요소가 남아있는지 확인한다. 있다면 true, 없다면 false

next()

다음 요소를 읽어 온다. hasNext()를 통해 읽어올 요소가 있다면 next()를 사용하여 다음 요소를 가져올 수 있다.

List list = new ArrayList();
list.add(1); list.add(2); list.add(3);
Iterator it = list.iterator();    //iterator(): Collection 인터페이스에 정의된 함수
while (it.hasNext()){
    System.out.print(it.next()+" ");    //1 2 3
}

Iterator의 사용 이유?

ArrayList를 다음과 같이 순회한다고 가정하자.

List list = new ArrayList();
for (int i=0; i<5; i++)
    list.add(i);    //0,1,2,3,4
for (int i=0; i<5; i++){
    Object obj = list.get(i);
    System.out.println(obj);
}

현재 상태에서는 for문에서의 list.get() 메소드를 사용하여도 List를 순회할 때 문제가 없다. 그러나 데이터를 담던 자료구조를 ArrayList에서 HashSet으로 바꾼다면 다음과 같은 문제점이 나타난다.

Set list = new HashSet();
for (int i=0; i<5; i++)
    list.add(i);    //0,1,2,3,4
/*
HashSet은 ArrayList와 달리 get 메서드를 지원하지 않는다. 에러!
for (int i=0; i<5; i++){
    Object obj = list.get(i);
    System.out.println(obj);
}
*/

그러나 만약 Iterator를 통해 순회하였다면 이러한 문제점을 고려하지 않아도 되며 유지 보수 및 코드의 재사용성이 높아진다.

List list = new ArrayList();
//Set list = new HashSet();
for (int i=0; i<5; i++)
    list.add(i);    //0,1,2,3,4
Iterator it = list.iterator();    //iterator() 메서드는 Collection에서 정의한 메서드이기 때문에 list와 set 모두 지원한다.
while(it.hasNext()){
    System.out.println(it.next());
}

Arrays 클래스는 배열을 다루기 편리한 static 메서드들을 제공한다.

toString(), deepToString()

배열의 내용을 출력해준다. 일차원 배열은 toString(), 다차원 배열의 경우 deepToString()을 사용해야 한다.

//static String toString(Object[] a)
int[] arr = {1,2,3,4};
int[][] arr2D = {{11,12},{21,22}};
System.out.println(Arrays.toString(arr);    //[1, 2, 3, 4]
System.out.println(Arrays.deepToString(arr2D);    //[[11, 12], [13, 14]]

equals(), deepEquals()

두 배열이 동일한지 비교한다. 일차원 배열은 equals(), 다차원 배열의 경우 deepEquals()를 사용해야 한다.

int[] arr = {0,1,2};
int[] arr2 = {0,1,2};
Arrays.equals(arr,arr2);    //true
int[][] arr2D = {{0,1},{1,2}};
int[][] arr2D2 = {{0,1},{1,2}};
Arrays.deepEquals(arr2D,arr2D2);    //true

copyOf(), copyOfRange()

배열의 복사를 한다. copyOf는 해당 배열을 설정한 길이만큼 복사하며, copyOfRange는 해당 배열을 설정한 범위만큼 복사한다.

int[] arr = {1,2,3,4};                //1,2,3,4
int[] arr2 = Arrays.copyOf(arr,2);    //1,2
//copyOfRange 시 기존 배열의 초과 범위는 0으로 채움
int[] arr3 = Arrays.copyOfRange(arr,1,5)    //2,3,4,0

fill(), setAll()

배열을 채운다. fill은 배열의 전체를 해당 값으로 채우고, setAll은 람다를 사용하여 배열 원소를 하나하나 채운다.

int[] arr = new int[5];
Arrays.fill(arr,3);    //3,3,3,3,3
//setAll 두번째 인자로 람다 사용 및 난수로 채우기
Arrays.setAll(arr,(i)->(int)(Math.random()*5)+1);

sort()

배열을 정렬한다. 정렬의 기준에 대해서는 다음 참조. Comparator과 Comparable

binarySearch()

배열을 이분탐색한다. 이분탐색이기 때문에 정렬된 상태에서 사용해야 하며, 그렇지 않을 시 이상한 값이 나온다.

int[] arr = {6,3,8,10,1};
Arrays.sort(arr);    //1,3,6,8,10
Arrays.binarySearch(arr,6);    //idx=2

asList()

배열을 List로 변환한다. 🚫이 때 반환된 List는 읽기 전용이다. 따라서 만약 수정하고 싶다면 ArrayList 등의 생성자를 활용해야 한다.

int[] arr = {1,2,3,4};
List list = Arrays.asList(arr);
//list.add(5);    //수정 불가
List list2 = new ArrayList(Arrays.asList(arr));
list2.add(5);

• String 클래스는 char[] 데이터와 관련 메서드로 구성된다.
• 내용을 변경할 수 없는 불변(immutable) 클래스다. 따라서 만약 String을 편집하거나 두 개를 합치는 등을 통해 문자열이 달라지면, 새로운 객체가 생성된다.
• 즉 문자열 결합을 할 때마다 계속 새로운 문자열 객체가 생성된다. 따라서 성능이 저하된다. ✅ 문자열의 결합 / 변경이 잦을 때 해결책: StringBuffer

String의 비교

String을 생성하는 방법은 다음 두가지가 있다.

• String str1 = "abc"; String str2 = "abc";
• String str3 = new String("abc"); String str4 = new String("abc");

첫번째 방식은 str1과 str2가 가리키는 객체가 동일하다. 즉 둘 모두 동일한 주소의 "abc"라는 문자열 리터럴을 공유한다. 두번째 방식은 새로운 String 인스턴스를 생성한다. 즉 str3와 str4의 문자열 값 자체는 동일하지만, 두 객체가 가리키는 주소값은 다르다. String 클래스는 불변이기 때문에, 첫번째 방식으로 두 개 이상의 String 클래스가 동일한 문자열 리터럴을 공유하더라도 큰 문제는 없다. 이에 따른 차이는 "==" 연산에서도 나타난다.

• 첫번째 방식으로 생성한 str1과 str2는 주소값 역시 같다. 따라서 == 연산의 결과는 true가 된다.
• 두번째 방식으로 생성한 str3와 str4는 그 값은 같지만 주소값이 다르다. 따라서 == 연산의 결과는 false가 된다.

따라서 String 클래스에서 주소값의 비교가 아닌 실제 문자열 값을 비교하고 싶다면, == 보다는 "equals" 메소드를 사용해야 한다.

    System.out.println(str1 == str2);    //true
    System.out.println(str1.equals(str2));    //true
    System.out.println(str3 == str4);    //false
    System.out.println(str3.equals(str4));    //true        

"compareTo" 메소드 역시 문자열의 비교에 사용할 수 있다. 해당 메소드는, 두 문자열이 같다면 0, 문자열이 사전순으로 더 앞선다면 -1, 뒤에 있다면 1을 반환한다.

    System.out.println("aaa".compareTo("aaa"));    //0
    System.out.println("aaa".compareTo("bbb"));    //-1
    System.out.println("bbb".compareTo("aaa"));    //1

StringBuffer 클래스

• StringBuffer 클래스 역시 char[]형 데이터를 가진다.
• 그러나 String과 달리 내용 변경이 가능하다. (mutable) StringBuffer 역시 고정된 크기의 배열에 문자들이 할당되는 형태다. 따라서 mutable이지만 만약 모든 배열이 다 찬다면, 새로운 배열 공간을 할당하고 기존의 데이터를 옮긴 후 참조를 변경하는 과정이 요구된다. 이는 곧 성능의 오버헤드이기 때문에, 처음 StringBuffer 생성 시 문자열의 길이를 고려한 적절한 크기 할당이 요구된다.

StringBuffer의 변경

앞서 설명했듯 StringBuffer는 내용 변경이 가능하다.

• append()는 지정된 내용을 StringBuffer에 추가 후 StringBuffer(즉 자기자신)의 참조를 반환한다.

  StringBuffer sb = new StringBuffer("abc");    //sb == "abc"
  sb.append("123");    //sb == "abc123"
  StringBuffer sb2 = sb.append("ZZ");    //sb == sb2 == "abc123ZZ"

StringBuffer의 비교

equals가 오버라이딩 되어 있는 String과 달리, StringBuffer는 equals가 오버라이딩 되어 있지 않다. 즉 equals가 문자열의 내용으로 비교하지 않고 주소값으로 비교를 한다. 따라서 두 개의 StringBuffer의 문자열이 동일한지를 비교하기 위해서는 equals를 쓰기 전에 String으로 변환하는 작업이 요구된다.

StringBuffer sb = new StringBuffer("abc");
StringBuffer sb2 = new StringBuffer("abc");
System.out.println(sb == sb2);    //주소 비교 -> false;
System.out.println(sb.equals(sb2));    //주소 비교 -> false;
String s = sb.toString();
String s2 = sb2.toString();
System.out.println(s.equals(s2));    //값 비교 -> true;

StringBuilder

StringBuffer는 동기화되어 있기 때문에 멀티스레드 환경에서 안전하다. 그러나 동기화는 곧 성능 저하이기 때문에 싱글스레드 환경에서는 동기화가 없는 StringBuilder를 사용하면 더 나은 성능이 가능하다.

프로그램에서 일시적으로 사용되고 재사용되지 않는 객체에 대해서, 클래스를 모두 만들어준다면 코드가 복잡해지고 오히려 유지보수에 불리해질 수 있다. 따라서 이러한 경우 클래스를 별도로 만들어주지 않고 코드 내에서 익명클래스를 생성 및 정의하여 일회성으로 사용한다.

구현 방법: 익명 자식객체

public class Basic{
    void print(){
        System.out.println("First Print");        
    }
}

public class Anony{
    Basic tuning = new Basic(){
        String mode = "tuning";

        void print(){
            System.out.println("Tuning Print");
        }

        void print2(){
            System.out.println("Mode is"+mode);
        }
    };
    //Basic형 변수 tuning에 익명 자식 객체를 담는다.
    //mode와 print2()는 자식 객체 내에서는 사용될 수 있지만, 변수가 부모타입의 클래스이기 때문에 외부에서 사용 불가하다.
}

구현 방법: 익명 구현객체

부모클래스를 상속한 익명 자식객체와 달리, 인터페이스를 구현하여 익명 클래스를 생성하는 것도 가능하다. 일반적인 상속과 달리 인터페이스는 무조건 메서드들을 구현해야 하기 때문에 규격화에 도움이 된다.

public class Button{
    interface ListenerInterface{
        void onClick();
    }
    ListenerInterface listener;

    void setListenerInterface(ListenerInterface listener){
        this.listener = listener;
    }

    void touch(){
        listener.onClick();
    }
}  

public class ButtonHandler{
    Button firstBtn = new Button();
    Button secondBtn = new Button();

    //인터페이스를 구현한 익명 객체
    Button.OnClickListener listener = new Button.OnClickListener(){
            @Override
            public void onClick(){
                System.out.println("second Button");
            }
    }

    secondBtn.setListenerInterface(listener);
    //매개변수로 익명 객체 바로 생성
    firstBtn.setListenerInterface(new Button.OnClickListener(){
        @Override
        public void onClick(){
            System.out.println("first Button");
        }    
    });
}

그래프 자료구조에서, 모든 노드에 대해 다른 노드로의 최단 경로를 구하는 알고리즘. 다이나믹 프로그래밍의 일종이다.

방법?

다음과 같은 그래프가 있다고 가정하자.

각 노드에 대해 다른 노드로의 직선 비용은 다음과 같다.

다른 노드를 거치지 않고 바로 목적지 노드로 가기 위해서는 위 표의 비용이 소비된다. 이제 모든 노드에 대해 최소 비용 경로를 알기 위해 표를 갱신해야 한다. 비교 기준은 다음과 같다. 노드1에서 노드2로 가는 현재 최소 비용 VS 노드1에서 노드3으로 가는 비용 + 노드3에서 노드2로 가는 비용

• 노드 1을 거쳐가는 경우 노드 1을 거쳐서 다른 노드로 가는 경우가 더 빠르다면 해당 경우로 최소 비용을 교체한다. 그 결과는 다음과 같다.

• 노드 2를 거쳐가는 경우 노드 1을 거쳐가는 경우를 계산한 결과 표에서, 노드 2를 거쳐가는 경우로 동일한 작업을 수행한다. 그 결과는 다음과 같다.

• 노드 3를 거쳐가는 경우 노드 1과 2를 거쳐가는 경우를 계산한 결과 표에서, 노드 3을 거쳐가는 경우로 동일한 작업을 수행한다. 그 결과는 다음과 같다.

• 노드 4를 거쳐가는 경우 마지막으로 노드 4를 거쳐가는 경우를 계산한다. 그 결과는 다음과 같다.

추천 문제

프로그래머스 - 순위

파생 클래스에서 재정의할 것으로 기대하는 멤버 함수.

정적 바인딩

일반적으로 C++ 컴파일러는 함수 호출 시 어느 블록의 함수인지, 해당 함수의 메모리 상 위치 등의 정보를 요구한다. 함수 호출 코드로부터 이러한 정보를 해석하는 것을 바인딩(binding)이라 한다. 대부분의 함수 호출은 컴파일 타임에 고정된 메모리 주소로 변환된다. 이를 정적 바인딩이라 한다.

동적 바인딩

그러나 컴파일 타임에 바인딩 정보를 모르는 경우가 있다. 이럴 때 사용하는 것이 동적 바인딩이다. 가상 함수를 사용할 때 결합 타입이 분명하다면 정적 바인딩을 사용하지만, 기초(부모) 클래스 타입의 포인터 또는 참조를 통하여 호출할 때는 해당 포인터의 실제 객체 정보를 컴파일 타임에는 모르기 때문에 동적 바인딩을 사용한다.

class Parent{
public:
    virtual void Print() {cout << "A 함수\n";
};

class Child : public Parent{
    virtual void Print() {cout << "B 함수\n";
};

int main(){
    Parent* ptr;
    Parent p;
    Child c;
    ptr = &obj_a;
    ptr->Print();
    ptr = &obj_b;
    ptr->Print();
    return 0;
}

실행 결과

A 함수
B 함수

만약 가상함수가 아니라면 정적 바인딩을 사용하게 되고, 따라서 ptr이 c를 가리킴에도 불구하고 기존에 바인딩되었던 parent의 print()함수를 호출하게 된다. 가상 함수를 사용함으로써 포인터의 타입이 아닌 포인터가 실제 가리키는 객체의 타입에 따라 멤버 함수를 선택한다 (동적 바인딩).

가상 함수의 단점

가상 함수 실행 시 C++ 프로그램은 가상 함수 테이블을 통해 적합한 함수의 주소를 호출한다. 따라서 정적 바인딩에 비해 함수의 호출 과정이 복잡해지기 때문에 메모리와 실행 속도에서 약간의 부담을 가진다.

순수 가상 함수

가상 함수는 반드시 재정의해야 하는 함수가 아닌, 재정의가 가능한 함수다. 반면 순수 가상 함수는 반드시 재정의해야하는 함수다. 함수의 내용에 대한 정의, 즉 본체가 없기 때문에 재정의하지 않으면 사용할 수 없다.

virtual func()=0;

추상 클래스

하나 이상의 순수 가상 함수를 포함하고 있는 클래스다. 추상 클래스는 순수 가상 함수를 포함하기 때문에 인스턴스의 생성이 불가하다. 즉 상속을 통해 파생 클래스를 정의하고, 이후 파생 클래스에서 순수 가상 함수를 오버라이딩 한 후에 파생 클래스의 인스턴스 생성이 가능하다. ❗️추상 클래스 타입의 포인터 및 참조는 바로 사용 가능하다.

참고: TCP스쿨

인라인 함수

함수의 모든 코드를 호출된 자리에 바로 삽입하는 방식의 함수. 따라서 함수 호출에 걸리는 시간이 단축된다. ❗️인라인 함수는 재귀 호출이 허용되지 않는다.

인라인 함수 예시

inline int func(int a, int b) { return a+b; }

int main(){
    cout << func(3,5);
    return 0;
}

매크로 함수와의 차이점?

매크로 함수는 단순 치환이다.예를 들어 #define fun(x) (x*x) 라는 매크로 함수를

x=2;
fun(x+5);

로 실행한다면, 7*7=49의 결과가 나오는 것이 아닌,2+5*2+5=17의 결과가 나온다. 그러나 인라인 함수는 이러한 단순 치환이 아니기 때문에 정상적인 결과인 49가 나온다.

단점?

매 함수 호출마다 해당 함수를 전부 가지고 오기 때문에 메모리 공간적으로 낭비가 심하다. 즉 10번 함수를 호출하면 10개의 동일한 코드가 메모리를 차지한다.

접근 제어 지시자를 통해 구조체, 또는 클래스의 멤버들에 대한 접근 권한을 설정할 수 있다. 외부에서 사용자가 알 필요가 없는 정보는 사용자로부터 숨기는 것이 좋다. (정보 은닉) 이를 통해 사용자는 최소한의 정보로 프로그램을 쉽게 사용 가능하다.

Public

멤버가 어떠한 접근 제약도 가지지 않는다.즉 파생 클래스, 다른 클래스, 또는 다른 패키지에서도 모두 해당 멤버에 접근 가능하다. 따라서 private 멤버와 다른 클래스, 또는 프로그램간의 인터페이스 역할을 할 수 있다.

Private

멤버가 외부에 공개되지 않아서 접근이 불가능하며, 클래스 내부에서만 접근 가능하다. (파생 클래스도 불가) 따라서 외부에서 접근을 위해서는, private에 접근하는 public 멤버를 활용해야 한다. 클래스에 접근 제어 지시자를 생략하였을 때의 기본 접근 제어 권한은 private이다.

Protected

protected는 기본적으로 private과 같다. 그러나 다음의 경우 protected에 접근할 수 있다.

• public 또는 protected로 파생된 클래스

friend

friend는 접근 제어자는 아니다.friend 키워드를 사용하여 클래스나 함수를 명시할 수 있다. friend 함수 또는 클래스는 friend의 private / protected 멤버에 접근 가능하다.

class Friend1 {
private:
    int m1;
    friend class Friend2;        //Friend2가 Friend1의 친구 클래스임을 명시
}

class Firend2 {
public:
    void access_friend(Friend1& f, int m){
        f.m1 = m;        
        //파생클래스가 아니지만 friend이기 때문에 private / protected 접근 가능
    }
}

서버와 클라이언트가 같은 키를 사용. 클라이언트에서 암호화한 키를 서버에서 똑같이 사용하여 복호화한다.

문제점?

서버와 클라이언트가 어떻게 같은 키를 가지게 할 것인가가 문제다. 만약 클라이언트에서 서버로 암호키를 전송한다면, 중간에 패킷 스니핑 등으로 해당 암호키를 탈취하면 보안의 의미가 없어진다.또한 서버가 클라이언트와 통신을 할 때 각각의 클라이언트에 대해 각각의 대칭키를 가지게 되면 키의 개수가 급증한다.

비대칭키 (공개키)

A키로 암호화하고, B키로 복호화한다. 개인키로 암호화 한 정보는 그 쌍이 되는 공개키로만 복호화가 가능하고, 공개키로 암호화한 정보는 그 쌍이 되는 개인키로만 복호화가 가능하다. 예를 들어, 네이버는 개인키를 보유하고, 공개키를 클라이언트(유저)들에게 공개한다. 유저는 해당 공개키로 암호화를 하여 네이버 서버에 데이터를 전송한다. 공개키로는 해당 암호문을 해독할 수 없기 때문에 개인키를 가진 네이버만 복호화가 가능하다. 또한 네이버가 유저에게 전송하는 데이터 중 일부는 네이버의 개인키로 암호화되며, 이는 공개키로 해독 가능하다. 따라서 해당 암호화된 데이터가 해독가능하다면 네이버 공식사이트로 인지할 수 있고, 해독 불가능하다면 네이버 피싱 사이트 등 다른 사이트임을 알 수 있어서 보안을 유지 가능하다.

HTTPS

https는 최초 접속 시 공개키-개인키 방식, 즉 비대칭키 방식으로 데이터를 주고 받는다. 그러나 비대칭키는 성능적으로 큰 오버헤드를 유발하기 때문에 이후 통신에는 대칭키를 사용한다. 이러한 대칭키를 공유할 때 비대칭키를 사용하기 때문에 기존 대칭키 스니핑 등으로 인한 문제점은 해결 가능하다.

Structured Query Language 관계형 모델이 가지는 큰 장점 중 하나. 원하는 데이터를 간단하게 조작할 수 있다. DBMS의 Optimizer가 쿼리를 re-order과 같은 작업으로 자동으로 어느 정도 최적화해준다.

Select, Delete, Update, Insert 등 다양한 쿼리 명령어가 존재한다.

View

쿼리를 통해 가상 테이블인 View를 생성할 수 있다.

CREATE VIEW HighScoreStudents(sid,gpa)
    AS SELECT S.sid, S.gpa
    FROM Students S
    WHERE S.gpa > 3.5

View를 통해 외부 스키마와 내부, 논리 스키마의 독립인 논리적 데이터 독립성이 보장된다. 즉 원본 테이블의 확장/축소 (다른 field 추가/삭제) 시 기존의 View가 참조하는 field에 영향이 없다면 기존의 View는 영향받지 않는다. View 또한 가상이긴 하지만 Table이기 떄문에 Table에 수행하는 update, insert, select 등이 가능하다.

릴레이션의 삭제, 변경

DROP TABLE Students [RESTRICT | CASCADE]

Students 릴레이션(schema + instance)을 삭제한다.

• RESTRICT: 참조하는 뷰나 제약조건이 있으면 실패
• CASCADE: 참조 뷰나 제약조건도 모두 삭제

ALTER TABLE Students ADD COLUMN firstYear:integer

Students 릴레이션의 스키마가 새로운 필드 추가로 변경된다. 기존의 모든 튜플들은 새로운 필드에 대해 null값을 가지게 된다.

관계형 데이터 모델의 구성 요소

• 구조 (Structure): 개체 타입들간의 관계로 데이터 구조를 표현 DDL(Data Definition Language): 데이터베이스 구조를 정의, 수정, 삭제하는 언어 ( alter, create, drop, view creation, index creation )
• 연산 (Operations): 데이터의 처리 작업. DB를 조작하는 기본 도구. DML(Data Manipulation Language): 데이터베이스 내의 검색, 삽입, 갱신, 삭제 등을 하는 언어 ( select, insert, update, delete )
• 제약 조건 (Constraints): 데이터의 논리적인 제약 조건 DCL (Data Control Language): 데이터 무결성 유지, 보호, 관리, 권한 부여 등을 하는 언어 ( commit, rollback, grant, revoke )

관계형 데이터베이스

관계형 데이터베이스: a set of relations 릴레이션: Schema와 Instance로 구성된다.

• Schema: 릴레이션의 이름과 각 column(attribute)의 이름과 타입
• Instance: row와 column으로 구성된 table ❗️ # of rows = cardinality, # of fields = degree/arity

무결성 제약조건

DBMS는 릴레이션 내의 데이터가 지켜야 할 조건들을 관리한다. 스키마가 정의될 때 구체화되며, 릴레이션의 변경 (insert, delte, update)가 발생할 때 제약 조건을 검사한다.

키 (Key)

• 유일성: 어떠한 2개의 튜플도 키 필드에 대해 같은 값을 가질 수 없다.
• 최소성: 키를 구성하는 속성들이 진짜 각 튜플을 구분하는데 꼭 필요한 속성들로만 구성되어 있어야 한다. 최소성을 만족하지 않는 키 ➡️ 수퍼키(super key) 하나의 릴레이션에 여러 개의 candidate keys가 있다면, 그 중 하나가 primary key가 된다.

슈퍼키(Super Key)

유일성은 만족하지만 최소성을 만족하지 않는 키 (더 정확히는, 최소성에 관한 제약조건이 없기 때문에 최소성을 지켜도, 안지켜도 된다). 예를 들어, 학생의 학번은 고유 번호이기 때문에 유일성과 최소성을 만족한다. 그러나 학생의 이름, 나이, 성별 등은 중복이 가능하여 유일성을 만족하지 않는다. 만약 (학번,이름,나이,성별)을 키로 사용한다면, 이름, 나이, 성별은 중복이 가능하지만 학번으로 인해 유일성을 가지게 된다. 그러나 이름, 나이, 성별은 각 튜플을 구분하는데 꼭 필요한 속성이 아니기 때문에 최소성을 만족하지 못한다. 따라서 (학번,이름,나이,성별)은 유일성을 만족하지만 최소성을 만족하지 않는 슈퍼키가 된다.

후보키(Candidate Key)

슈퍼키가 유일성만 만족하고 최소성에는 제약이 없었다면, 후보키는 유일성과 최소성 모두 요구된다. UNIQUE를 통해 후보키로 설정될 수 있으며, 이러한 후보키 중 하나가 기본키가 된다. 기본키로 적절한 조건은 다음과 같다.

• NULL 값을 가질 수 있는 속성이 포함된 후보키는 기본키로 부적절하다.
• 값이 자주 변경될 수 있는 속성이 포함된 후보키는 기본키로 부적절하다.
• 단순한 것으로 선택한다.

기본키(Primary Key)

후보키 중 하나로 선정된 키

대체키

후보키 중 기본키를 제외한 키

외래키(Foreign Key)

어떤 릴레이션의 특정 field 또는 field 집합이 다른 릴레이션의 기본키인 경우, 이를 외래키라 한다. 데이터 무결성을 위해 존재한다. 예를 들어 주문 릴레이션에서 고객의 id를 외래키로 하는 경우, 고객의 id가 변경되면 주문에서의 고객 id 역시 변경된다. 그러나 고객의 id를 외래키로 하지 않고 고유하게 관리한다면, 고객 릴레이션과 주문 릴레이션에서의 고객 id 값이 달라질 수 있다. 또한 외래키로 지정이 되면, 참조하는 테이블에 없는 값은 입력이 불가하다. Foreign Key의 참조 키 update/delete에 대해 다음과 같은 처리가 가능하다.

• CASCADE: Foreign Key가 함께 수정/삭제된다.
• No Action: update/delete가 거부된다.
• Set Default: Foreign Key가 기본값으로 설정된다.
• Set NULL: Foreign Key가 NULL로 설정된다.

View

일종의 가상 릴레이션이다. 따라서 실제로 디스크에 해당 뷰에 대한 저장 공간의 할당이 이루어지는 것이 아닌, 딕셔너리 테이블에 뷰에 대한 정의만 저장된다. 또한 뷰에 대한 update, delete 등의 수정은 해당 뷰가 참조하는 원본 테이블에 대해서도 이루어진다. 뷰를 통해 사용자 별로 특정 객체에 대한 접근 권한을 설정 가능하며, 논리적 독립성이 제공된다.

파일시스템 vs DBMS

파일시스템

• Concurrency Control (동시성 제어): 다수 사용자의 하나의 파일에 대한 동시 작업(동기화)이 불가하다.
• 데이터 간 불일치: 중복된 데이터의 변경 제어가 어려워, 일부의 데이터만 변경될 수 있다. 따라서 데이터의 불일치가 발생할 수 있다.
• 쿼리: 지원하지 않는다. 즉 원하는 데이터를 편하게 가져올 수 없다.
• Recovery: 지원하지 않는다. 데이터에 손상이 생길 경우 복구가 어려울 수 있다.
• Security & Access Control: 유연하지 못하다. 유저별 파일의 특정 레코드에 대한 접근 권한, 보안 등의 설정이 까다롭다. (파일 단위의 권한 부여만 가능)
• Data Integrity (데이터 무결성): 파일의 데이터가 지켜야 할 조건들을 일일이 프로그램에 명시해야 하기 때문에 무결성 제약 조건 유지 관리가 어렵다.
• 데이터 독립성: 데이터 독립성이란 하위 단계의 데이터 구조가 변경되어도 상위 단계에 영향을 미치지 않는 것이다. 파일시스템에서는, 파일의 데이터가 응용 프로그램에 적용이 되어있다. 따라서 파일의 구조가 바뀌면 해당하는 응용 프로그램 역시 모두 수정이 요구된다.

  DBMS

• Concurrency Control (동시성 제어): 다중 사용자의 동시 작업을 트랜잭션 레벨 설정을 통해 지원한다.
• 쿼리: SQL을 통해 원하는 데이터를 얻을 수 있다.
• Recovery: Undo, Redo 로그를 통해 회복을 지원한다.
• Security & Access Control: 유저 (또는 프로그램) 별로 테이블/레코드에 대한 접근 권한 설정이 가능하다.
• Data Integrity (데이터 무결성): 데이터가 지켜야 할 조건들을 DBMS가 관리해준다.
• 데이터 독립성: 논리적 데이터 독립성과 물리적 데이터 독립성을 모두 가지고 있다.
  1. 논리적 데이터 독립성: 데이터베이스의 논리적 구조가 변경되더라도 응용 프로그램에 영향을 주지 않는다. 즉 개념 스키마가 변경되어도 외부 스키마(View)에 영향을 미치지 않는다.
  2. 물리적 데이터 독립성: 데이터의 물리적 구조가 변경되더라도 응용 프로그램과 데이터베이스의 논리적 구조에 영향을 주지 않는다. 즉 내부 스키마(Index 등)가 변경되어도 외부 / 개념 스키마에 영향을 미치지 않는다.

스키마

데이터베이스의 구조와 제약조건에 관해 전반적인 명세

• 외부 스키마(External Schema): 유저가 데이터를 어떻게 보는가 (View)
• 개념 스키마(Conceptual Schema): 데이터베이스의 전체적인 논리적 구조. 개체간의 관계와 제약조건을 명시한다.
• 내부 스키마(Physical Schema): 물리적인 저장장치에 DB가 저장되는 방법. (index, unordered 등)

그림 예시

DDL in SQL: external schema: Create view logical schema: Create table phyisical schema: Create index, Create table ... partitioning

데이터 독립성

논리적 독립성: 데이터의 개념 스키마가 변경되어도 외부 스키마에 영향을 미치지 않는다. 물리적 독립성: 데이터의 내부 스키마가 변경되어도 외부, 개념 스키마에 영향을 미치지 않는다.

비비교 정렬 (Non-Comparison)

Counting Sort

계수 정렬은 각 원소의 개수를 세서 배열에 저장한다. 따라서 원소의 최대값 크기만큼의 배열이 요구된다. 과정

시간복잡도

최선, 평균, 최악의 경우와 관계없이 모두 O(N+K)가 요구된다. K는 원소의 최대값이다. 만약 원소 중 음수가 있다면, 최소값만큼 K를 더해줘야 한다. 즉, N개의 원소에 대해 counting을 한 후, 최소값(or 0) ~ 최대값까지 개수를 저장하는 배열의 값을 탐색해야하는 것이다. ➡️ T(N) = O(N+K)

공간복잡도

K (음수가 있을 경우 최소값+K) 만큼의 추가 배열이 요구된다. ➡️ O(K)

장점

K가 작다면 효율적이다.

단점

K에 따라 시간과 메모리의 낭비가 심할 수 있다.

Radix Sort

기수 정렬은 낮은 자리수부터 비교하여 정렬하는 방식이다. 즉 1의 자리, 10의 자리, 100의 자리, ... 순으로 정렬하여 임시 배열에 저장한다. 과정

시간복잡도

N개의 원소를 최대 자리수만큼 반복하여 정렬하면 된다. ➡️ T(N) = O(N)

공간복잡도

기수의 개수만큼 (eg. 09, az, A~Z...) 추가적인 공간이 필요하다.

장점

O(N)이라는 매우 빠른 속도로 가능하다.

단점

데이터 타입이 일정해야 한다. 데이터 타입에 따라 구현의 조건이 많아지거나 불가능할 수 있다. (eg. double, float) 양의 정수는 양의 정수끼리, 음의 정수는 음의 정소끼리 비교해야 한다. 추가적인 메모리 공간이 요구된다.

비비교 정렬 알고리즘 비교

안정 vs 불안정

Counting, Radix 둘 다 안정 정렬이다.

[참고 사이트] https://gaemi606.tistory.com/

#include <iostream>
using namespace std;
int N;
int* arr;
int* tmp_arr;
void print_arr(){
    for (int i=0; i<N; i++)
        cout << arr[i] << ' ';
    cout << '\n';
}

void sort(){
    //implement here
}

int main(){
    cin >> N;
    arr = new int[N];
    tmp_arr = new int[N];
    for (int i=0; i<N; i++)
        cin >> arr[i];
    cout << "before sort:\n";
    print_arr();
    cout << "\nafter sort:\n";
    sort();
    print_arr();
    return 0;
}

비교 정렬 (Comparison)

Bubble Sort

서로 인접한 두 원소의 대소관계를 검사하여 정렬한다. 즉 만약 오름차순으로 정렬한다면, 가장 큰 수가 마지막으로 오고, 그 후 두번째로 큰 수가 마지막에서 2번째로 오고, ...의 순으로 정렬된다. 과정

코드

void sort(){
    for (int i=0; i<N; i++){
        for (int j=0; j<N-i; j++){
            if (arr[j-1] > arr[j]){
                int tmp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

시간복잡도

최선, 평균, 최악의 경우와 관계없이 모두 O(N²)의 비교 횟수 교환은 최선의 경우 (이미 정렬된 경우) 한 번도 일어나지 않고, 역순으로 정렬된 경우 매번 일어나야 한다. ➡️ T(N) = O(N²)

공간복잡도

in-place로 정렬을 수행한다. ➡️ O(1)

장점

구현이 쉽다.

단점

느리기 때문에 거의 쓰이지 않는다.

Selection Sort

버블 정렬이 계속해서 인접한 수를 비교 후 swap했다면, 선택 정렬은 비교 대상 값의 index를 저장 후 한 번만 바꾼다. 즉 첫번째 자리에는 가장 최솟값의 index를 저장 후 해당 index의 값과 첫번째 원소를 swap, 두번째 자리에는 남은 원소들 중 최솟값의 index를 저장 후 해당 index의 값과 두번째 원소를 swap, ... 순으로 정렬된다. 과정

코드

void sort(){
    for (int i=0; i<N; i++){
        int idx = i;
        for (int j=i+1; j<N; j++){
            if (arr[idx] > arr[j])
                idx = j;
        }
        int tmp = arr[idx];
        arr[idx] = arr[i];
        arr[i] = tmp;
    }
}

시간복잡도

최선, 평균, 최악의 경우와 관계없이 모두 O(N²)의 비교 횟수 그러나 버블 정렬에 비해 교환의 횟수가 적다. ➡️ T(N) = O(N²)

공간복잡도

in-place로 정렬을 수행한다. ➡️ O(1)

장점

구현이 쉽다. 버블 정렬에 비해서는 swap 횟수가 적어 빠르다.

단점

불안정하다. 즉, 같은 값일 때 정렬 후 순서가 바뀔 수 있다. 구체적 예시로, 만약 a < b,B < c 이고, 현재 상태가 B b a c라면, 선택 정렬 후 a b B c가 되어 b와 B의 순서가 바뀐다. 느리다.

Insertion Sort

원소를 첫번째부터 마지막까지 원소들을 차례대로 자신의 위치에 끼워넣는 방식으로 정렬한다. 즉, 0부터 i-1번째 원소까지는 정렬이 됐다고 가정하고, i번째 원소를 i-1부터 0번째 원소까지 순서대로 비교를 하며 정렬 순서가 바꼈을 경우 swap을 해주고, 정렬 순서가 올바르다면 i+1번째 원소에 대해 같은 작업을 진행한다. 과정

코드

void sort(){
    for (int i=1; i<N; i++){
        int tmp = arr[i];
        int j;
        for (j=i-1; j>=0; j--){
            if (arr[j] > tmp)
                arr[j+1] = arr[j];
            else break;
        }
        arr[j+1] = tmp;
    }
}

시간복잡도

최선의 경우(이미 정렬되어 있을 경우), N번의 원소에 대해 swap없이 1번의 비교만 수행된다. ➡️ T(N) = O(N) 그러나 평균 또는 최악(역순으로 정렬)의 경우 N개의 원소에 대해 각각의 자리까지 swap이 이루어져야 한다. ➡️ T(N) = O(N²)

공간복잡도

in-place로 정렬을 수행한다. ➡️ O(1)

장점

원소들의 대부분이 정렬된 경우 좋은 성능을 보인다. 원소의 수가 적을 경우 간단한 알고리즘으로 다른 복잡한 정렬들에 비해 유리할 수 있다.

단점

역시 버블정렬에 비해는 좋은 성능을 보이지만, 대체적으로 많은 자리 이동이 요구되므로 성능이 좋지 않다.

Merge Sort

분할 ➡️ 정복 ➡️ 결합의 과정을 통해 정렬된다. 구체적으로, 더 이상 나뉘지 않을 때까지 절반으로 분할한다. 이후, 더 이상 나뉘지 않는 배열, 즉 원소가 하나인 배열에 대해서는 해당 원소를 반환한다. 두 개의 sub-배열을 결합하는 과정에서 비교를 통해 임시 배열에 정렬하여 저장한다. 최종적으로 모든 sub-배열을 결합하여 원래 배열 크기의 정렬된 배열이 완성된다. ❓어차피 하나 남을 때까지 분할하는데, 바로 안하고 절반씩 분할하는 이유? ❗️재귀적 구현을 위하여. 과정

코드

void merge(int left, int mid, int right){
    //sub-array merge (with sort)
    int i, j, k;
    i = left;
    j = mid+1;
    k=left;
    while(i<=mid || j<=right){
        if (j>right || (i<=mid&&arr[i] <= arr[j]))
            tmp_arr[k++] = arr[i++];
        else tmp_arr[k++] = arr[j++];
    }

    for (int itr=left; itr<=right; itr++)
        arr[itr] = tmp_arr[itr];
}

void merge_sort(int left, int right){
    if (left < right){
        int mid = (left+right)/2;
        //divide
        merge_sort(left,mid);
        merge_sort(mid+1, right);
        merge(left,mid,right);
    }
}

시간복잡도

분할 ➡️ 별도의 비교/이동 연산이 요구되지 않는다. 합병 ➡️ 1개, 2개, 4개, ..., N/2개 크기의 sub-array들이 이진트리를 이루고 있다고 가정할 수 있다. 이 때 트리의 높이는 log₂N 이다. 또한 트리의 각 레벨에서 최대 N번의 비교 연산이 요구된다. 따라서 비교 연산은 Nlog₂N 이 요구된다. 이동 연산의 경우, 임시 배열 (코드에서 tmp_arr)에 정렬 후 원본 배열로 다시 복사가 이루어진다. (2N) 또한 트리의 높이만큼 이러한 작업들이 이루어지므로, 2Nlog₂N 이 요구된다. ➡️ T(N) = O(Nlog₂N) 모든 레벨에 대해 N/2번의 비교 연산이 무조건 요구되기 때문에(예를 들어 배열1이 배열2보다 모두 크다고 해도 적어도 N/2번 비교가 이루어진 후에야 배열2를 모두 복사할 수 있다), 후 정렬이 이루어지기 때문에, 최악, 최선, 평균의 경우 모두 O(Nlog₂N)이 된다.

공간복잡도

N 크기의 추가적인 임시배열이 요구된다. ➡️ O(N)

장점

최악, 평균의 경우 Bubble, Selection, Insertion 정렬보다 빠르다.

단점

in-place 정렬에 비해 추가적인 임시 공간(배열)이 필요하다. 레코드들의 크기가 큰 경우 이동 횟수가 많기 때문에 (임시 배열로 정렬하면서 복사 후 다시 원본으로 복사) 비효율적이다.

Heap Sort

힙을 활용한 정렬. 정렬 대상 레코드들을 힙에 삽입하고, 하나씩 꺼내면서 저장하면 정렬이 된다.

힙 삽입 과정 힙 삭제 과정

코드

void sort(){
    priority_queue<int, vector<int>, greater<int>> pq;  //최소힙
    for (int i=0; i<N; i++)
        pq.push(arr[i]);
    for (int i=0; i<N; i++){
        arr[i] = pq.top();
        pq.pop();
    }
}

시간복잡도

힙에 N개의 원소를 삽입하는 시간 ➡️ O(Nlog₂N) 힙에서 N개의 원소를 꺼내는 시간 ➡️ O(Nlog₂N) ➡️ T(N) = O(Nlog₂N)

공간복잡도

추가적인 힙을 위한 공간을 사용한다면 O(N)이 필요하지만, 기존 배열 내에서 heapify한다면 O(1)로 가능하다. ➡️ O(1) or O(N)

장점

시간복잡도가 효율적이다. 전체 정렬이 아닌, 가장 큰 값 (또는 가장 작은 값) 몇 개만 필요할 때 유용하다.

단점

불안정하다.

Quick Sort

합병정렬과 같이 분할 ➡️ 정복 ➡️ 결합의 과정을 통해 정렬된다. 차이점은, 퀵정렬은 배열을 비균등하게 분할한다.

• pivot 원소를 선택한다.
• pivot 이하의 원소를 pivot 왼쪽, pivot보다 큰 원소를 pivot 오른쪽으로 옮긴다.
• 왼쪽 sub-array와 오른쪽 sub-array에 대해 같은 작업을 반복한다.

과정

코드

int partition(int left, int right){
    int pivot = arr[left];
    int l_idx = left;
    int r_idx = right;
    while(1){
        while (arr[l_idx]<=pivot)
            l_idx++;
        while (arr[r_idx] > pivot)
            r_idx--;
        if (l_idx < r_idx){
            int tmp = arr[l_idx];
            arr[l_idx] = arr[r_idx];
            arr[r_idx] = tmp;
        }
        else break;
    }
    arr[left] = arr[r_idx];
    arr[r_idx] = pivot;
    return r_idx;
}

void sort(int left, int right){
    //implement here
    if (left < right){
        int pivot_idx = partition(left,right);  //pivot의 index
        sort(left,pivot_idx-1);
        sort(pivot_idx+1,right);
    }
}

시간복잡도

최선의 경우는, pivot으로 리스트가 절반씩 계속하여 나뉘는 경우다. 이 경우, 트리의 높이가 log₂N 이 된다. 각 높이 별로 평균 N번의 비교가 이루어지기 때문에 ➡️ T(N) = O(Nlog₂N) 최악의 경우는, pivot이 리스트의 최대/최소 값으로 계속하여 선택되는 경우다. 즉 이미 정렬된 경우 최악의 효율을 보일 수 있다. 이 경우, 트리의 높이가 N이 되며, 각 레벨에서 비교 역시 N, N-1, N-2, ..., 1번까지 이루어지기 때문에 ➡️ T(N) = O(N²) 평균적으로 pivot을 극단적이지 않게 잘 선정한다면 ➡️ T(N) = O(Nlog₂N) 이 가능하다. 불필요한 데이터의 이동이 적고, 먼 거리의 데이터를 swap하며 한 번 결정된 pivot은 다음 재귀에서는 제외되기 때문에 다른 O(Nlog₂N) 의 정렬들보다도 빠르다. (즉 상수 계수가 낮다.)

❓효율적인 pivot 선정? ❗️pivot을 배열의 첫번째 원소로 선정한다면, 이미 정렬된 경우 최악의 시간복잡도가 된다. 따라서 첫번째 원소와 중간값을 swap해준다면 평균적인 시간복잡도로 개선 가능하다. 물론 이러한 방법은 최악을 피할 확률을 높이는 것이지 보장하는 것이 아니기 때문에 최악의 경우는 O(Nlog₂N)이 된다. ❗️또는 pivot을 리스트의 중간값으로 선정하는 방법이 있다. ❗️특정 위치의 원소를 pivot으로 설정하는 것이 아닌, 임의의 random 원소를 pivot으로 설정하면 평균의 성능을 얻을 확률이 높다.

공간복잡도

재귀적 호출로 인한 O(log N)이 요구된다. 따라서 이 역시 최악의 경우 O(N)까지 악화될 수 있다. ➡️ O(log N) or O(N)

장점

평균적으로 매우 빠르다. 다른 O(Nlog₂N)의 정렬들 중 가장 빠르다. O(N)의 공간을 요구하는 Merge Sort보다 적은 O(log N)의 공간을 요구한다.

단점

최악의 경우 시간복잡도가 O(N²)까지 악화된다. 불안정하다.

비교 정렬 알고리즘 비교

안정 vs 불안정

[참고 사이트] https://gmlwjd9405.github.io/