지금의 기록이 미래의 자산이 된다.

• [Programmers] 17684. [3차] 압축

  2023-02-24

  devFancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(2022.02.24)
  • Review

  문제 링크

  성능 요약

  • 메모리: 80 MB, 시간: 6.50 ms

  구분

  • 코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT

  Answer Code1(2022.02.24)

  import java.util.ArrayList;
  import java.util.HashMap;
  
  class Solution {
      public int[] solution(String msg) {
          ArrayList<Integer> arr = new ArrayList<>();
          HashMap<String, Integer> hm = new HashMap<>();
          
          // [1] HashMap 알파벳으로 초기화
          for(int i = 'A'; i <= 'Z'; i++) {
              hm.put((char)i + "", i+1 - 'A');
          }
          
          for(int i = 0; i < msg.length(); i++) {
              int idx = i + 1;
              
              // [2] msg 길이만큼 반복
              while(idx <= msg.length()) {
                  // [3] idx가 문자열 끝까지 도달하면 해당 인덱스를 결과 배열에 추가
                  // 초기 반복문을 빠져나오기 위해 i를 idx로 초기화
                  if(idx == msg.length()) {
                      arr.add(hm.get(msg.substring(i)));
                      i = idx;
                      break;
                  }
                  
                  // [4] 다음 키 미리 계산(다음 키를 확인하기 위해 초기 반복문의 i보다 한칸 큰 idx 선언)
                  String nextKey = msg.substring(i, idx + 1);
                  // [5] 다음 키가 있을 경우 문자를 하나 추가하기 위해 idx 증가
                  if(hm.containsKey(nextKey)) 
                      idx++;
                  // [6] 다음 키가 없을 경우
                  else {
                      // [6-1] 결과 배열에 현재 키의 인덱스를 추가
                      arr.add(hm.get(msg.substring(i, idx)));
                      // [6-2] 현재 해쉬에 없는 다음 키를 해쉬에 추가
                      hm.put(nextKey, hm.size() + 1);
                      // [6-3] 문자의 idx-1 까지 처리했음으로 i를 idx-1로 초기화(밖에 반복문 시작시 i++ 되므로 idx-1로 초기화)
                      i = idx - 1;
                      break;
                  }
              }
          }
          // [7] ArrayList를 int []로 변환
          int[] answer = new int[arr.size()];
          for(int i = 0; i < arr.size(); i++) {
              answer[i] = arr.get(i);
          }
          return answer;
      }
  }
  

  Review

  • HashMap<문자열(키), 자연수(키에서 몇 번째 인덱스인지)>를 만들어서 구하는 문자열 처리 관련 문제였다.

  • 문제 설명 이해하는 데 어려움이 있었고, [3] ~ [6] 부분에 대한 구현 아이디어가 떠오르지 않았다.

  • 구현에 대한 아이디어는 yline 풀이를 참고했다.

  • 해당 문제는 풀이에 대한 코드 해석도 어려웠기 때문에 반드시 다시 풀어보자.

  Read All

  ---

• [Programmers] 12921. 소수찾기

  2023-02-24

  devFancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(2023.02.20)
  • Answer Code2(2023.02.24)
  • 문제 풀이

  문제 링크

  성능 요약

  • 메모리: 52.4 MB, 시간: 202.81 ms - Answer Code1(2023.02.20)

  • 메모리: 56 MB, 시간: 17.91 ms - Answer Code2(2023.02.24)

  구분

  • 코딩테스트 연습 > 연습문제

  Answer Code1(2023.02.20)

  class Solution {
      public int solution(int n) {
          
          boolean flag; // 소수이면 true, 아니면 false
          int answer = 0;
          
          //에라토스테네스의 법칙
          for(int i = 2; i <= n; i++) {
              flag = true;
              for(int j = 2; j <= Math.sqrt(i); j++) {
                  if(i%j == 0) {
                      flag = false;
                      break;
                  }
              }
              // flag = true, 소수값이므로 +1 추가
              if(flag == true) {
                  answer++;
              }
          }
          
          return answer;
          
      }
  }
  

  Answer Code2(2023.02.24)

  class Solution {
      public int solution(int n) {
          int answer = 0;
          int[] arr = new int[n + 1];
  
          for (int i = 2; i <= (int) Math.sqrt(n); ++i) {
              if (arr[i] == 1) continue;
              for (int j = i + i; j <= n; j += i) {
                  arr[j] = 1;
              }
          }
          
          for (int i = 2; i < arr.length; ++i) {
              if (arr[i] != 1) ++answer;
          }
  
          return answer;
      }
  }
  

  문제 풀이

  • 첫 번째 풀이는 시간이 너무 걸리고 효율성 테스트가 너무 높게 나와서, 해당 문제점을 개선하기 위해 다시 풀었다.

  • 두 번째 풀이의 아이디어는 밈아님의 소수찾기 풀이방법를 통해 알 수 있었다. (밈아님 감사합니다)

  • [1] 입력 받는 n 값이 커질 수록 반복문이 도는 횟수도 더 많아지므로, 반복문을 n번 돌리는 것이 아닌 n의 제곱근번을 돌리게 하여 반복문 실행 횟수를 줄이도록 했다.

    • 반복문을 n 까지가 아닌 n의 제곱근까지만 검사해도 소수인지 판별이 가능했다는 것이다.

  • [2] 그리고 첫 번째 풀이 방법에서 n번 반복되는 코드와 달리 두 번째 풀이 방법에는 소수의 개수를 체크하는 for문을 따로 빼냈다.

    • 굳이 n의 제곱근번을 반복하지 않고, 해당 배열의 갯수만큼 반복해도 소수가 몇개인지 확인할 수 있기 때문이다.
  Read All

  ---

• [DB] Locking

  2023-02-21

  devFancy

  Database
  Read All

  ---

• [데이터베이스개론] 트랜잭션

  2023-02-20

  devFancy

  Database
  • 트랜잭션
  • 트랜잭션 특성
  • 트랜잭션의 상태
  • 예상 질문

  이 글은 컴퓨터학부 수업인 데이터베이스 와 데이터베이스 개론을 공부하고 정리한 내용입니다.

  트랜잭션

  데이터베이스는 다수의 사용자가 동시에 사용하더라도 항상 모순이 없는 정확한 데이터를 유지해야 한다.

  데이터베이스 관리 시스템은 데이터베이스가 항상 정확하고 일관된 상태를 유지할 수 있도록 다양한 기능을 제공하는데, 그 중심에는 트랜잭션이 있다.

  트랜잭션은 작업 하나를 수행하는 데 필요한 데이터베이스의 연산들을 모아놓은 것으로, 데이터베이스에서 논리적인 작업의 단위가 된다. 그리고 데이터베이스에 장애가 발생했을 때 데이터를 복구하는 작업의 단위도 된다.

  예를 들어, 인터넷뱅킹을 통해 계좌이체 작업을 완벽하게 수행하기 위해 2개의 데이터베이스 연산을 처리해야 한다면, 계좌이체 트랜잭션은 2개의 연산으로 구성할 수 있다.

  이체하기 전의 팬시의 잔액은 20,000원이고 케빈의 잔액은 0원인 경우을 다음과 같이 정리했다.

  [이체하기 전의 DB 상태]

  팬시 잔액 : 20,000원
  케빈 잔액 :      0원
  

  이때 팬시가 브루스에게 10,000원을 이체한 경우 계좌이체 트랜잭션은 다음과 같이 2개의 연산으로 구성할 수 있다.

  (팬시의 계좌번호는 100, 케빈의 계좌번호는 200으로 가정한다)

  [1] 팬시 계좌에서 10,000원 인출

  UPDATE  계좌
  SET     잔액 = 잔액 - 10,000
  WHERE   계좌번호 = 100;
  

  [2] 케빈 계좌에 10,000원 입금

  UPDATE  계좌
  SET     잔액 = 잔액 + 10,000
  WHERE   계좌번호 = 200;
  

  [이체한 이후의 DB 상태]

  팬시 잔액 : 10,000원
  케빈 잔액 : 10,000원
  

  여기서 중요한 점은 2개의 UPDATE 문이 모두 완전하게 처리되어야 트랜잭션이 성공적으로 수행한다는 것이다. 만약 둘 중 하나라도 처리 과정에서 오류가 발생한다면, 모든 명령문의 실행을 취소하고 트랜잭션 작업 전의 데이터베이스 상태로 되돌아가야 한다.

  트랜잭션은 데이터베이스에 장애가 발생했을 때 복구 작업을 수행하거나, 다수의 사용자가 동시에 사용할 수 있도록 제어 작업을 하는데 중요한 단위로 사용된다.

  그러므로 데이터베이스의 무결성과 일관성을 보장하려면 작업을 수행하는 데 필요한 연산들을 하나의 트랜잭션으로 제대로 정의하고 관리해야 한다.

  트랜잭션 특성

  트랜잭션이 성공적으로 처리되어 데이터베이스의 무결성과 일관성이 보장되려면 네 가지 특성을 모두 만족해야 한다. 트랜잭션의 네 가지 특성을 각 특성에 해당하는 영어 단어 첫 자를 따로 ACID 특성이라고 한다.

  [1] 원자성(Atomicity) : 트랜잭션을 구성하는 연산들이 모두 정상적으로 실행되거나 하나도 실행되지 않아야 한다는 All-Or-Nothing 방식을 의미한다.

  만약 트랜잭션을 수행하다가 장애가 발생하여 작업을 완료하지 못했다면, 지금까지 실행한 연산 처리를 모두 취소하고 데이터베이스를 트랜잭션 작업 전의 상태로 되돌려 트랜잭션의 원자성을 보장해야 한다.

  그러므로 트랜잭션의 원자성을 보장하려면 이처럼 장애가 발생했을 때 데이터베이스의 원래 상태로 복구하는 회복 기능이 필요하다.

  커밋(Commit) : 여러 쿼리가 성공적으로 처리되었다고 확정하는 명령어로 트랜잭션 단위로 수행되며 변경된 내용이 모두 영구적으로 저장되는 것을 말한다. “커밋이 수행되었다.”라는 것은 “하나의 트랜잭션이 성공적으로 수행되었다.“를 말한다.

  롤벡(Rollback) : 에러나 여러 이슈 때문에 트랜잭션 전으로 돌려야 할 때 사용하는 것을 말한다.

  [2] 일관성(Consistency) : 트랜잭션이 성공적으로 수행된 이후에도 데이터베이스가 일관된 상태를 유지해야 함을 의미한다.

  [3] 격리성(Isolation) : 고립성이라고도 하는데 현재 수행 중인 트랜잭션이 완료될 때까지 트랜잭션이 생성한 중간 연산 결과에 다른 트랜잭션들이 접근할 수 없음을 의미한다.

  각 트랜잭션이 독립적으로 수행될 수 있도록 다른 트랜잭션의 중간 연산 결과에 서로 접근하지 못하게 한다.

  [4] 지속성(Durability) : 영속성이라고도 하는데 트랜잭션이 성공적으로 완료된 후 데이터베이스에 반영된 수행 결과는 어떠한 경우에도 손실되지 않고 영구적이어야 함을 의미한다.

  즉, 시스템에 장애가 발생하더라도 트랜잭션 작업 결과는 없어지지 않고 데이터베이스에 그대로 남아 있어야 한다는 의미이다.

  그러므로 트랜잭션의 지속성을 보장하려면 시스템에 장애가 발생했을 때 데이터베이스를 원래 상태로 복구하는 회복 기능이 필요하다.

  원자성과 지속성의 공통점은 장애가 발생했을 때 데이터베이스를 원래 상태로 복구하는 회복 기능이 필요하다.

  트랜잭션의 상태

  트랜잭션은 아래의 그림처럼 5가지 상태 중 하나에 속하게 된다.

  

  1. 활동 상태(Active) : 트랜잭션이 수행되기 시작하여 현재 수행 중인 상태를 말한다.

  2. 부분 완료 상태(Partially committed) : 트랜잭션의 마지막 연산이 실행된 직후의 상태를 말한다. 모든 연산의 처리가 끝났지만 트랜잭션이 수행된 최종 결과를 DB에 아직 반영하지 않은 상태이다.

  3. 완료 상태(Committed) : 트랜잭션이 성공적으로 완료되서 commit 연산을 실행한 상태를 말한다. 트랜잭션이 수행한 최종 결과를 DB에 반영하고 종료된다.

  4. 실패 상태(Failed) : H/W 혹은 S/W의 문제, 트랜잭션의 내부의 오류 등 여러 이유로 인해 장애가 발생하여 트랜잭션의 수행이 중단된 상태를 말한다. 더는 정상적으로 수행할 수 없을 때 실패 상태가 된다.

  5. 철회 상태(Aborted) : 트랜잭션을 수행하는 데 실패하여 rollback 연산을 실행한 상태를 말한다. 철회 상태가 되면 지금까지 실행한 트랜잭션의 연산을 모두 취소하고 트랜잭션이 수행되기 전의 DB 상태로 되돌리면서 트랜잭션이 종료된다.

  ---

  예상 질문

  • 트랜잭션이란 무엇인가요?

  • 트랜잭션의 특성 4가지에 대해 설명해 주세요.

  • 트랜잭션의 상태 5가지에 대해 설명해 주세요.

  Read All

  ---

• [DB] 트랜잭션 격리 수준

  2023-02-20

  devFancy

  Database
  • Prologue
  • 격리성
  • 격리 수준에 따라 발생하는 현상
    • 더티 리드
    • 반복 가능하지 않은 조회
    • 팬텀 리드
  • 격리 수준
    • 격리 수준의 필요성
    • READ_UNCOMMITTED
    • READ_COMMITTED
    • REPEATABLE_READ
    • SERIALIZABLE
  • 예상 질문
  • Reference

  Prologue

  • 이전 트랜잭션의 ACID 특성 중 한 가지인 격리성에 대해 조금 더 깊게 공부하기 위해 해당 포스트를 작성하게 되었다.

  격리성

  • 트랜잭션의 특성 중 한 가지인 격리성(Isolation)은 현재 수행 중인 트랜잭션이 완료될 때까지 트랜잭션이 생성된 중간 연산 결과에 다른 트랜잭션들이 접근할 수 없음을 의미한다.

  • 격리성은 여러 개의 격리 수준으로 나뉘어 격리성을 보장한다.

  • 격리 수준은 아래와 같이 4개가 있다.

  

  • 위로 갈수록 동시성이 강해지지만 격리성은 약해지고, 아래로 갈수록 동시성은 약해지지만 격리성은 강해진다.

  • 또한 각 단계마다 나타나는 현상이 있다.

    • READ_UNCOMMITTED - 팬텀 리드, 반복 가능하지 않는 조회, 더티 리드가 발생할 수 있다.

    • READ_COMMITTED - 팬텀 리드, 반복 가능하지 않는 조회가 발생한다.

    • REPEATABLE_READ - 팬텀 리드가 발생한다.

  격리 수준에 따라 발생하는 현상

  • 격리 수준에 따라 발생하는 현상은 더티 리드, 반복 가능하지 않는 조회, 팬텀 리드가 있다.

  더티 리드

  • 더티 리드(Dirty Read)는 반복 가능하지 않은 조회와 유사하며 한 트랜잭션이 실행 중일 때 다른 트랜잭션에 의해 수정되었지만 아직 ‘커밋되지 않은’행의 데이터를 읽을 경우 발생한다.

  • 예를 들어 사용자 A의 계좌(A 트랜잭션)가 $100을 $0으로 변경한 내용이 아직 커밋되지 않은 상태라도 그 이후에 사용자 B가 조회했을 때 결과가 $0으로 나온 경우를 말한다.

  • 만약 수정한 트랜잭션 A가 그 변경 사항을 롤백하면, 그 데이터를 읽은 다른 트랜잭션 B가 더티 데이터를 가지고 있다고 말한다.

  반복 가능하지 않은 조회

  • 반복 가능하지 않은 조회(Non-Repeatable Read)는 한 트랜잭션 내의 같은 행에 두 번 이상 조회가 발생했는데, 그 값이 다른 경우를 가리킨다.

  • 예를 들어 팬시의 계좌가 1번인 잔고 안에 $100가 들어 있다.

    처음에 계좌 1번의 데이터를 읽으면, $100를 읽게 된다.

    하지만 이 때 팬시가 계좌가 1번인 잔고에서 $10을 다른 계좌로 송금했다.

    그러면 두 번째로 계좌 1번의 데이터를 읽을 때에는 $90를 읽게 된다.

  • 이처럼 한 트랜잭션 내에서 같은 Key를 가진 Row를 두 번 읽었는데 그 사이에 값이 변경되거나 삭제되어 결과가 다르게 나타나는 현상을 말한다.

  팬텀 리드

  • 팬텀 리드(Phantom Read)는 한 트랜잭션 내에서 동일한 쿼리를 보냈을 때 해당 조회 결과가 다른 경우를 말한다.

  • 다른 트랜잭션 의한 변경 사항으로 인해 현재 사용중인 트랜잭션의 Where 절의 조건에 맞는 새로운 행이 생길 수 있는 경우에 관한 것이다.

  • 예를 들어, 팬시의 잔고가 $100 미만인 계좌가 2개인 DB에서

    $100 미만인 계좌를 찾는 트랜잭션이 있고, 그 트랜잭션안에서 Select 쿼리를 2번 수행한다고 가정하자.

    처음에 데이터를 읽으면 2개의 계좌를 찾게 된다.

    하지만 이 때 다른 트랜잭션에서 $0인 계좌를 새로 만들고 난 이후에

    두 번째 데이터를 읽을 때에는 3개의 계좌를 찾게 된다.

  • 이처럼 Where 절의 조건에 맞는 새로운 행이 생길 수 있는 경우를 말한다.

  격리 수준

  

  • 위의 표에서 알 수 있듯이 엄격해질수록 이상 현상을 허용하지 않는다.

  • 격리 수준은 세 가지 이상 현상을 정의한 뒤 어떤 현상을 허용/허용하지 않는지에 따라 격리 수준이 나뉜다.

  • 개발자는 이 격리 수준을 통해 전체 처리량(Throughput)과 데이터 일관성 사이에서 trade 할 수 있다.

  격리 수준의 필요성

  • DB는 데이터 무결성을 보장하는 것이 중요하다. 데이터 무결성은 데이터의 정확성과 일관성을 유지하고 보증하는 것을 말한다.

    그리고 그 무결성을 보장하기 위한 특징이 ACID(Atomicity, Consistency, Isolation, Durability)이다.

    데이터베이스는 ACID 특징과 같이 트랜잭션이 독립적인 수행을 하도록 한다. 그래서 등장한 개념이 Locking이다.

  • Locking은 트랜잭션이 DB를 다루는 동안 다른 트랜잭션이 관여하지 못하게 막는 역할이다.

    하지만 무조건적인 Locking으로 동시에 수행되는 수많은 트랜잭션들을 순서대로 처리하면 DB의 성능은 현저히 떨어지게 될 것이다.

    그렇다고 해서 성능을 높이기 위해 Locking 범위를 줄인다면, 잘못된 값이 처리될 수 있다.

    그래서 최대한 효율적인 Locking 방법이 필요하다.

  • 이와 관련된 Locking 방법이 격리 수준(Isolation Level)이다.

  READ_UNCOMMITTED

  • 가장 낮은 격리 수준으로, 하나의 트랜잭션이 커밋되기 이전에 다른 트랜잭션에 노출되는 문제가 있지만 가장 빠르다.

  • 이는 데이터 무결성을 위해 되도록이면 사용하지 않는 것이 이상적이나, 몇몇 행이 제대로 조회되지 않더라도 괜찮은 거대한 양의 데이터를 어림잡아 집계하는 데는 사용하면 좋다.

  • 발생할 수 있는 문제

    • Phantom Read

    • Non-Repeatable Read

    • Dirty Read

  READ_COMMITTED

  • 가장 많이 사용하는 격리 수준이며, PostgreSQL, SQL Server, 오라클에서 기본값으로 설정되어 있다.

  • READ_UNCOMMITTED 와 달리 다른 트랜잭션이 커밋 되지 않은 정보는 읽을 수 없다.

    즉, 커밋 완료된 데이터만 조회를 허용한다.

  • 하지만, 어떤 트랜잭션이 접근한 행을 다른 트랜잭션이 수정할 수 있다.

    예를 들어 트랜잭션 A가 수정한 행을 트랜잭션 B가 수정할 수 있다.

  • 발생할 수 있는 문제

    • Phantom Read

    • Non-Repeatable Read

  REPEATABLE_READ

  “REPEATABLE READ: This is the default isolation level for InnoDB.” - MySQL 공식문서 -

  • MySQL의 InnoDB엔진의 기본 격리수준으로, 하나의 트랜잭션이 수정한 행을 다른 트랜잭션이 수정할 수 없도록 막아주지만 새로운 행을 추가하는 것은 막지 않는다.

    따라서 이후에 추가된 행이 발견될 수 있다.

  • 발생할 수 있는 문제

    • Phantom Read

  SERIALIZABLE

  • 말 그대로 트랜잭션을 순차적으로 진행시키는 것을 말한다.(직렬화)

    여러 트랜잭션이 동시에 같은 행에 접근할 수 없다.

    이 수준은 매우 엄격한 수준으로 해당 행에 대해 격리시키고, 이후 트랜잭션이 이 행에 대해 일어난다면 기다려야 한다.

    그렇기 때문에 교착 상태가 일어날 확률도 많고 가장 성능이 떨어지는 격리수준이다.

  교착 상태(Dead Lock)란 두 트랜잭션이 각각 Lock을 설정한 다음 서로의 Lock에 접근하여 값을 얻어오려고 할 때 이미 각각의 트랜잭션에 의해 Lock이 설정되어 있기 때문에 양쪽 트랜잭션 모두 무한정 기다려야 하는 상태를 말한다.

  • 발생할 수 있는 문제 X

  예상 질문

  • 트랜잭션 격리 수준이 필요한 이유는 무엇일까요?

  • 트랜잭션 격리 수준에 대해 설명해 주세요.

  • 트랜잭션 격리 수준에 따라 발생하는 현상에 대해 설명해 주세요.

  Reference

  • 면접을 위한 CS 전공지식 노트

  • [DB] 트랜잭션과 격리성

  • 트랜잭션 고립화 레벨

  • 트랜잭션 격리 수준

  • 트랜잭션 - Isolation level(격리 수준)과 이상 현상

  Read All

  ---