데린이 성장 일지

https://school.programmers.co.kr/learn/courses/30/lessons/49995

1차 시도

첫째 아들에게 쿠키를 주다가 둘째 아들에게 쿠키를 주는 기준점을 정해서 answer을 구하는 방법으로 코드를 구현했습니다.

def solution(cookie):
    answer = 0
    N = len(cookie)
    
    if N == 1:
        return answer
    
    for mid in range(N-1):
        l = mid
        r = mid+1
        while l >= 0 and r <= N-1:
            first_cookie = sum(cookie[l:mid+1])
            second_cookie = sum(cookie[mid+1:r+1])
            if first_cookie == second_cookie:
                answer = max(answer, first_cookie)
                r += 1
                l -= 1
            elif first_cookie > second_cookie:
                r += 1
            else:
                l -= 1
        
    return answer

2차 시도

1차 시도에서 시간을 줄일 수 있는 방법으로 while문을 돌 때 sum을 매번 하는 것이 아닌 새롭게 추가된 쿠키를 더하는 방법으로 변경했습니다.

def solution(cookie):
    answer = 0
    N = len(cookie)
    
    if N == 1:
        return answer
    
    for mid in range(N-1):
        l = mid
        r = mid+1
        first_cookie = cookie[l]
        second_cookie = cookie[r]
        while True:
            if first_cookie == second_cookie:
                answer = max(answer, first_cookie)
                r += 1
                l -= 1
                if l >= 0 and r <= N-1:
                    first_cookie += cookie[l]
                    second_cookie += cookie[r]
                else:
                    break
            elif first_cookie > second_cookie:
                r += 1
                if r <= N-1:
                    second_cookie += cookie[r]
                else:
                    break
            else:
                l -= 1
                if l >= 0:
                    first_cookie += cookie[l]
                else:
                    break
        
    return answer

코드 설명

기준점 mid를 for문으로 전부 돕니다.

while문이 핵심 코드인데,

• if first_cookie == second_cookie:(첫째 아들에게 준 쿠키와 둘째 아들에게 준 쿠키가 같다면)
  answer와 first_cookie 중 높은 수를 answer로 초기화합니다.
  r은 1을 더해주고 l은 1을 뺍니다.
  유효한 r과 l이라면 first_cookie와 second_cookie에 바로 전 또는 후의 쿠키를 더해주게 됩니다.
  유효하지 않다면 while문을 종료합니다.
• elif first_cookie > second_cookie:(첫째 아들에게 준 쿠키가 더 많다면)
  r에 1을 더해줍니다.
  유효한 r이라면 second_cookie에 바로 후의 쿠키를 더해줍니다.
  유효하지 않다면 while문을 종료합니다.
• else:(둘째 아들에게 준 쿠키가 더 많다면)
  l에 1을 빼줍니다.
  유효한 l이라면 first_cookie에 바로 전의 쿠키를 더해줍니다.
  유효하지 않다면 while문을 종료합니다.

https://school.programmers.co.kr/learn/courses/30/lessons/42897?language=python3

1차 시도

dp로 푸는 것을 떠올랐고, 첫 번째 집부터 터는 경우와 두 번째 집부터 터는 경우로 나누어서 각 경우의 마지막 dp 값이 큰 경우가 답이 될 것이라 생각했습니다.

def solution(money):
    N = len(money)
    
    # 첫 번째부터 털 경우 -> 마지막 집 못 텀
    dp = [0] * N
    
    dp[0] = money[0]
    dp[1] = money[0]
    
    for i in range(2, N-1):
        dp[i] = max(dp[i-2] + money[i], dp[i-1])
        
    from_first = dp[N-2]
    
    # 두 번째부터 털 경우
    dp = [0] * N
    
    dp[0] = 0
    dp[1] = money[1]
    
    for i in range(2, N):
        dp[i] = max(dp[i-2] + money[i], dp[i-1])
        
    from_second = dp[N-1]
    
    return max(from_first, from_second)

결과: 100

정확성, 효율성 모두 통과

풀이

현재(i)까지 집을 털었을 때 최대값은 

• i-2 번째까지 집을 털었을 때 최대값(dp[i-2]) +  i 번째 집을 털었을 때
• i-1 번째까지 집을 털었을 때 최대값(dp[i-1])

이 두 경우를 비교해서 더 큰 값이 dp[i]가 됩니다.

첫 번째 집을 털 경우 마지막 집은 첫 번째 집과 인접하기 때문에 털 수가 없습니다.

그래서 첫 번째 집부터 털 경우와 두 번째 집부터 털 경우를 구분해야 합니다.

첫 번째 집부터 털 경우

첫 번째 집을 털 경우 두 번째 집을 털지 못하기 때문에 dp[0]과 dp[1]는 money[0]이 됩니다.

마지막 집의 바로 전 집(N-2)까지 턴 경우의 최대값이 첫 번째 집부터 털 경우의 최대값(dp[N-2])이 됩니다.

두 번째 집부터 털 경우

첫 번째 집을 털지 않고 두 번째 집을 털기 때문에 dp[0]는 0, dp[1]는 money[1]이 됩니다.

마지막 집(N-1)까지 턴 경우의 최대값이 두 번째 집부터 털 경우의 최대값(dp[N-1])이 됩니다.

두 경우의 최대값 중 더 큰 값이 정답이 됩니다.

인덱스(Index)

인덱스가 없다면 모든 테이블의 데이터를 스캔(Full Table Scan)해야 합니다.

테이블을 가리키는 대상이기 때문에 테이블이 삭제되면 같이 삭제됩니다.

인덱스 부작용

인덱스를 저장할 추가적인 공간이 필요합니다.

인덱스 작성 시간이 있기 때문에 행 데이터가 너무 많으면 이 시간이 오래 걸릴 수 있습니다.

INSERT, UPDATE, DELETE 작업 할 때 인덱스를 다시 작성하기 때문에 검색(SELECT)가 아닌 작업(INSERT, UPDATE, DELETE) 시 성능이 낮아집니다.

※ INSERT가 나머지 UPDATE, DELETE보다 성능이 더 낮아질 수 있습니다.

그래서 인덱스를 사용하기 좋은 열은?

• SELECT이 많고 INSERT, UPDATE, DELETE가 적은 열
• 카디널리티(Cardinality)가 높은 열

인덱스 종류

클러스터형 인덱스(Clustered index)

테이블 당 하나만 있습니다.

PRIMARY KEY(우선 지정) / UNIQUE + NOT NULL 제약 조건 지정 시 자동 생성합니다.

행 데이터가 클러스터형 인덱스로 지정된 데이터에 대해 자동 정렬합니다.

※ 대부분 PRIMARY KEY에 클러스터형 인덱스가 걸릴 거라 생각합니다.

보조인덱스(Secondary index)

테이블당 여러 개 가능합니다.

중복값을 가질 수 있습니다.

고유키로 지정된 컬럼(UNIQUE 제약 조건)은 자동으로 보조 인덱스가 생성됩니다.

행 데이터가 인덱스로 지정된 데이터에 대해 자동 정렬하지 않습니다.

보조 인덱스 사용 방법

-- 인덱스 생성
CREATE INDEX 인덱스명 ON 테이블명 (컬럼명);

-- 인덱스 조회
SHOW INDEX FROM 테이블명;

-- 인덱스 삭제
DROP INDEX 인덱스명 FROM 테이블명;

뷰(View)

select의 결과를 하나의 테이블처럼 사용하는 가상의 테이블입니다.

뷰를 사용하며 쿼리가 단순화되고 모든 데이터를 보여줄 필요가 없게 됩니다.

뷰 사용 방법

-- 뷰 생성
USE VIEW 뷰이름 AS SELECT문;

-- 뷰 삭제
DROP VIEW 뷰이름

조회는 제한이 없을지 모르나 삽입, 수정, 삭제는 안될 수도 있습니다.

뷰는 실제 테이블이 아니기 때문에 뷰에 대한 조작을 하면 참조한 테이블이 조작됩니다.

그렇기 때문에 참조한 테이블의 제약조건에 위배되는 뷰에 대한 조작을 할 수 없습니다.

또한 집계함수를 이용하여 뷰를 만든 경우에는 조회만 가능하게 됩니다.

조인(Join)

RDB의 강력한 기능 중 하나입니다.

여러 테이블을 하나로 묶는 방법입니다.

조인 종류

Outer Join에서 어느 한쪽에 없는 데이터는 null로 채워지게 됩니다.

조인 사용 방법

-- inner join
SELECT Employees.Name, Employees.Position, Departments.DepartmentName
FROM Employees
INNER JOIN Departments ON Employees.DepartmentID = Departments.ID;

-- left outer join
SELECT Employees.Name, Employees.Position, Departments.DepartmentName
FROM Employees
LEFT OUTER JOIN Departments ON Employees.DepartmentID = Departments.ID;

-- right outer join
SELECT Employees.Name, Employees.Position, Departments.DepartmentName
FROM Employees
RIGHT OUTER JOIN Departments ON Employees.DepartmentID = Departments.ID;

-- full outer join
SELECT Employees.Name, Employees.Position, Departments.DepartmentName
FROM Employees
FULL OUTER JOIN Departments ON Employees.DepartmentID = Departments.ID;

-- union
SELECT Employees.Name, Employees.Position, Departments.DepartmentName
FROM Employees
LEFT JOIN Departments ON Employees.DepartmentID = Departments.ID
UNION
SELECT Employees.Name, Employees.Position, Departments.DepartmentName
FROM Employees
RIGHT JOIN Departments ON Employees.DepartmentID = Departments.ID;

※ MySQL에서는 Full Outer Join을 지원않아서 UNION을 사용하여 구현한다고 합니다.

RDB에서 많이 사용되는 원칙이기에 정리하고자 합니다.

ACID

데이터베이스 관리 시스템 (DBMS)에서 트랜잭션의 원자성(Atomicity), 일관성(Consistency), 고립성(Isolation), 지속성(Durability)을 보장하기 위한 속성들을 가리키는 약어입니다.

원자성

트랜잭션과 관련된 작업들이 부분적으로 실행되다가 중단되지 않는 것을 보장하는 것입니다.

즉, 트랜잭션은 실패하거나 전부 성공해야 한다는 것입니다.

예를 들어, 자금 이체는 성공할 수도 실패할 수도 있지만 보내는 쪽에서 돈을 빼 오는 작업만 성공하고 받는 쪽에 돈을 넣는 작업을 실패해서는 안된다는 것입니다.

일관성

트랜잭션 처리 전과 처리 후 데이터 모순이 없는 상태를 유지해야 한다는 것입니다.

예를 들어, 마이너스 통장이면 안되는 통장의 잔고가 0원일 때, 돈을 빼 오는 작업이 성공되어선 안된다는 것입니다.

고립성

트랜잭션을 수행 시 다른 트랜잭션의 연산 작업이 끼어들지 못하도록 해야 한다는 것입니다.

이것은 트랜잭션 밖에 있는 어떤 연산도 중간 단계의 데이터를 볼 수 없음을 의미합니다.

예를 들어, 20만원 입금과 30만원 입금이 동시에 일어났을 때, 20만원 입금 트랜잭션이 30만원 입금 트랜잭션보다 늦게 끝나서 20만원 입금 결과만 반영이 되어선 안된다는 것입니다.

지속성

성공적으로 수행된 트랜잭션은 영원히 반영되어야 한다는 것입니다.

예를 들어, 20만원 입금이 성공했다면, DB에 장애가 발생한 후 복구되었을 때도 20만원 입금 성공 결과는 반영되어 있어야 한다는 것입니다.

저는 최근 프로젝트에서 데이터가 많아질 수록 쿼리 최적화로 성능을 높이는 것이 중요한 일 중 하나라고 느껴서 쿼리 최적화에 대해 정리하고자 합니다.

쿼리 최적화 방법

1. SELECT 시에는 필요한 컬럼만 가져오기

-- Inefficient
SELECT * FROM movie; 

-- Improved
SELECT id FROM movie;

많은 필드 값을 불러올수록 DB는 더 많은 로드를 부담하게 됩니다.

2. 조건 부여 시, 가급적이면 기존 DB값에 별도의 연산을 걸지 않기

-- Inefficient
SELECT m.id, ANY_VALUE(m.title) title, COUNT(r.id) r_count 
FROM movie m 
INNER JOIN rating r 
ON m.id = r.movie_id 
WHERE FLOOR(r.value/2) = 2 
GROUP BY m.id;

-- Improved
SELECT m.id, ANY_VALUE(m.title) title, COUNT(r.id) r_count 
FROM movie m 
INNER JOIN rating r 
ON m.id = r.movie_id 
WHERE r.value BETWEEN 4 AND 5 
GROUP BY m.id;

r.value에 인덱싱이 되어 있을 때, Inefficient 쿼리에서 r.value 값을 변환하고 있어서 r.value 인덱스를 활용할 수 없어서 Full Table Scan을 합니다.

또한, 함수를 적용하고 결과를 비교하는 비용이 생깁니다.

반면에 Improved 쿼리는 r.value 범위를 지정했기 때문에 r.value 인덱스를 활용하여 효율적으로 필요한 레코드를 찾을 수 있습니다.

3. LIKE 사용 시 와일드카드 문자열(%)을 String 앞부분에 배치하지 않기

-- Inefficient
SELECT g.value genre, COUNT(r.movie_id) r_cnt 
FROM rating r 
INNER JOIN genre g 
ON r.movie_id = g.movie_id 
WHERE g.value LIKE "%Comedy"  
GROUP BY g.value;

-- Improved(1): value IN (...)
SELECT g.value genre, COUNT(r.movie_id) r_cnt 
FROM rating r 
INNER JOIN genre g 
ON r.movie_id = g.movie_id 
WHERE g.value IN ("Romantic Comedy", "Comedy") 
GROUP BY g.value;

-- Improved(2): value = "..."
SELECT g.value genre, COUNT(r.movie_id) r_cnt 
FROM rating r 
INNER JOIN genre g 
ON r.movie_id = g.movie_id 
WHERE g.value = "Romantic Comedy" OR g.value = "Comedy"
GROUP BY g.value;

-- Improved(3): value LIKE "...%"
-- 모든 문자열을 탐색할 필요가 없어, 가장 좋은 성능을 내었습니다
SELECT g.value genre, COUNT(r.movie_id) r_cnt 
FROM rating r 
INNER JOIN genre g 
ON r.movie_id = g.movie_id 
WHERE g.value LIKE "Romantic%" OR g.value LIKE "Comed%"
GROUP BY g.value;

와일드 카드가 앞에 있다면 Full Table Scan을 하게 됩니다.

4. DISTINCT와 같은 중복 값을 제거하는 연산은 최대한 사용하지 않기

-- Inefficient
SELECT DISTINCT m.id, title 
FROM movie m  
INNER JOIN genre g 
ON m.id = g.movie_id;

-- Improved
SELECT m.id, title 
FROM movie m  
WHERE EXISTS (SELECT 'X' FROM rating r WHERE m.id = r.movie_id);

중복 값을 제거하는 연산은 많은 시간이 걸립니다.

만약 불가피하게 사용해야 하는 상황이라면, DINTINCT 연산을 EXISTS를 활용하는 방법으로 대체하거나, 연산의 대상이 되는 테이블의 크기를 최소화하는 방법을 사용하는 것이 좋습니다.

5. 같은 내용의 조건이라면, GROUP BY 연산 시에는 가급적 HAVING보다는 WHERE 절을 사용하기

-- Inefficient
SELECT m.id, COUNT(r.id) AS rating_cnt, AVG(r.value) AS avg_rating 
FROM movie m  
INNER JOIN rating r 
ON m.id = r.movie_id 
GROUP BY id 
HAVING m.id > 1000;

-- Improved
SELECT m.id, COUNT(r.id) AS rating_cnt, AVG(r.value) AS avg_rating 
FROM movie m  
INNER JOIN rating r 
ON m.id = r.movie_id 
WHERE m.id > 1000
GROUP BY id ;

쿼리 실행 순서에서 WHERE 절이 HAVING 절보다 먼저 실행되기 때문에, GROUP BY에서 다뤄야하는 데이터 크기를 미리 줄인다면 그만큼 빨라집니다.

같은 이야기로 ORDER BY도 다뤄야하는 데이터 크기를 미리 줄인 다음 사용하는 것이 좋습니다.

6. 3개 이상의 테이블을 INNER JOIN 할 때는, 크기가 가장 큰 테이블을 FROM 절에 배치하고, INNER JOIN 절에는 남은 테이블을 작은 순서대로 배치하기

-- Query (A)
SELECT m.title, r.value rating, g.value genre 
FROM rating r 
INNER JOIN genre g 
ON g.movie_id = r.movie_id  
INNER JOIN movie m 
ON m.id = r.movie_id;

-- Query (B)
SELECT m.title, r.value rating, g.value genre 
FROM rating r 
INNER JOIN movie m
ON r.movie_id = m.id 
INNER JOIN genre g 
ON r.movie_id = g.movie_id;

INNER JOIN 과정에서 최소한의 Combination을 탐색하도록 FROM & INNER JOIN의 순서를 배열하면 좋다는 이야기인데, 항상 통용되지는 않습니다.

간단한 INNER JOIN의 경우는 대부분의 Query Planner에서 가장 효과적인 순서를 탐색해 INNER JOIN의 순서를 바꾸기 때문에 결과적으로 Query A와 Query B 실행시간에 큰 차이는 없습니다.

7. 모든 값을 반환할 필요가 없을 때 LIMIT 사용하기

-- Inefficient
SELECT title
FROM `my-project.mydataset.mytable`
ORDER BY title;

-- Improved
SELECT title
FROM `my-project.mydataset.mytable`
ORDER BY title DESC
LIMIT 1000;

일부만 반환해도 될 때, LIMIT를 사용하면 반환 비용을 줄일 수 있습니다.
예를 들어 20만개의 데이터가 있는데, 이름 순 1000개를 보기위해 20만개를 다 반환 받아서 보는 것보다 1000개만 반환 받는 것이 반환 비용이 훨씬 적습니다.

8. 자주 사용하는 데이터의 형식에 대해서는 미리 전처리된 테이블을 따로 보관/관리하기

RDBMS의 원칙에 어긋나는 측면이 있고, DB의 실시간성을 반영하지 못할 가능성이 높기 때문에, 대부분 운영계보다는 분석계에서 더 많이 사용되곤 합니다.

JPA(Java Persistence API)는 자바 ORM 기술에 대한 API 표준입니다.

그렇기 때문에 JPA는 ORM의 장점과 단점을 가지고 있습니다.

ORM

ORM이란 Object Realational Mapping의 약자로 객체와 관계형 데이터베이스를 매핑해주는 것입니다.

장점

객체 지향적인 접근

객체 지향 프로그래밍 언어를 사용하는 애플리케이션과 관계형 데이터베이스 간에는 패러다임의 불일치가 있습니다.

객체는 클래스와 상속, 다형성 등의 개념을 사용하여 데이터를 표현하고, 관련된 동작을 캡슐화합니다.

반면에 관계형 데이터베이스는 테이블과 열, 행 등의 개념을 사용하여 데이터를 저장하고 관리합니다.

ORM은 이러한 불일치를 해결하여 객체 지향적인 코드로 데이터베이스를 다룰 수 있게 해줍니다.

독립성

특정 데이터베이스에 종속되지 않고 객체 지향적인 코드를 작성할 수 있습니다.

생상성 향상

SQL 쿼리를 직접 작성하는 번거로움을 줄일 수 있습니다.

대신 객체 지향적인 코드로 데이터베이스 조작을 수행할 수 있으므로 개발자가 더 쉽게 작업할 수 있습니다.

CRUD 기능을 자동으로 처리하고, 데이터베이스와의 통신을 추상화하여 개발 시간을 단축시킵니다.

유지보수성 향상

객체와 데이터베이스 간의 매핑이 명확해지므로, 코드의 유지 보수가 용이해집니다.

데이터베이스 스키마의 변경이 있을 때도 ORM을 사용하면 코드 수정이 최소화됩니다.

일반적으로 객체와 데이터베이스 사이의 매핑을 설정하는 많은 기능을 제공하여 유지 보수성을 향상시킵니다.

단점

SQL 제어의 어려움

복잡한 조인이나 집계 함수를 포함하는 쿼리를 작성하는 경우에는 네이티브 쿼리(native query)를 사용해야 할 수도 있습니다.

네이티브 쿼리를 사용하게 되면 특정 데이터베이스에 종속될 수도 있습니다.

성능 저하 위험

자동으로 생성되는 쿼리가 많기 때문에 개발자가 의도하지 않는 쿼리로 인해 성능이 저하될 수도 있습니다.

학습 곡선

개념과 기능을 이해하는 데 시간이 걸릴 수 있습니다.

많은 애플리케이션에서 데이터베이스를 활용하지만, 데이터베이스 연결에는 많은 비용이 듭니다.

이 비용을 줄이기 위해 커넥션 풀이라는 개념이 등장했다고 합니다.

커넥션 풀

데이터베이스와 커넥션된 객체를 일정한 수만큼 미리 만들어 넣어두는 컨테이너입니다.

애플리케이션에서 데이터베이스에 대한 조작이 있을 때, 커넥션 풀에서 커넥션을 꺼내와 사용합니다.

다 사용하면 커넥션을 커넥션 풀에 반환합니다.

이렇게 함으로써, 데이터베이스와 연결하고 끊는 비용을 줄이고, 효율적으로 데이터베이스와 통신 할 수 있습니다.

※ 종류는 여러가지 있지만 스프링부트는 성능과 동시성 면에서 우수한 성능을 보이는 HikariCP을 우선적으로 선택합니다. 

프로젝트를 설계하다 보면 DB를 선택해야 하는데, 어떤 종류의 DB를 선택하는 것이 좋을지 판단하는 데 사용한 글을 정리하고자 합니다.

RDBMS

장점

• 스키마가 명확하게 정의되어 있습니다.
• 데이터 무결성을 보장합니다.
• 각 데이터를 중복 없이 한 번만 저장합니다.

단점

• 스키마를 사전에 계획해야 하고 추후 수정 비용이 클 수 있습니다.
• 관계를 맺고 있어서 조인문이 많은 복잡한 쿼리가 만들어질 수 있습니다.
• 대체로 수직적 확장만 가능합니다.

NoSQL

장점

• 스키마가 없기 때문에 유연하고 언제든지 저장된 데이터를 조정하고 새로운 필드를 추가할 수 있습니다.
• 데이터가 애플리케이션이 필요로 하는 형식으로 저장되기 때문에 읽어오는 속도가 빠릅니다.
• 수평 확장이 가능합니다.
• 여러 대의 백업 서버 구성이 가능하여 장애 발생 시에도 무중단 서비스가 가능합니다.

단점

• 데이터베이스 일관성에 약합니다.
• 데이터가 여러 컬렉션에 중복되어 있어서 데이터를 update하는 경우 모든 컬렉션에서 수행해야하기 때문에 느립니다.

그렇다면 언제 뭘 써야할까?

RDBMS

• 관계를 맺고 있는 데이터가 자주 변경될 경우
• 변경될 여지가 없고, 명확한 스키마가 사용자와 데이터에게 중요한 이유

NoSQL

• 정확한 데이터 구조를 알 수 없거나 변경/확장 될 수 있는 경우
• 읽기를 자주 하지만, 데이터 변경은 자주 없는 경우
• 데이터베이스를 수평으로 확장해야 하는 경우(막대한 양의 데이터를 다뤄야 하는 경우)