기역니은

boolean solution(String inputString) {
    for (int i = 0; i < inputString.length() / 2; i++) {
        if (inputString.charAt(i) != inputString.charAt(inputString.length() - i - 1)) {
            return false;
        } 
    }
    return true;
}

먼저 두 노드를 회전시킨다는 건 두 노드의 높이를 서로 바꾸는 것을 의미한다. 그냥 잡아 피는 게 아니라 노드의 부모자식관계를 역전시켜야 한다.

일직선 불균형, 꺽쇠 불균형은 단지 내가 분류하려고 붙인 것일 뿐 정식 명칭은 아니다. 본래 왼쪽 자식의 왼쪽 서브트리에서 불균형이 발생하면 LL 유형 오른쪽 자식의 왼쪽 서브트리에서 불균형이 발생하면 RL유형과 같이 말한다.

오른쪽 회전, 왼쪽 회전이 헷갈린다면 그냥 시계방향(오른쪽 회전) 반시계방향(왼쪽 회전)으로 이해하면 좀 낫다.

1. 일직선 불균형(RR,  LL유형)

불균형이 생긴 서브트리의 반대 방향으로 회전한다.

왼쪽 자식의 왼쪽 서브트리에서 불균형이 발생하면 오른쪽(시계방향)으로 회전(LL유형)

오른쪽 자식의 오른쪽 서브트리에서 불균형이 발생하면 왼쪽(반시계방향)으로 회전(RR유형)

왼쪽 자식의 서브트리에서 불균형이 발생했으므로 오른쪽(시계방향) 회전한다.

2. 꺽쇠 불균형(RL, LR유형)

a. 자식 노드를 불균형이 발생한 방향으로 회전시켜 일직선 노드를 만든다.

왼쪽에서 불균형이 발생했으므로 자식노드를 왼쪽(반시계방향) 회전한다.

b. 일직선 불균형이 됐으므로 부모노드를 반대 방향으로 회전시킨다.

부모 노드를 오른쪽(시계방향) 회전한다.

1. 접근

ArrayList :  요소의 위치를 알면 인덱스로 바로 접근해서 시간복잡도가 O(1)이다.

LinkedList : 첫 노드부터 순차적으로 접근해야 되므로 시간 복잡도가 O(n)이다.

2. 삽입 및 삭제

ArrayList : 리스트 끝에 삽입하거나 삭제할 때의 시간복잡도는 O(1)이지만 그 외에는 다른 요소들을 복사해 이동시켜줘야 하므로 O(n)이다. (이와 같은 특징 때문에 Stack을 구현하기에 적합하다)

LinkedList : 첫 노드를 삽입하거나 제거할 때의 시간복잡도는 O(1)이지만 맨 끝에 삽입하거나 제거할 때는 맨 마지막 노드까지 접근해야 하므로 O(n)의 시간복잡도를 갖는다. (이와 같은 특징 때문에 Queue를 구현하기에 적합하다)

리스트 중간에 요소를 제거하거나 삽입할 때는 대체로 LinkedList의 처리속도가 더 빠르다.

4. 메모리 사용

ArrayList : 배열의 크기는 고정되어있으므로 요소가 배열의 크기를 벗어나면 더 큰 배열을 새로 생성해 기존 배열의 내용을 복사해 줘야 된다. 그렇다고 배열의 크기를 너무 크게 잡으면 메모리가 낭비된다.

LinkedList : 크기가 가변적이므로 요소들을 계속 추가해도 상관없다. 다만 배열리스트와는 다르게 next 포인터를 가지고 있어 배열리스트보다 더 많은 용량을 차지한다.

- O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다. 

- o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.

- θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.

- Ω (빅 오메가 복잡도) : 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.

- ω (리틀 오메가 복잡도) : 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.

※ 시간 복잡도를 다룰 때 등호(=)는 같다는 뜻이 아니라 속한다(∈)에 가깝다. 

예를 들어 아래 식이 참인지 판별하려면 2n이 n과 같거나 더 빠른 범위에 포함되는지를 확인하면 된다. 시간복잡도를 다룰 때 상수는 무시하므로 2n은 n과 같다. 고로 아래 식은 참이다.

n^3/4이 nlogn보다 같거나 빠르다는 뜻이다. 입력값이 작은 경우는 고려하지 않고 계산하기 쉬운 큰 값을 넣어 맞는지 확인해 보자

n = 1000, 로그의 밑을 10으로 놓고 계산하면

좌항은 10000, 우항은 3000이므로 좌항이 더 크다. 즉 n^3/4가 nlogn보다 더 시간복잡도가 큰 느린 알고리즘이므로 위 식은 거짓이다.

상수는 무시하고, 최고차항만을 고려하므로 좌항과 우항은 같다. 곧 위 식은 참이다.

1. 입력값(n)은 항상 0보다 크다.

2. 입력값이 증가하면 처리시간도 늘어난다.

3. 모든 상수를 무시한다. 

3n, 10n, 4n+13 모두 시간 복잡도가 n인 알고리즘이다.

4. 다항식에서 가장 높은 차수의 항만을 고려한다.

- 4n^7+22n^5+10n 의 시간 복잡도는 n^7이다.

5. 로그의 밑은 무시한다.

- 로그의 밑을 계산하기 가장 편한 값으로 두고 계산하면 된다.

- 시간 복잡도가 로그인 알고리즘은 보통 2로 나누거나 곱하는 경우에 자주 쓰인다.