NLP

자연어 처리에서 데이터 수집이 진행되었다면, 대부분이 정제되지 않은 텍스트 형태일 것이다. 그런 상태에서 분석을 수행하기 위해선 주어진 텍스트 데이터들을 토큰화 & 정규화 & 정제 하는 업무를 수행해야만 한다.

토큰화부터 차차 학습을 해보자.

• Word Tokenization 토큰의 기준을 단어로 하는 경우, 단어 토큰화라고 한다. 다만 여기서의 word는 단어를 포함하여 단어구, 의미를 갖는 문자열로도 간주된다.
  토큰화의 예시로는 마침표(.), 컴마(,), 물음표(?), 세미콜론(;), 느낌표(!) 등과 같은 기호와 띄어쓰기 공백을 제거하는 경우들도 포함한다. 그러나, 구두점, 특수문자를 전부 제거하면 토큰 자체가 가지는 의미를 잃어버리는 경우도 있어서 문제가 될 수 있고, 특히 한국어의 경우 띄어쓰기 단위로 자르는 영어와 달리 의미가 달라질 수도 있기에 주의해야 한다.
  NLTK 라이브러리에서 WordPunctTokenizer는 구두점을 별도로 분류하는 특징을 가지고 있다.
  주의 사항은 다음과 같다.

1. 구두점이나 특수 문자를 단순 제외해서는 안 된다.
2. 줄임말과 단어 내 띄어쓰기가 있는 경우 (New York)
   nltk 라이브러리를 기준으로 함수들을 살펴보면 다음과 같다.

• work_tokenize : Don't를 Do와 n't로 분리.
• WordPunctTokenizer().tokenize() : 구두점을 별도로 분류하는 특징. Don't를 Don과 't로 분리.

  from nltk.tokenize import TreebankWordTokenizer
  >
  tokenizer = TreebankWordTokenizer()
  >
  text = "Starting a home-based restaurant may be an ideal. it doesn't have a food chain or restaurant of their own."
  print('트리뱅크 워드토크나이저 :',tokenizer.tokenize(text))
  트리뱅크 워드토크나이저 : ['Starting', 'a', 'home-based', 'restaurant', 'may', 'be', 'an', 'ideal.', 'it', 'does', "n't", 'have', 'a', 'food', 'chain', 'or', 'restaurant', 'of', 'their', 'own', '.']

  문장을 토큰화하는 방법 : sent_tokenize
  한국어의 경우 문장 토큰화를 진행할 경우, 박상길님이 개발한 KSS (Korean Sentence Splitter)를 대부분 추천한다.
  영어의 경우, New York과 같은 합성어, he's와 같이 줄임말에 대해 예외처리를 하면, 띄어쓰기 토큰화를 수행해도 매우 잘 작동하는 것을 알 수 있다. 하지만, 띄어쓰기 단위가 되는 단위인 '어절' 토큰화를 한국어 NLP에선 적용이 힘들다. 그 이유는 한국어가 교착어(조사, 어미 등을 붙여서 말을 만드는 단어)이기 때문이다.
  한국어 토큰화를 진행하기 위해선 형태소란 개념을 반드시 이해해야 한다. 형태소는 2가지 종류가 있는데, 자립 형태소와 의존 형태소가 있다.
• 자립 형태소 : 접사, 어미, 조사와 상관없이 자립하여 사용할 수 있는 형태소.
• 의존 형태소 : 다른 형태소와 결합하여 사용되는 형태소, 조사, 어미, 어간을 말한다.
  OKT 형태소 분석기로 토큰화를 시도할 경우, morphs (형태소 추출), pos(Part-of-speech tagging) 폼사 태깅, nouns(명사 추출)
  OKT외에도 kkma 형태소 분석기가 존재하는데, 어떤 형태소 분석기를 선택하느냐는 사용자의 판단이 중요하다.

코퍼스에서 용도에 맞게 토큰을 분류하는 작업을 토큰화라고 하며, 토큰화 작업을 하기 전/후로 텍스트 데이터를 용도에 맞게 정제/정규화 하는 일을 항상 함께한다.

• 정제 : 갖고 있는 코퍼스로부터 노이즈 데이터를 제거한다.
• 정규화 : 표현 방법이 다른 언어들을 통합시켜 같은 단어로 만들어준다.

1. 대/소문자 통합
2. 규칙에 기반한 표기가 다른 단어 통합 (usa, us), (uk, england)
3. 불필요 단어 제거 (등장 빈도가 적거나 길이가 짧은 단어 등)
4. 정규 표현식

단어의 개수를 줄일 수 있는 기법.

1. 표제어 추출 (Lemmatization)
   be 동사 (am, are, is) 등. 단어의 형태학적 파싱을 먼저 진행하여 형태소의 종류인 어간과 접사로 단어를 분류하는 기법. (nltk - WordNetLemmatizer)

2. 어간 추출 (Stemming)
   어간을 추출하는 작업으로 어간이란, 단어의 의미를 담고 있는 핵심적인 부분을 의미한다.

   electricical -> electric || formalize -> formal

   그러나, 이러한 알고리즘을 사용했을 때 지나친 일반화가 발생할 수 있다.

한국어에서의 어간 추출

이 중 용언에 해당되는 동사와 형용사는 어간과 어미의 결합으로 구성된다.

활용이란 용언의 어간과 어미를 가지는 일을 말한다.

어간 : 용언을 활용할 때 원칙적으로 모양이 변하지 않는 부분. 어미에 선행하는 부분, 때론 어간의 모양도 바뀔 수 있다. 어미 : 용언의 어간 뒤에 붙어서 활용하면서 변하는 부분이며 여러 문법적 기능을 수행한다. 활용은 어간이 어미를 취할 때 어간의 모습이 일정하다면 규칙 활용, 어간이나 어미의 모습이 변하는 불규칙 활용으로 나뉜다.

불용어의 경우 개발자가 직접 지정하여 제거할 수 있다. stop_words = " ~ " 지정한 후, set 처리하여 텍스트 데이터가 포함되면 제거하도록 처리할 수 있다.

정규표현식 모듈 함수 및 문법 설명 참고 https://wikidocs.net/21703

올해 목표로 잡았던 책 50권 읽기를 성실히 수행 중인 1月 중순이다. 커리어 발전을 위한 SQL 튜닝 책도 열심히 보면서 틈틈이 공부 중이고, 투자 책도 열심히 읽고 있다. 요즘 친구들을 만나서 여러 이야기들을 나누다 보면 다들 직장을 다니면서 이제 돈도 벌고 있고 연애도 하면서 사회 구성원으로 생활을 하고 있다. 친구들을 만나면 가장 많이 나누는 이야기는 커리어 발전과 투자, 그리고 당연히 연애다.

그 중에서도 나는 오늘 커리어 발전을 주제로 이야기를 작성해보고자 한다. "어떤 식으로 커리어 발전을 이루어야 할까?"

책을 읽다보면, 성공의 공식과도 같던 과거와는 달리 이제는 롤모델이 사라지고 있는 추세며 자기계발 코드가 달라졌다고 한다.

맞는 말이다. 고등학교를 지나 상위권 대학을 가고, 자격증을 따서 대기업에 취직하여 남들보다 빠르게 승진하는 것이 목표였다.

그러나 지금 친구들과 이야기를 나누어보면, 이걸 넘어선 자기계발의 방식에 대한 고민들을 토로한다. 가장 '나다운' 성공이 무엇일까

책에서는 3가지를 이야기하고 있다.

첫째, 성공의 기준이 모두 다르므로 내가 생각하는 성공이 무엇인지에 대한 주관식 형태의 답변을 해야 한다. 둘째, 장기적인 목표가 아닌 눈 앞에 보이는 실천 가능한 한 가지에 집중하자. 셋째, 일상의 노력을 기록하고 그것을 주변 사람과 공유하는 습관을 들이자.

솔직히 마지막은 잘 모르겠으나, 첫번째 질문에 답을 하려면 나를 발견하는 과정이 중요하다고 생각한다. 내가 무엇에 강점이 있지?도 한 부분이 될 수 있겠지만, 내가 잘하는게 무엇일까를 찾는 것이 더 효율적이라고 생각이 든다. 나는 나에게 맞는 포인트를 찾아야 전문 분야를 더욱 키울 수 있다고 생각한다.

요새 기업들도 이에 발맞춰 컬쳐핏 면접을 보기도 하고, 개개인의 역량을 확인할 수 있도록 컨설팅 서비스가 주를 이루고 있다. 그렇기에 더더욱 '나를 발견하는 과정'은 더욱 중요한 시대가 되었다고 생각한다.

두 번째로, 눈 앞에 보이는 목표를 달성하자 역시 200% 동감하는 내용이다. 모두에게나 시간과 노력은 한정되어 있다. 그렇기에 인생에서 효율성이 중요하지 않을 수 없다. 장기적인 목표를 세우는 것도 좋다. 그러나, 장기적인 목표를 세우기 위해서 단계별로 눈 앞에 보이는 목표를 설정해 한 걸음씩 나가는 방식이 더 효율적이라고 생각한다. 현재 세계 최고의 야구선수가 된 오타니를 예시로 구속 160이라는 큰 목표를 달성하기 위해 그는 9가지의 세부적인 목표를 담은 만다라트를 작성했었다.

뭐든 하면 된다. 단, 열심히 해야 한다. 내가 요새 매력을 느끼는 문구가 있다. 진인사 대천명 : 모든 일에 최선을 다하고 나머지는 하늘에 맡긴다.

맞는 말이다. 내가 올해 책 50권 읽기를 목표로 잡은 이유는, 생각하는 것에 비해 언어가 부족하다는 생각이 들었고, 책을 통해 맞는 말을 더욱 가슴에 새길 수 있다고 생각해서 이다. 커리어 발전을 위한 기술적인 책도 좋고, 투자 공부를 하기 위한 책도 좋고 개인이 내적으로 성장할 수 있는 자기계발서도 좋다. 하면 된다. 먼 미래를 위해 책을 읽어서 지식을 쌓아가보자.

3.1 ✅ 테이블 액세스 최소화

인덱스를 활용하면 대량의 데이터를 조회해도 금방 데이터를 조회할 수도 있고, 오히려 테이블 전체를 스캔할 때보다 느릴 때도 있다. 이러한 이유에 대해서 알아보자.

SQL이 참조하는 컬럼을 인덱스가 모두 포함하는 경우가 아니면, 인덱스를 스캔한 이후 테이블을 스캔하도록 반드시 설정이 되어있다.

1. 인덱스 ROWID는 물리적 주소? 논리적 주소?

-> 결과부터 이야기하면 인덱스 ROWID는 논리적 주소에 가깝다. 물리적(데이터파일 번호, 오브젝트 번호, 블록 번호 와 같은 물리적 요소)으로 직접 연결되지 않고 디스크 상에서 테이블 레코드를 찾기 위한 위치 정보만을 담는다.

우리가 표현하기 쉽도록 포인터라고 지칭하지 실제로 인덱스 ROWID는 포인터에 해당되지 않는다. 잘못된 표현이다. 또한, 인덱스 ROWID는 물리적으로 테이블과 직접 연결되어 있지도 않기에 무조건 논리적 주소라고 지칭하는 것이 맞다.

※ ** 포인터 : 메모리 주소값을 담는 변수 **

메인 메모리 DB : 데이터를 모두 메모리에 로드해놓고 메모리를 통해서만 I/O를 수행하는 DB

잘 튜닝된 OLTP라면, 디스크를 경유하지 않고 대부분 데이터를 메모리에서만 읽기 때문에 버퍼캐시 히트율이 99% 이상이다. A라는 메인 메모리 db의 경우 인스턴스 기동 시 디스크에 저장된 데이터를 버퍼캐시로 로딩하고 이어서 인덱스를 생성한다. 이때 인덱스는 메모리상의 주소 정보, 즉 포인터를 갖기에 테이블을 액세스하는 비용이 매우 낮다. 그렇기에 메인 메모리 DB에 비해 일반 DBMS에서 인덱스 ROWID를 이용한 테이블 액세스가 생각만큼 빠르지가 않다.

결과적으로 I/O 성능을 높이려면 버퍼캐시를 활용해야 한다.

정리하면, 해싱 알고리즘으로 버퍼 헤더를 찾고, 그때 얻은 포인터로 버퍼 블록을 찾아간다.

디스크 DB가 사용하는 ROWID는 우편주소에, 메인 메모리 DB가 사용하는 포인터를 전화번호에 비유할 수 있다.

이 말의 뜻은, 디스크 DB가 메인 메모리 DB에 비해 현저히 느리다는 것을 알 수 있다.

3.1.2 🧨 인덱스 클러스터링 팩터

CF (Clustering Factor)는 군집성 계수라고 번역할 수 있고, 특정 컬럼을 기준으로 같은 값을 갖는 데이터가 모여있는 정도를 의미한다. 특정 컬럼을 기준으로 데이터가 물리적으로 근접해있으면 흩어져 있을 때보다 데이터를 찾는 속도가 빠르다. (검색 효율이 좋다)

이는, 테이블 액세스량에 비해 블록 I/O가 적게 발생함을 의미한다.

인덱스 손익분기점 : Index Range Scan에 의한 테이블 액세스가 Table Full Scan보다 느려지는 지점

Table Full Scan을 성능이 항상 일정한 반면, Index Range Scan의 경우 조회해야 할 데이터가 일정량을 넘어가는 순간 더 느려지는 지점이 존재한다.

1. Table Full Scan은 시퀀셜 액세스인 반면, 인덱스 ROWID를 이용한 테이블 액세스는 랜덤 액세스 방식이다.
2. Table Full Scan은 Multiblock I/O인 반면, 인덱스 ROWID를 이용한 테이블 액세스는 Single Block I/O 방식이다.
   알아두기... 만 건만 넘어가도 그냥 Table Full Scan 방식으로 읽는 게 더 빠를 수 있다. 대량 데이터를 빠르게 처리하기 위해선 인덱스와 NL조인보다 Full Scan과 해시 조인이 더 유리하다.

   3.1.4 🧨 인덱스 컬럼 추가

   테이블 액세스 최소화를 위해 가장 일반적으로 사용하는 튜닝 기법은 인덱스에 컬럼을 추가하는 것이다. 인덱스에 조건절에 사용된 컬럼을 추가하여 컬럼을 만든다면, 불필요한 테이블 액세스를 크게 줄일 수 있다.

   3.1.6 🧨 인덱스 구조 테이블

   랜덤 액세스가 아예 발생하지 않도록 테이블을 인덱스 구조로 생성하는 방식.
   Oracle : IOT(Index-Organized Table) MSSQL : 클러스터형 인덱스 (Clustered)
   테이블을 찾기 위해 ROWID를 갖는 일반 인덱스와 달리 IOT는 그 자리에 테이블 데이터를 갖는다. 즉, 테이블 블록에 있어야 할 데이터를 인덱스 리프 블록에 모두 저장하고 있다. IOT는 인위적으로 CF를 좋게 만드는 방법 중 하나이다. 같은 값을 가지는 레코드들이 100% 정렬된 상태로 모여 있기에 랜덤 액세스가 아닌 시퀀셜 방식으로 데이터를 액세스하기 때문이다.
   이 때문에 BETWEEN이나 부등호 조건으로 넓은 범위를 읽을 때 유리하다.
   오라클의 클러스터 테이블은 인덱스 클러스터와 해시 클러스터로 나뉜다.
   인덱스 클러스터 테이블은 클러스터 키 값이 같은 레코드를 한 블록에 모아서 저장하는 구조이다. 한 블록에 모두 담을 수 없다면 새로운 블록에 할당하여 클러스터 체인으로 이를 연결한다.
   여러 테이블을 같은 블록에 저장할 때는 다중 테이블 클러스터 라고 부른다.
   명칭 때문에 MSSQL 서버에서 말하는 클러스터형 인덱스와 같다 생각할 수도 있겠지만, 클러스터형 인덱스는 오히려 IOT와 가깝다. 클러스터 테이블은 정렬까지 수행하진 않기 때문이다.
   해시 클러스터 테이블의 경우는 인덱스를 사용하지 않고 해시 알고리즘을 사용해 클러스터를 찾아간다는 점만 다르다.
   인덱스 선행컬럼이 반드시 조건 절에 있어야 한다. EX) 인덱스 조건이 C1_C2_C3_C4 컬럼일 때, 아래와 같이 SQL을 작성했다고 하자.

   SELECT *
   FROM TABLE
   WHERE C1 = 'A'
   AND C2 = 'B'
   AND C4 <= 3

   이럴 경우 선행 컬럼인 C3가 조건절에 없기 때문에 더 많은 레코드를 조회하게 되는 불상사가 일어날 수 있다.

2.3 💡 인덱스 확장 기능 사용법

첫 번쨰로 학습할 내용은 Index Range Scan이다.

2.3.1. ✍️ Index Range Scan

B Tree 인덱스의 가장 일반적이고 정상적인 형태의 액세스 방식이다. 인덱스 루트에서 리프 블록까지 수직적으로 탐색한 이후, 필요한 범위만 스캔한다.

단, 인덱스를 Range Scan하려면 선두 컬럼을 가공하지 않은 상태로 조건 절에 사용해야 한다.

2.3.2. ✍️ Index Full Scan

수직적 탐색없이 인덱스 리프 블록을 처음부터 끝까지 수평적으로 탐색하는 방식

Index Full Scan은 대개 데이터 검색을 위한 최적의 인덱스가 없을 때 차선으로 선택된다.

데이터 저장 공간은 가로x세로 즉, 컬럼 길이 x 레코드 수에 의해 결정되므로 인덱스가 차지하는 면적은 테이블보다 훨씬 적다.

만약 인덱스 스캔 단계에서 대부분 레코드를 필터링하고 아주 일부만 테이블을 액세스하는 상황이라면 면적이 큰 테이블보다 인덱스를 스캔하는 쪽이 유리하다. -> 그럴 때 옵티마이저는 Index Full Scan 방식을 선택한다.

2.3.3. ✍️ Index Unique Scan

수직적 탐색으로만 데이터를 찾는 스캔 방식으로서 Unique 인덱스를 '=' 조건으로 탐색하는 경우에 작동한다.

2.3.4. ✍️ Index Skip Scan

인덱스 선두 컬럼을 조건절에 사용하지 않으면 옵티마이저는 기본적으로 Table Full Scan을 선택한다. Table Full Scan보다 I/O를 줄일 수 있거나 정렬된 결과를 쉽게 얻을 수 있다면 Index Full Scan을 사용하기도 한다.

이 스캔 방식은 조건절에 빠진 인덱스 선두 컬럼의 Distinct Value 개수가 적고 후행 컬럼의 Distinct Value 개수가 많을 때 유용하다.

ex) Distinct Value가 적은 컬럼은 성별, 많은 컬럼은 고객 ID 등이다.

2.3.5. ✍️ Index Fast Full Scan

기존 Index Full Scan보다 빠른 이유는 논리적인 인덱스 트리 구조를 무시하고 인덱스 세그먼트 전체를 Multi Block I/O방식으로 스캔하기 때문이다.

Index Full Scan과의 차이점은 다음과 같다.

1. Index Full Scan

• 인덱스 구조를 따라 스캔
• 결과집합 순서 보장
• Single Block I/O
• (파티션 돼 있지 않다면) 병렬 스캔 불가
• 인덱스에 포함되지 않은 컬럼 조회 시에도 사용 가능

2. Index Fast Full Scan

• 세그먼트 전체를 스캔
• 결과집합 순서 보장 안 됨
• Multi Block I/O
• 병렬 스캔 가능
• 인덱스에 포함된 컬럼으로만 조회할 때 사용 가능

  2.3.6. ✍️ Index Range Scan Descending

  Index Range Scan과 동일한 스캔 방식으로 인덱스 루트에서 리프 블록까지 수직적으로 탐색하고 필요한 범위만 스캔하되, 인덱스를 뒤에서부터 앞쪽으로 스캔하기 때문에 내림차순으로 정렬된 결과 집합을 얻는다.

2.1 💡 인덱스 구조 및 탐색

데이터를 찾는 방식은 크게 2가지 방법이 있다.

• 테이블 전체를 스캔하는 방법
• 인덱스를 이용하는 방법
  테이블 전체 스캔과 관련해서는 튜닝 요소가 많지 않으나, 인덱스와 관련해서는 튜닝 요소가 매우 많고 기법 또한 다양하다.

  ✅ 인덱스 튜닝의 두 가지 핵심 요소.

  인덱스는 주로 테이블에서 소량 데이터를 검색할 때 사용한다. 특히 OLTP 시스템에서 소량 데이터를 주로 탐색하므로 인덱스 튜닝이 가장 중요하다.
  핵심요소는 크게 2가지이다.

1. 인덱스 스캔 효율화 튜닝 : 인덱스 스캔 과정에서 발생하는 비효율을 줄이는 것
2. 랜덤 액세스 최소화 튜닝 : 테이블 액세스 횟수를 줄이는 것 (인덱스 스캔 후 테이블 레코드를 읽을 때 랜덤 I/O 방식을 사용하므로)
   둘 중 성능에 미치는 영향이 더 큰 것은 랜덤 액세스 최소화 튜닝이다.
   1절부터 강조하는 것 중 하나이다. 바로, DB 성능이 느린 이유는 디스크 I/O 때문이다. 읽어야 할 데이터가 많고, 그 과정에 디스크 I/O가 많이 발생할수록 느릴 수 밖에 없다. 인덱스를 많이 사용하는 OLTP일수록 디스크 I/O 중에서도 랜덤 I/O가 특히 중요하다.

   2.1.2. ✍️ 인덱스 구조

   인덱스는 대용량 테이블에서 필요한 데이터만 빠르게 효율적으로 액세스하기 위해 사용하는 오브젝트다. 인덱스를 통해 우리는 DB내 일부 데이터만 읽고 멈출 수 있는 작업을 수행할 수 있다. 즉 범위 스캔이 가능하다. 범위 스캔이 가능한 이유는 마찬가지로 인덱스라는 존재가 있기에 데이터가 정렬되어 있기 때문이다.
   DBMS는 일반적으로 B※Tree 인덱스를 이용한다. 루트를 기반으로 브랜치를 거쳐 리프로 펼쳐지는 형태이다.
   이 중에서 루트와 브랜치 블록에는 키 값을 갖지 않는 특별한 레코드인 LMC가 있다. LMC (Leftmost Child) : 자식 노드 중 가장 왼쪽 끝에 위치한 블록
   LMC가 가리키는 주소를 찾아간 블록에는 키값을 갖는 첫 번째 레코드보다 작거나 같은 레코드가 저장되어 있다.
   리프 블록에는 키값 순으로 정렬되어 있을 뿐만 아니라 ROWID 또한 가지고 있어, 인덱스 키값과 ROWID를 기반으로 정렬되어 있다.
   인덱스를 스캔하는 이유는 주어진 범위 내의 데이터를 빨리 찾고 거기서 ROWID를 얻기 위해서이다.
   ROWID는 DBA(데이터 블록 주소)와 로우 번호로 구성되므로 이 값을 알면 테이블 레코드를 찾을 수 있다.

• ROWID : 데이터 블록 주소 + 로우 번호
• 데이터 블록 주소 : 데이터 파일 번호 + 블록 번호
• 블록 번호 : 데이터 파일 내에서 부여한 상대적 순번
• 로우 번호 : 블록 내 순번
  인덱스 탐색 과정은 2가지로 나뉜다.

1. 수직적 탐색 : 인덱스 스캔 시작지점을 찾는 과정
2. 수평적 탐색 : 데이터를 찾는 과정
   우선 수직적 탐색부터 살펴보자..!

   2.1.3. ✍️ 인덱스 수직적 탐색

   정렬된 인덱스 레코드 중 조건을 만족하는 첫 번째 레코드를 찾는 과정.
   인덱스 수직적 탐색은 루트 블록에서 부탁 시작하여 브랜치 블록에 저장된 각 인덱스 레코드는 하위 블록에 대한 주소값을 갖는다.

   2.1.4. ✍️ 인덱스 수평적 탐색

   수직적 탐색을 통해 스캔 시작점을 찾았으면, 찾고자 하는 데이터가 더 나오지 않을 때까지 인덱스 리프 블록을 수평적으로 스캔한다.
   인덱스 리프 블록은 양방향 연결 구조로 되어 있어 서로 앞뒤 블록에 대한 주소값을 갖는다. 인덱스를 수평적으로 탐색하는 이유는, 첫째 조건절을 만족하는 데이터를 모두 찾기 위함이고 둘쨰 ROWID를 얻기 위해서이다.

   2.1.5. ✍️ 결합 인덱스 구조와 탐색

   2개 이상의 컬럼을 결합해서 인덱스를 만들 수도 있다.
   ※ 참고 사항 BTree의 B는 Balanced를 의미한다. (어떤 값을 탐색하더라도 인덱스 루트에서 리프 블록에 도달하기까지 읽는 블록 수가 같음. 따라서 루트 ~ 리프 블록까지의 높이는 항상 같다.)

   2.2 💡 인덱스 기본 사용법

   인덱스를 Range Scan하는 방법을 의미한다.
   그런데, 인덱스를 Range Scan 할 수 없는 순간도 있다.
   "인덱스 컬럼을 가공하면 인덱스를 정상적으로 사용할 수 없다.

-> 인덱스 컬럼을 가공한다면, 인덱스 스캔 시작점을 찾을 수가 없다.

예를 들면 이런 것이다. where nvl(주문수량, 0) < 100

가공하지 않은 주문수량으로 인덱스를 만들었는데, 값이 NULL이면 0으로 치환한 값을 기준으로 100보다 작은 레코드를 찾는 쿼리를 실행하면, 스캔 시작지점을 확인할 수 없기에 테이블을 전체 스캔하게 된다.

또한, 다음 예시는 UNION ALL을 통해 해결할 수 있다

[AS-IS]
SELECT * 
FROM 고객
WHERE 전화번호 IN (:tel_no1, :tel_no2)
>
[TO-BE]
SELECT *
FROM 고객
WHERE 전화번호 =:tel_no1
UNION ALL
SELECT *
FROM 고객
WHERE 전화번호 =:tel_no2

위와 같은 방식으로 수행한다면, 각 브랜치 별로 인덱스 스캔 시작점을 찾을 수 있어 Range Scan이 가능하다.

인덱스를 Range Scan 하기 위한 가장 첫 번째 조건은 인덱스 선두 컬럼이 가공하지 않은 상태로 조건절에 있어야 한다는 사실이다.

그러나 문제는 또 존재한다. 인덱스를 Range Scan한다고 해서 또 성능이 무조건 좋은 건 아니라는 사실이다. 정말이지 반복되는 방식으로 문제가 계속해서 나온다 ㅋㅋㅋㅋ -> 인덱스 Range Scan을 한다의 기준은 인덱스 리프 블록에서 스캔하는 양을 기준으로 결정해야 한다.

추가로, 조건절에 데이터 형변환이 이루어진 경우에도 Range Scan을 할 수 없다. ex) 날짜 = 19981225 (오라클에서는 자동으로 형변환 처리를 해준다고 한다.)

그렇지만, 혹시 모를 문제를 대비하여 날짜나 특정 데이터 형태의 포맷을 정확히 지정해주는 습관이 중요하다. ex) 날짜 = TO_DATE('01-JAN-2018', 'DD-MON-YYYY').

위와 같이 TO_CHAR, TO_DATE, TO_NUMBER와 같은 형변환 함수를 적극적으로 활용하여 조건 절에 입력해 형변환으로 인한 문제가 발생해선 안되도록 해야 한다.

1.3.6. ✍️ Single Block I/O vs Multi Block I/O

지난 번 시간에 데이터 Block은 데이터를 읽고 쓰는 최소 단위라고 정의하였다. 일반적으로 메모리 캐시가 클수록 좋지만 비용과 기술적인 한계로 전체 데이터를 캐시에 전부 적재할 수는 없다. 캐시에서 찾지 못한 데이터 블록은 I/O Call을 통해 디스크에서 DB버퍼캐시로 적재하고서 읽는다. I/O Call 수행 시 한 번에 한 블록 혹은 여러 블록을 요청한다.

이때, 나온 방식이 표제의 건이다. Single Block I/O : I/O Call 요청 시 한 번에 한 블록씩 요청하는 방식 Multi Blcok I/O : 한 번에 여러 블록씩 요청하여 메모리에 적재하는 방식

인덱스는 보통 소량의 데이터를 읽을 때 주로 사용하므로, 기본적으로 인덱스와 테이블 블록 모두 Single Block I/O를 사용한다.

Single Blcok I/O 대상 오퍼레이션

• 인덱스 루트 블록을 읽을 때
• 인덱스 루트 블록에서 얻은 주소 정보로 브랜치 블록을 읽을 때
• 인덱스 브랜치 블록에서 얻은 주소 정보로 리프 블록을 읽을 때
• 인덱스 리프 블록에서 얻은 주소 정보로 테이블 블록을 읽을 때
  이와 반대로, 많은 데이터 블록을 읽을 때는 Multi Block I/O 방식이 효율적이다. 그래서 인덱스를 이용하지 않고 테이블 전체를 스캔할 때 이 방식을 사용한다. 읽고자 하는 블록을 DB 버퍼캐시에서 찾지 못하면 해당 블록을 디스크에서 읽기 위해 I/O Call을 한다. 그동안 프로세스는 대기 큐에서 대기를 한다.

• 대용량 테이블을 Full Scan할 때 Multi Block I/O 단위를 크게 설정하면 성능이 좋아짐.

  정리를 하자면, Multi Block I/O는 캐시에서 찾지 못한 특정 블록을 읽으려고 I/O Call을 할때 디스크 상에서 그 블록과 인접한 블록(같은 익스텐트에 속한 블록)들을 한꺼번에 읽어 캐시에 미리 적재하는 기능.
  결국 Multi Block I/O 방식으로 읽어도 익스텐트 경계를 넘지 못한다.
  오라클에서 한 번 담을 수 있는 양을 조절하는 파라미터는 db_file_multiblock_read_count이다.
  Q. Multi Block I/O 중간에 왜 Single Block I/O가 나타나는가?

• 익스텐트 맵 : 테이블에 대한 인덱스

• Multi Block I/O : 배치 I/O

  배치 단위로 I/O를 수행하게 되면 결국 익스텐트 맵으로 블록 목록을 확인할 것이고, 캐시버퍼 체인에서 찾지 못한 블록들을 Multi Block I/O 방식으로 디스크 I/O Call을 수행할텐데, 이때 여러 개가 아닌 1개의 블록을 대상으로 수행할 떄에는 Single I/O 방식을 채택하게 될 것이다.
• ) Full Scan 중 Chain이 발생한 로우를 읽을 떄에도 Single Block I/O 방식으로 읽는다.

  1.3.7. ✍️ Table Full Scan VS Index Range Scan

  테이블에 저장된 데이터를 읽는 방식은 2가지다. Table Full Scan : 테이블에 속한 블록 전체를 읽어 사용자가 원하는 데이터를 찾는 방식 Index Range Scan (인덱스를 이용한 테이블 액세스) : 인덱스에서 일정량을 스캔하여 얻은 ROWID로 테이블 레코드를 찾는 방식 (ROWID : 테이블 레코드가 디스크 상에서 어디 저장됐는지를 가리키는 정보)
  Table Full Scan 방식은 시퀀셜 액세스와 Multi Block I/O 방식으로 디스크 블록을 읽는다. 한 블록에 속한 모든 레코드를 한 번에 읽어들이고 캐시에서 못찾으면 동일 익스텐트 내 인접한 블록 수십 ~ 수백개를 한꺼번에 I/O 하는 매커니즘이다.
  그러나, 큰 테이블 내에서 소량의 데이터를 검색할 때는 반드시 인덱스를 활용해야 효율적이다.
  당연한 이야기지만, 예시를 들어보면 우리가 사과라는 과일을 살때 주변 마트나 시장을 검색하지 곧바로 트레이더스를 검색하진 않는다.
  반면, Index Range Scan을 통한 테이블 액세스는 랜덤 액세스와 Single Block I/O 방식으로 디스크 블록을 읽는다. 소량의 데이터를 검색할 떄에는 적합하지만, 읽었던 블록을 반복해서 읽게 되는 비효율적인 문제가 존재하긴 한다.
  [개인 견해] 그렇다면 소량이다, 대량이다가 되는 기준이 어떻게 될까? 이건 DB 테이블 내 적재된 데이터의 형태에 따라 상당히 달라진다고 생각한다. 텍스트 형태의 데이터이고 VARCHAR 단위가 3000 가까이 된다면, 이는 로우가 100개에 불과해도 대량 데이터라고 판단할 수 있을 것이다.
  쿼리 툴을 개발한다면, Table Full Scan 뿐만 아니라, 예상 Cardinality가 일정량을 넘어서는데도 인덱스로 테이블을 액세스하는 부분에 표시해주는 기능이 있다면 좋을 것이다.

  1.3.8. ✍️ 캐시 탐색 메커니즘

  DBMS의 버퍼캐시는 해시 구조로 관리된다. 버퍼캐시에서 블록을 찾을 때, 해시 알고리즘을 거쳐 버퍼 헤더를 찾고 거기서 얻은 포인터로 버퍼 블록을 액세스하는 방식을 사용한다.
  해시 구조의 특징은 다음과 같다.

1. 같은 입력 값은 항상 동일한 해시 체인에 연결된다.
2. 다른 입력 값이 동일한 해시 체인에도 연결될 수 있다.
3. 해시 체인 내에서는 정렬이 보장되지 않는다.

   🧨 캐시버퍼 체인 래치

   래치란, 직렬화가 가능하도록 지원하는 메커니즘이다.

   대량의 데이터를 읽을 때 모든 블록에 대해 해시 체인을 탐색한다. DBA를 해시 함수에 입력하고 거기서 반환된 값으로 스캔해야 할 해시 체인을 찾는다. 이때, 다른 프로세스가 체인 구조를 변경한다면, 반환된 값으로 스캔을 못하기에 이를 방지하고자 해시 체인 래치가 존재하게 된다.
   캐시버퍼 체인뿐만 아니라, 버퍼 블록 자체에도 직렬화 메커니즘이 존재하는데, 바로 버퍼 Lock이다. 이런 직렬화 메커니즘에 의한 캐시 경합을 줄이기 위해선 SQL 튜닝을 통해 쿼리 일량(논리적 I/O)를 줄여야만 한다.

1.1 💡 SQL 파싱과 최적화

SQL 튜닝에 앞서 옵티마이저가 어떻게 SQL을 처리하고, 서버 프로세스는 데이터를 어떻게 읽고 저장하는지 살펴보자.

두 테이블을 부서번호로 조인하여 사원명으로 정렬하는 로직.

SELECT E.EMPNO, E.ENAME, E.JOB, E.DEPTNO, D.DNAME, D.LOC
FROM EMP E, DEPT D
WHERE E.DEPTNO = D.DEPTNO
ORDER BY E.ENAME

이렇게 원하는 명령을 DB에 질의하는 것을 쿼리라고 하고 위 단어로 배열된 쿼리를 SQL문이라고 한다. 즉, SQL은 구조적이고 집합적이며 선언적인 질의 언어이고, 이를 만드는 과정은 절차적인 과정을 거칠 수 밖에 없다. 이때 이러한 순차적인 과정을 프로시저라고 칭하고 이러한 프로시저를 생성하는 DBMS 내부 엔진으로 SQL 최적화를 수행하는 것이 SQL 옵티마이저이다.

SQL 최적화 : DBMS 내부에서 프로시저를 작성하고 컴파일해서 실행 가능한 상태로 만드는 전 과정

SQL 최적화 과정을 세분화하면 다음과 같다.

1. SQL 파싱 : 사용자로부터 SQL을 전달받으면 가장 먼저 SQL 파서가 파싱을 진행한다. SQL 파싱은 다음 3개로 요약.

• 파싱 트리 생성 : SQL 문을 이루는 개별 구성요소를 분석해서 파싱 트리 생성
• Syntax 체크 : 문법적 오류가 없는지 확인
• Semantic 체크 : 의미상 오류가 없는지 확인

2. SQL 최적화 : 옵티마이저가 수행하는 것으로, 미리 수집한 시스템, 오브젝트 통계정보를 바탕으로 다양한 실행경로를 생성해서 비교 후 가장 효율적인 하나를 선택한다.

3. 로우 소스 생성 : SQL 옵티마이저가 생성한 실행경로를 실제 실행 가능한 코드 또는 프로시저 형태로 포맷팅하는 단계.

   1.1.4.✍️ SQL 실행계획과 비용

   실행계획 : DBMS에도 SQL 실행경로 미리보기.

-> SQL 옵티마이저가 생성한 처리절차를 사용자가 확인할 수 있게 트리 구조로 표현한 것.

그렇다면 특정 실행계획을 선택하는 근거는 무엇인가? < 테스트용 테이블 >

CREATE table T
AS
SELECT d.no, e.*
FROM scott.emp E
    , (SELECT rownum no FROM dual connect by level <= 1000) d;

SQL※PLUS에서 AutoTrace를 활성화하고 SQL을 실행하면 실행계획을 확인할 수 있다. SQL을 선택하고 Ctrl + E 키를 누르면 됌. 즉, 옵티마이저는 각 인덱스를 선택할 때 추정되는 비용을 근거로 수행한다.

1.1.5.✍️ 옵티마이저 힌트

수동적으로 효율적인 데이터 액세스 경로를 파악하기 위해 사용하는 기법

SELECT /*+ INDEX(A 고객PK) */
    고객명, 고객연락처, 주소, 가입일시
FROM 고객 A
WHERE 고객ID = '00001'

옵티마이저 힌트를 사용할 떄의 주의 사항은 다음과 같다.

1. 힌트 내 , 금지
2. 스키마명 명시 금지
3. ALIAS를 지정한 테이블명을 사용하기.

1.2 💡 SQL 공유 및 재사용

본 절에서는 소프트 파싱과 하드 파싱의 차이를 설명.

SGA (System Global Area) : 서버/백그라운드 프로세스가 공통으로 액세스하는 데이터와 제어 구조를 캐싱하는 메모리 공간 Library Cache : SQL 파싱, 최적화, 로우 소스 생성 과정을 거쳐 생성한 내부 프로시저를 반복 재사용할 수 있도록 캐싱해 두는 메모리 공간

소프트 파싱 : SQL을 캐시에서 찾아 곧바로 실행단계로 넘어가는 것 하드 파싱 : 캐시에서 찾지 못하여 최적화, 로우 소스 생성 단계까지 모두 거치는 것을 하드 파싱이라 함.'

SQL 옵티마이저는 순식간에 수 많은 연산을 수행한다.

• 테이블, 컬럼, 인덱스 구조에 관한 기본 정보
• 오브젝트 통계 : 테이블 통계, 인덱스 통계, (히스토그램을 포함한) 컬럼 통계
• 시스템 통계 : CPU 속도, Single Block I/O 속도, Multiblock I/O 속도 등
• 옵티마이저 관련 파라미터
  하나의 쿼리를 수행하는 데 있어 후보군이 될만한 무수히 많은 실행경로를 도출하고 짧은 순간에 딕셔너리와 통계 정보를 읽어 각각에 대한 효율성을 판단하는 과정은 결코 가벼울 수 없다.
  하드 파싱은 CPU를 많이 소비하는 몇 안되는 작업 중 하나.
  이렇게 하드 파싱을 거쳐 생성한 내부 프로시저를 저장하기 위해 라이브러리 캐시가 필요하다.
  SQL은 영구적으로 보관되지 않고 모든 텍스트가 이름 역할을 하여 라이브러리 캐시에 저장되고 여러 사용자가 이를 공유하며 재사용하게 된다. 만일 캐시 공간이 부족하면 버려 진 후 다음 번에 실행 시 똑같은 최적화 과정을 거쳐 캐시에 적재된다.
  Oracle, MSSQL Server 등에서 SQL을 영구 저장하지 않는 이유는 1개다. 모든 SQL은 변수명만 변해도 새로운 SQL로 처리하기에 모든 SQL을 저장하려면 그만큼 많은 공간이 필요하고 결국 캐싱이라는 의미가 사라지게 된다.
  한 예시로 사용자의 로그인 기능이 있는 쇼핑몰의 경우 특가 행사가 있을 때 사람들이 몰리게 될텐데 일반적인 ID를 받는 식으로 DB를 조회한다면 서버에 부화가 될 가능성이 높다. 그렇기에 ID를 파라미터로 받아 재사용하며 처리하는 기능이 더 효율적인텐데, 이를 바로
• 바인드 변수* 라고 칭한다.

  1.3 💡 데이터 저장 구조 및 I/O 메커니즘

  I/O 튜닝이 곧 SQL 튜닝이라고 해도 과언이 아니다. SQL 작업이 느린 이유는 열이면 열 디스크 I/O 때문이다.
  OS 또는 I/O 서브시스템이 I/O를 처리하는 동안 프로세스(실행 중인 프로그램)는 멈춰있기에 SQL이 느리다. (프로세스는 하나의 CPU를 공유하지만 특정 순간에는 1개의 프로세스만 CPU를 사용할 수 있기 때문이다.)

  1.3.2. 데이터베이스 저장 구조.

  데이터를 저장하려면 우선 테이블스페이스를 생성해야 한다. 테이블스페이스는 여러 세그먼트를 담는 콘테이너로서 여러 개의 데이터 파일(OS파일)로 구성된다.
  세그먼트는 테이블, 인덱스처럼 데이터 저장 공간이 필요한 오브젝트이고 여러 익스텐트로 구성된다.

• ※ (익스텐트는 공간을 확장하는 단위.)
  테이블, 인덱스를 생성할 때 데이터를 어떤 테이블스페이스에 저장할 지를 지정한다.
  정리를 한 번 하자면, 다음과 같다.

1. 데이터를 저장하기 위해선 테이블스페이스를 생성해야 함.
2. 데이터 블록 ㄷ 익스텐트 ㄷ 세그먼트 ㄷ 테이블스페이스 순서로 구성되어 있다.
3. 익스텐트 ㄷ 데이터파일 ㄷ 테이블스페이스, 데이터파일 ㄷ 세그먼트 ㄷ 데이터파일

• 데이터 블록이란, 사용자가 입력한 레코드를 실제로 저장하는 공간 (한 블록은 한 테이블이 독점)
• 익스텐트란 연속된 블록들의 집합, 공간을 확장하는 단위
• 세그먼트란 여러 익스텐트로 구성된 하나의 파티션을 의미
  < 오라클에서 세그먼트에 할당된 익스텐트 목록을 조회하는 방법 >

  SELECT segment_type, tablespace_name, extent_id, file_id, block_id, blocks
  FROM dba_extents
  WHERE owner = USER
  AND segment_name = 'MY_SEGMENT'
  ORDER BY extent_id;

  위 쿼리를 통해 구성된 세그먼트를 DBA_EXTENTS 뷰에서 조회 시 아래와 같은 표가 나온다

이 세그먼트에 할당된 2번 익스텐트는 2번 데이터 파일 1번 블록으로부터 연속된 4개 블록으로 이루어져있다. 바로 뒤에 할당된 3번 익스텐트는 그래서 5번부터 시작한다. 다른 익스텐트들은 직전 인스텐트와 인접하지 않는다.

최종적으로 정리하면 다음과 같아.

• 데이터 블록 (페이지) : 데이터를 읽고 쓰는 단위
• 익스텐트 : 공간을 확장하는 단위, 연속된 블록 집합
• 세그먼트 : 데이터 저장공간이 필요한 오브젝트 (테이블, 인덱스, 파티션, LOB 등)
• 테이블스페이스 : 세그먼트를 담는 콘테이너
• 데이터파일 : 디스크 상의 물리적인 OS파일 ※ 모든 데이터 블록은 디스크 상 자신이 몇 번째 블록인지 나타내는 고유 주소값을 갖는다.
• 인덱스를 이용해 테이블 레코드를 읽을 때는 인덱스 ROWID를 활용.
• 테이블 스캔 시 테이블 세그먼트 헤더에 저장된 익스텐트 맵을 이용.
  테이블과 인덱스는 블록 단위로 데이터를 읽고 쓴다.

  1.3.4. ✍️ 시퀀셜 vs 랜덤 액세스

  테이블 또는 인덱스 블록을 액세스(읽는) 방식은 2가지가 있다.

1. Sequential 액세스 : 논리적, 물리적으로 연결된 순서에 따라 차례대로 블록을 읽는 방식. (인덱스 리프 블록은 앞뒤를 가리키는 주소값을 통해 논리적으로 서로 연결되어 있음.)

-> 이 주소값에 따라 앞/뒤로 순차적으로 스캔하는 방식

테이블 블록 간에는 서로 논리적으로 연결되어 있지 않다. Q. 그렇다면 순차적인 방식을 어떻게 선택하는가? -> 오라클의 경우 익스텐트 목록을 세그멘트 헤더에 맵으로 관리한다.

(익스텐트 맵은 각 익스텐트의 첫 블록 주소 값을 갖는다, 이를 순차적으로 읽으면 Full Table Scan이다.)

2. Random 액세스 : 순서를 따지지 않고 레코드 하나를 읽기 위해 한 블록씩 접근하는 방식.

+) SGA 구성요소 중 하나인 라이브러리 캐시와 DB버퍼캐시가 있다.

라이브러리 캐시가 SQL, 실행계획, DB 저장형 함수/프로시저 등을 캐싱하는 '코드 캐시'라 한다면, DB 버퍼캐시는 '데이터 캐시'라고 한다. -> 어렵게 읽은 데이터 블록을 캐싱해 둠으로써 같은 블록에 대한 반복적인 I/O Call을 줄이기 위함.

논리적 블록 I/O : SQL 처리하는 과정에서 발생한 총 블록 I/O 물리적 블록 I/O : 디스크에서 발생한 총 블록 I/O

결국 물리적 I/O는 논리적 I/O 중 캐싱에서 발견하지 못한 경우에 액세스하는 것.

• 물리적 I/0 = 논리적 I/O * (100%-BCHR)
  논리적 I/O를 줄일 수 있는 방법 : SQL을 튜닝해서 읽는 총 블록 개수를 줄이면 됌.
  최종적으로 논리적 I/O를 줄임으로써 물리적 I/O를 줄이는 것이 곧 SQL 튜닝.

✅ 176. Second Highest Salary.

Employee Table : id | salary.

salary가 2번째로 높은 인원의 salary를 출력하는 문제. 만일 테이블 개수가 1게이면 null이 출력되어야 함.

SELECT MAX(salary) AS SecondHighestSalary
FROM Employee
WHERE salary < (SELECT MAX(salary) FROM SecondHighestSalary)

문제 풀이는 간단하게 생각했다. 테이블을 2개로 만들고 MAX(salary)를 조회한다. 단 앞서 만든 테이블의 MAX(salary)값이 더 커야만 한다.

✅ 1484. Group Sold Products By The Date.

Acitivities : sell_date | product

각 날짜 별로 팔린 물건 수와 각 물건 이름을 나열하는 문제. 이때 물건 이름은 순서대로 정렬할 것. EX) Basketball,Headphone,T-shirt

SELECT
    sell_date,
    COUNT(DISTINCT product) AS num_sold,
    GROUP_CONCAT(DISTINCT product ORDER BY product SEPARATOR ',') AS products
FROM Activities
GROUP BY sell_date
ORDER BY sell_date;

GROUP_CONCAT() 함수를 활용하여 한 열에 저장되어 있는 데이터를 한 행에 있는 데이터로 변경할 수 있다.

알아두면 아주 유용한 함수

✅ 1667. Fix Names in a Table.

Users : user_id | name

Write a solution to fix the names so that only the first character is uppercase and the rest are lowercase.

Return the result table ordered by user_id.

SELECT
    user_id,
    CONCAT(UPPER(SUBSTR(name, 1, 1)), LOWER(SUBSTR(name, 2))) AS name
FROM Users
ORDER BY user_id;

이름의 첫 글자만 대문자, 나머지는 소문자로 표기하기. 방법은 다음과 같다. SUBSTR()로 문자를 우선 구분해주고, 앞 첫 글자만 대문자 처리. UPPER(SUBSTR(name, 1, 1)) 이후 같은 함수를 활용하여 첫 글자를 제외한 나머지를 전부 소문자로 처리한다. LOWER(SUBSTR(name, 2))

✅ 1527. Patients With a Condition

Patients : patient_id | patient_name | conditions

Write a solution to find the patient_id, patient_name, and conditions of the patients who have Type I Diabetes. Type I Diabetes always starts with DIAB1 prefix. Return the result table in any order. The result format is in the following example.

SELECT *
FROM Patients
WHERE 
    conditions LIKE 'DIAB1%'
    OR conditions LIKE '% DIAB1%'

처음에는, DIAB1으로 시작하는 condition을 조회하는 줄 알고 LEFT함수를 썼으나, DIAB1으로 단어가 시작하는 것을 조회해야 했기에, 2가지 케이스를 두고 LIKE를 적용하였다.

✅ 196. Delete Duplicate Emails

Person : id | email

Write a solution to delete all duplicate emails, keeping only one unique email with the smallest id.

DELETE A
FROM Person AS A, Person AS B
WHERE A.email = B.email AND A.id > B.id

한 개의 테이블만 주어진 상황에서, 중복 처리를 위해 동일한 테이블을 2회 불러온다.

이후, A라는 테이블을 지우되, 다음 조건을 만족하는 경우에만 제거한다.

테이블 A와 테이블 B에서 email이 동일하고, 테이블 A의 id가 더 큰 경우 제거를 수행하여, email이 같은 상황에서 더 낮은 id만을 갖는 데이터를 냅둔다.

✅ 185. Department Top Three Salaries.

Employee Table : id | name | salary | departmentId Department Table : id | name

A company's executives are interested in seeing who earns the most money in each of the company's departments. A high earner in a department is an employee who has a salary in the top three unique salaries for that department.

Write a solution to find the employees who are high earners in each of the departments.

Return the result table in any order.

The result format is in the following example.

WITH CTE AS (
    SELECT 
        D.name AS Department,
        E.name AS Employee,
        E.salary AS Salary,
        DENSE_RANK() OVER(PARTITION BY D.name ORDER BY E.salary DESC) AS ranking
    FROM Employee AS E
    JOIN Department AS D ON E.departmentId = D.id
)
>
SELECT 
    Department,
    Employee,
    Salary
FROM CTE
WHERE ranking < 4;

문제 풀이의 핵심은 Ranking 함수를 잘 사용할 줄 아는가이다. 흔히 알고 있는 순위함수란, 결과에 순번을 매기는 것을 의미하고 비집계함수들 중 RANK, NTILE, DENSE_RANK, ROW_NUMBER 등이 존재한다.

순위를 매기는 범주에는 PARTITION BY 와 ORDER BY가 존재하는데, 정의는 다음과 같다.

• PARTITION BY : 동일 그룹으로 묶어줄 컬럼명 지정 시 사용
• ORDER BY : 파티션 정의에 지정된 컬럼에 대해 정렬을 수행할 때 활용.
  또한, 비집계함수 들에 대해 살펴보면 다음과 같다.
• RANK() : 동일 값 포함하여 다음 숫자 산정. EX) 1-2-2-4
• DENSE_RANK() : 동일 값 포함하지 않고 다음 숫자 산정 EX) 1-2-2-3
• ROW_NUMBER() : 값이 같더라도 순위는 상승 EX) 1-2-3-4
• NTILE(PARTITION 수) : 파티션 수만큼 등급을 나누어 각 등급을 부여 EX) 특정 그룹 1, 특정 그룹 2
  따라서, 부서별 순위를 매길 시에는 다음과 같이 사용한다.

  SELECT DENSE_RANK() OVER(PARTITION BY 범위 ORDER BY 정렬기준할컬럼 ASC OR DESC) AS 지정할 컬럼명
  FROM 테이블명

  이와 관련하여, 아래 사이트를 참고하면 좋다 https://jie0025.tistory.com/85 정보 제공해주셔서 감사합니다 :)

✅ 585 Investments in 2016

Write a solution to report the sum of all total investment values in 2016 tiv_2016, for all policyholders who :

• have the same tiv_2015 value as one or more other policyholders, and
• are not located in the same city as any other policyholder (i.e., the (lat, lon) attribute pairs must be unique) Round tiv_2016 to two decimal places The result format is in the following example.

  SELECT ROUND(SUM(tiv_2016), 2) AS tiv_2016
  FROM Insurance
  WHERE tiv_2015 IN (
    SELECT tiv_2015
    FROM Insurance
    GROUP BY tiv_2015
    HAVING COUNT(*) > 1
  ) AND (lat, lon) IN (
    SELECT lat, lon
    FROM Insurance
    GROUP BY lat, lon
    HAVING COUNT(*) = 1
  )

  문제 풀이의 핵심은 다음과 같다.

1. tiv_2015 값이 1개보다 많아야 되는 상황 (as one or more)
2. lat, lon 이 unique한 값이어야 되는 상황
3. 최종적으로 tiv_2016 합산 값을 소수점 둘째 자리로 표현해야 되는 상황.

✅ 1907 Count Salary Categories

+-------------+------+ | Column Name | Type | +-------------+------+ | account_id | int | | income | int | +-------------+------+ account_id is the primary key (column with unique values) for this table. Each row contains information about the monthly income for one bank account. Write a solution to calculate the number of bank accounts for each salary category. The salary categories are: "Low Salary": All the salaries strictly less than $20000. "Average Salary": All the salaries in the inclusive range [$20000, $50000]. "High Salary": All the salaries strictly greater than $50000. The result table must contain all three categories. If there are no accounts in a category, return 0. Return the result table in any order. The result format is in the following example.

SELECT 'Low Salary' AS category, COUNT(IF(income < 20000, 1, NULL)) AS accounts_count FROM Accounts 
UNION ALL
SELECT 'Average Salary' AS category, COUNT(IF(income>=20000 AND income<=50000, 1, NULL)) AS accounts_count FROM Accounts
UNION ALL
SELECT 'High Salary' AS category, COUNT(IF(income > 50000, 1, NULL)) AS acoounts_count FROM Accounts

해당 문제의 핵심은, UNION ALL을 활용한 행 결합과 IF함수를 활용하여 값이 충족되지 않으면 NULL로 처리하는 과정이다.

✅ 626. Exchange Seats

SELECT
    id, 
    CASE
     WHEN MOD(id, 2) = 0 THEN LAG(student) OVER (ORDER BY id) 
     ELSE IFNULL(LEAD(student) OVER (ORDER BY id), student)
    END AS student
FROM Seat

id를 기준으로 연속적인 학생들의 자리를 바꿔준다. 만일, 끝 번호가 홀수인 경우 자리를 바꾸지 않는다.

위 조건을 만족할 수 있도록, CASE 문구를 활용해 조건을 활성화시킨다. 우선 짝수 인원에 대해 이전 id를 가진 학생의 이름을 가져오고, 홀수 인원의 경우 마지막 인원 처리를 위해 IFNULL을 활용한다.

✅ 1341. Movie Rating

Write a solution to:

• Find the name of the user who has rated the greatest number of movies. In case of a tie, return the lexicographically smaller user name.
• Find the movie name with the highest average rating in February 2020. In case of a tie, return the lexicographically smaller movie name. The result format is in the following example.

  WITH CTE AS ((
    SELECT B.name AS name, COUNT(C.rating) as rating
    FROM Users B
    LEFT JOIN MovieRating C ON B.user_id = C.user_id 
    GROUP BY B.name
    ORDER BY rating DESC, name 
    LIMIT 1)
    UNION ALL 
    (SELECT A.title AS name, AVG(rating) as rating
    FROM Movies A
    LEFT JOIN MovieRating C ON A.movie_id = C.movie_id
    WHERE DATE_FORMAT(created_at, '%Y-%m') = '2020-02'
    GROUP BY A.title
    ORDER BY rating DESC, A.title
    LIMIT 1
  ))
  SELECT name AS results
  FROM CTE

  3개의 테이블을 JOIN하여 영화 평가를 가장 많이 한 사람의 이름과, 2020년 2월 평점이 가장 높은 영화 이름을 출력하는 문제.
  편리성을 높히기 위해 CTE 문구로 테이블을 새로 만들고, UNION ALL을 활용해 각각 구해야 하는 답을 테이블로 저장한다.

✅ 1321. Restaurant Growth

• Compute the moving average of how much the customer paid in a seven days window (today + 6 days before) average_amount should be rounded two decimal places.

  SELECT 
    visited_on,
    (
        SELECT SUM(amount)
        FROM Customer
        WHERE visited_on BETWEEN DATE_SUB(A.visited_on, INTERVAL 6 DAY) AND A.visited_on
    ) AS amount,
    ROUND((
            SELECT SUM(amount) / 7
            FROM Customer
            WHERE visited_on BETWEEN DATE_SUB(A.visited_on, INTERVAL 6 DAY) AND A.visited_on
        ), 2) AS average_amount
  FROM Customer AS A
  WHERE visited_on >= (SELECT DATE_ADD(MIN(visited_on), INTERVAL 6 DAY) FROM Customer)
  GROUP BY visited_on
  ORDER BY visited_on;

  핵심 function은 다음과 같다. DATE_ADD/DATE_SUB(컬럼, INTERVAL 수 (일/주/월 등의 기간) EX) DATE_SUB(A.visited_on, INTERVAL 6 DAY)

• 6일 전의 날짜를 의미

  최종적으로, 주어진 테이블 내, 7일 기간을 갖는 최소 날짜를 미리 선정하여 7일 전부터 현재 날짜까지의 amount 합과 평균 amount를 구하면 되는 문제.
  주의할 사항으로는, 각 amount 통계치를 구할 때엔 (7일전 ~ 현재날짜) 기준이고, 최종적인 group by를 갖는 전체 where 절에는, 최소 날짜에서 7일 후를 더한 날짜부터 계산할 수 있도록 필터를 지정해주어야 한다.

✅ 1164. Product Price at a Given Date.

product_id, change_date is the primary key of the below table. +---------------+---------+ | Column Name | Type | +---------------+---------+ | product_id | int | | new_price | int | | change_date | date | +---------------+---------+

Write a sol. to find the prices of all products on 2019-08-16. Assume the price of all products before any change is 10. Return the result table in any order.

# 2019-08-16 이전 최근 날짜 기준 id, price 갖고오기
SELECT product_id, new_price as price
FROM Products
WHERE (product_id, change_date) IN (
    SELECT product_id, MAX(change_date) as date
    FROM Products
    WHERE DATE_FORMAT(change_date, '%Y-%m-%d') <= '2019-08-16'
    GROUP BY product_id
)

UNION

# 2019-08-16 이후는 price 10으로 처리하여 중복제거 병합
SELECT DISTINCT product_id, 10 as price
FROM Products
WHERE product_id NOT IN (
    SELECT DISTINCT product_id
    FROM Products 
    WHERE DATE_FORMAT(change_date, '%Y-%m-%d') <= '2019-08-16'
)

✅ 1204. Last Person to Fit in the Bus.

+-------------+---------+ | Column Name | Type | +-------------+---------+ | person_id | int | | person_name | varchar | | weight | int | | turn | int | +-------------+---------+ person_id column contains unique values. This table has the information about all people waiting for a bus. The person_id and turn columns will contain all numbers from 1 to n, where n is the number of rows in the table. turn determines the order of which the people will board the bus, where turn=1 denotes the first person to board and turn=n denotes the last person to board. weight is the weight of the person in kilograms.

There is a queue of people waiting to board a bus. However, the bus has a weight limit of 1000 kilograms, so there may be some people who cannot board. Write a solution to find the person_name of the last person that can fit on the bus without exceeding the weight limit. The test cases are generated such that the first person does not exceed the weight limit. Note that only one person can board the bus at any given turn.

SELECT person_name 
FROM(
    # 버스를 탑승하는 인원의 이름, 무게, 누적 무게 테이블 생성
    SELECT person_name, weight, sum(weight) OVER (ORDER BY turn) AS cum_weight
    FROM Queue 
    ORDER BY turn) 
WHERE cum_weight <=1000 
ORDER BY cum_weight DESC LIMIT 1;

거의 6개월 간 블로그에 학습한 내용들을 작성하지 않았는데 정말 많은 일들이 있었습니다.

우선, 지난 8월 학사를 졸업한 이후 하반기부터 본격적으로 준비했던 취업에 성공하여 4월 초부터 직장에 다니고 있습니다.

작년 하반기에 저는 무조건 취업에 성공할 줄 알았습니다. 그 이유는 2개 기업을 제외하곤 제출했던 서류는 전부 붙었고 면접도 골라서 10번 넘게 봐왔기 때문이죠. 하지만, 취업의 벽은 제가 생각했던 것보다 훨씬 높았고 타 사람들과 면접 준비 경험도 없이 혼자 면접을 준비했던 탓에 전부 떨어졌다고 생각합니다.
그래서 연말엔 제주도도 여자친구와 다녀오고 일본도 어머니랑 다녀오고 (혼자 거의 돌아다녔지만) 등등 리프레쉬를 다녀오며 스스로를 좀 돌아보는 시간을 많이 가졌습니다. 이후 올해 상반기 이전 진행되는 수시모집에서 올라오는 공고들을 다 지원해가면서 면접을 더 많이 보러 다녔고, 4월 초에 드디어 입사를 하게 되었습니다.

제가 취업을 하면서 가장 중요하다고 느낀 부분은 '나 자신을 믿고 끝까지 포기하지 말자'입니다. 이를 위해선 먼저 내가 지금 하고 싶은 일이 무엇인지를 알아야 합니다. 만약 자신이 커리어 상 가고자 하는 방향을 확실하게 정했으면, 부족한 부분이 무엇인지 끊임없이 탐구하고 내가 가진 역량을 활용하여 발전시킬 수 있는 기업을 찾는 것이 중요합니다. 면접 준비를 하며 이 부분이 정말 중요하다고 느껴졌고, 이 과정을 수차례 겪다보면 산업 별로 겪고 있는 Pain-point를 발견해낼 수 있습니다. 결과적으로 이 점을 효과적으로 활용하여 면접에서 자신의 경험을 꾸밈없이 얘기한다면 좋은 결과로 이루어질 수 있다고 생각합니다.

저 역시 수차례 면접에서 실패를 경험했지만, 제가 원하던 직무인 데이터 분석과 BI 직무를 끝까지파고들었고 면접에 떨어진 이후에도 학습을 이어 나갔습니다. 끝까지 제가 선택했던 길을 포기하지 않았기에 결국엔, 열매를 성취할 수 있었다고 생각이 드네요. 저도 취업 준비 과정을 거치면서 주변 사람들의 조언과 격려를 많이 받으며 '학사로서 데이터 분석 업무를 수행할 수 있을까?', '내가 해왔던 성공 경험이 적용될 수 있을까?' 등등 정말 많은 고민들을 해왔지만, 여러분 포기하지 않고 끝까지 자신을 잃지 않았으면 합니다. 자신이 하고 싶은 걸 하세요. 그렇다면 결국 끝까지 포기하지 않게 되고 절실해 진다고 생각합니다.

어쨌든, 취업은 다행히도 성공했고 현재 4개월 차에 접어들고 있습니다. 회사에서 적응은 다했고, 직무도 제가 원했던 데이터 분석과 BI 업무를 수행하고 있습니다. 그래서 Power BI도 요새 공부를 다시 하고 있습니다. (인턴 때와 데이터 시각화 가끔할 때 외엔 사실 Python 과 통계 기반 분석만을 수행했기 때문이죠)

앞으로 커리어 적으로 좀 더 저도 고민을 많이 해서 제 가치를 키워나가고자 합니다.

두 번째로는 투자 공부를 본격적으로 하고 있습니다.

제가 투자 공부를 하게 된 이유는 3가지 입니다.

첫 번째로 살면서 투자 공부는 반드시 해야 하는 것 중 하나입니다. 모든 월급쟁이들이 원하는 건 '지금 수입에 월 300 정도를 더 벌고 싶다'입니다. 그렇게 하기 위해서 많은 사람들이 부업을 하면서 투잡, 쓰리잡도 하고 있죠. 나아가 대부분의 사람들은 '남은 생을 일을 아예 하지 않고 살 수 있는 돈을 마련해 은퇴를 하고 싶다' 입니다. 부업이 지금 현재 하고 있는 일보다 수입이 많아지면 사람들은 은퇴를 하게 되니까요. 이런 생각을 해보니, 만일 지금 벌고 있는 돈을 뛰어넘는 부업을 하게 되더라도 결국엔 투자는 반드시 해야 하는 것이라고 생각이 들었습니다. 지금 400을 벌고, 부업으로 600을 번다 한들, 이 돈을 그냥 은행에 넣어버린다면 물가 상승률보단 조금 더 높겠지만 부동산이라든지 다른 투자 수익보단 현저히 낮기에 몇년, 몇십년이 지난 후를 본다면 과거에 투자를 안한 것을 반드시 후회하게 되있습니다.

두 번째는 복리의 마법을 알게 되었습니다. 회사에 다니기 시작한 뒤로 청년드림주택? 이름은 정확하게 모르겠지만 기존 주택청약통장을 이것으로 전환할 수 있다는 사실을 알게 되어 은행에 방문해 전환을 했습니다. 전환하려면 자신이 기존 통장에 넣었던 회차만큼 인정을 받을 수 있고, 기존 통장에서 발생한 이자 수익은 미리 받고 난 이후에 전환이 가능하단 것을 은행 직원 분께서 말씀하셨습니다. 매달 2만원씩 7년을 넣었기에 이자가 뭐 몇만원 나오겠지라는 생각으로 저는 "네 그렇게 진행해주세요"라고 말씀을 드렸고 이자를 받고 나서 깜짝 놀랐습니다. 세금을 떼고 이자로 들어온 금액은 약 16만원 정도로 약 8개월 치의 납입액이 들어왔습니다. 기존 청약의 이율이 그리 높지 않았음에도 월 적립식으로 입금했던 결과를 보며 복리가 대단한 것임을 느낄 수 있었습니다.

세 번째는 안정적인 연평균 수익률을 기대하기 위해서 입니다. 애초에 부업, 추가적인 업무를 통한 수익창출을 넘어 투자를 선택한 계기는 군 적금 만기로 입금했던 애플과 엔비디아의 막대한 주가 상승이 크게 한 몫을 하긴 했습니다. 하지만, 남은 인생이 몇십년인데 개별 종목만을 투자하기엔 너무나도 변동성이 크고 주가가 더 이상 얼마나 크게 오를까? 라는 생각도 들었습니다. 그렇기에 투자 공부를 하면서 ETF라는 분산 투자에 대해서도 알게 되었고, 개별 종목에 비해 변동성이 낮으면서 높은 연평균 수익률을 기대할 수 있다는 점도 알게 되었습니다. 그래서, ETF 상품들에 대해 공부도 많이 하고, ISA, IRP 계좌라는 것에 대해서도 공부를 정말 많이 했습니다. 그래서 현재는 기존에 보유했던 종목들을 모두 판매하고 현금과 주식/ETF 상품들 비중을 50ㅣ50으로 가져가면서 매분기 리밸런싱을 수행하려 합니다. (버핏이 이렇게 한다던데 많은 사람들이 쉽게 따라할 수 없다고 합니다. 제가 생각해도 이걸 따라하기엔 쉽지 않다고 생각이 듭니다만.. 해봐야죠 뭐)

이래저래 마지막으로 작성한 글이 6개월 전인데 글을 쓰지 않았던 6개월도 정말 알차게 잘 보냈다고 생각합니다. (중간 중간 국내 여행도 짧게 1박 2일로 3,4 번 다녀온 것 같네요)

지난 6개월은 이제 그렇다 치고. 2024년도 약 4개월 절반 정도 남았는데, 남은 4.5개월도 정말 알차게 보내기 위해 버킷리스트를 세워볼까 합니다.

✨ 2024년 to do list

1. 빅분기 실기 취득

   일정 < 빅분기 > 접수기간 : 10.28 ~ 11.1 수험표 11.15 시험일 11.30 사전점수 발표 12.13 ~ 12.17 결과발표 12.20

2. Power BI DAX 구문 완벽하게 마스터하기 ~ 10月
3. ChatGPT 사용법 완벽히 익히기 ~ 10月
4. 경영정보시각화 필기 공부
5. 데이터 분석 전반에 걸친 공부 (머신러닝 교과서 / 딥러닝 교과서 등)
6. 투자 공부 꾸준히
7. 자기 관리를 위한 운동 주 4회

🎈 1922 네트워크 연결

컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하고자 하낟. 하지만 허브가 없어 직접 연결을 수행해야 하는데, 모두가 자료를 공유하기 위해선 모든 컴퓨ㅓ가 여결되어 있어야 한다.

이왕이며 컴퓨터를 연결하는 비용을 최소로 하여 연결하고자 할 때, 최소 비용을 구하는 문제.

입력값으 다음과 같다.

첫 줄은 컴퓨터 수, 둘째 줄에는 연결할 수 있는 선의 수, 셋째 줄부터 m줄만큼 각 컴퓨터를 연결하는데 드는 비용이 주어진다. (a, b, c 순서로 a컴퓨터에서 b컴퓨터로 이동하는데 c만큼 비용 발생)

# 1 Prim 알고리즘 풀이
import sys, heapq
input = sys.stdin.readline

n = int(input())
m = int(input())
visited = [False] * (n+1)
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((c, b))
    graph[b].append((c, a))
# 최초 비용 0, 시작 지점 1로 시작
queue = []
heapq.heappush(queue, (0, 1))
answer = 0
def prim():
    global answer
    while queue:
        cost, now_node = heapq.heappop(queue)
        if not visited[now_node]:
            visited[now_node] = True
            answer += cost
            for next_cost, next_node in graph[now_node]:
                heapq.heappush(queue, (next_cost, next_node))
    return answer

print(prim())

< 해설 >

프림 알고리즘을 활용한 풀이. (현재 노드 기준 최소 비용 확인을 위해 힙에 넣고 뺼 때 간선에 매겨진 가중치를 기준으로 넣기)

• 양방향 그래프 생성 후 (힙에 비용을 기준으로 삽입, 꺼내기 위해 비용을 먼저 그래프에 넣는다.)
• 이후 힙에 최초 비용, 시작노드를 담고 방문하지 않은 조건에 한해 다음 인접 노드 탐색 진행.

# 2 Kruskal 알고리즘
import sys
input = sys.stdin.readline

def find_parent(parent, a):
    if parent[a] != a:
        parent[a] = find_parent(parent, parent[a])
    return parent[a]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n = int(input())
m = int(input())
parent = [i for i in range(n+1)]
graph = []
for _ in range(m):
    a, b, c = map(int, input().split())
    graph.append((c, a, b))

graph.sort(key=lambda x:x[0])
answer = 0
for cost, x, y in graph:
    if find_parent(parent, x) != find_parent(parent, y):
        union_parent(parent, x, y)
        answer += cost
print(answer)

< 해설 >

크루스칼 알고리즘을 활용한 풀이

• union-find 알고리즘을 활용해 함수 미리 만들어 주기.
• 이후 그래프에 비용을 기준으로 확인해주기 위해 비용, a, b 순서로 삽입
• 간선에 매겨진 가중치를 기준으로 오름차순 정렬
• 이후 for 루프를 기반으로 x와 y의 부모노드가 다르면 union 진행하고 비용 처리

💯 스패닝트리

모든 정점을 연결하는 가장 작은 최소비용을 구하는 문제는 결국, 모든 정점을 연결하는 최소 연결 횟수 (노드-1)개로 연결된 트리 형태이기에 스패닝트리를 구현하는 문제이다. (단, 사이클이 있어선 안된다.)

스패닝트리 풀이에는 프림, 크루스칼이 존재하는데 간략하게 정의를 한 번 다시 살펴보고자 한다.

프림

• 시작 노드 기준 연결된 edge 중 가중치가 가장 작은 edge와 연결된 노드를 추가하며 가장 최소 비용으로 탐색 진행해 간선 수가 n-1개면 중단.
• 시작 복잡도는 O(간선수 * log노드수)

• 다익스트라의 경우 한 정점에서 최소비용이 드는 순서대로 모두 방문한다면, 프림의 경우는 최소 비용 1개만을 골라 이동하는 방식

  크루스칼

• 그리디 방식으로 네트워크 내 모든 정점을 최소 비용으로 연결해 최적 해답을 구하는 방법.
• 간선 선택을 기반으로 이동하며 이전 단계에서의 만들어진 트리와 별개로 무조건 현재 기준 최소 비용이 드는 간선을 선택하는 방식이다.
• 간선을 기준으로 추가하기 때문에 사이클 여부를 반드시 확인해야 하고 현재 노드를 기준으로 간선 당 비용들을 오름차순 정렬해 확인해야 한다.)

🎈 1915 가장 큰 정사각형

NXM 크기의 각 칸이 0/1로 채워진 배열이 있다. 이 중 모든 칸이 1로 채워진 가장 큰 정사각형의 넓이를 구하는 문제.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
dp = [[0]*m for _ in range(n)]
answer = 0
for i in range(n):
    for j in range(m):
        # 행, 열이 첫 번째이면 dp는 그래프 값
        if i == 0 or j == 0:
            dp[i][j] = graph[i][j]
        # 그래프가 0일 때 dp는 0
        elif graph[i][j] == 0:
            dp[i][j] = 0
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
        answer = max(answer, dp[i][j])

print(answer**2)

< 해설 >

입력값들을 각각 채워주고 dp로 해결했다. 로직은 다음과 같다.

• 2중 for loop를 통해 인덱스를 지정해주고 주어진 nxm 크기의 정사각형의 열과 행이 첫 번째 인덱스면 dp는 해당 그래프 값을 채워준다.
• graph의 값이 0이면 dp도 0
• 이외의 케이스는 이전 3가지 케이스 중 최솟값에 1을 더해준다.

🎈 9935 문자열 폭발

문자열에 폭발 문자열을 심어놨고 폭발 문자열이 복팔하면 그 문자는 문자열에서 사라지고 이외의 문자열은 합쳐진다. 폭발은 다음과정으로 진행

• 문자열이 폭발 문자열을 포함하고 있는 경우, 모든 폭발 문자열이 폭발하고 남은 문자열들은 순서대로 이어 붙여 새로운 문자열이 된다.
• 새로 생긴 문자열에도 폭발 문자열이 포함될 수 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 반복한다.
  최종적으로 모든 폭발이 끝나고 남은 문자열을 출력하는 문제.
  첫 줄에는 문자열이 주어지고 둘째 줄에는 폭발 문자열이 주어진다.

import sys
input = sys.stdin.readline

word = list(input().rstrip())
destroy = input().rstrip()

stack = []
for i in word:
    stack.append(i)
    # 스택에 마지막이 폭발 문자열 끝 번호, 스택 끝에 있으면 빼기
    if stack[-1] == destroy[-1] and ''.join(stack[-len(destroy):]) == destroy:
        del stack[-len(destroy):]

if stack:
    print(''.join(stack))
else:
    print('FRULA')

< 해설 >

문자열을 word, 폭발 문자열을 destroy로 지정하고 스택을 이용해 폭발 문자열이 스택에 포함되면 제거해주는 방식으로 진행했다. 특히, 제거 후에도 문자열 내 폭발 문자열이 있으면 제거해 주어야 하므로 스택의 남아 있는 끝 값이 폭발 문자열과 동일한지 여부도 체킹해준다.

🎈 1781 컵라면

문제 N개가 주어질 때 각 문제는 [데드라인, 컵라면 수]로 구성되어 있다. 즉 문제를 푸는 사람은 데드라인 내 문제를 풀면 컵라면 수만큼 컵라면을 얻을 수 있다. 최종적으로 주어진 데드라인 내 최대 얻을 수 있는 컵라면 개수를 구하는 문제

import sys, heapq
input = sys.stdin.readline

n = int(input())
ramen = []
for _ in range(n):
    ramen.append(list(map(int, input().split())))
ramen.sort(key=lambda x: x[0])

heap = []
for i in range(n):
    heapq.heappush(heap, ramen[i][1])
    if len(heap) > ramen[i][0]:
        heapq.heappop(heap)
print(sum(heap))

< 해설 >

우선순위 큐를 활용해 해결한 문제.

• 우선 ramen이라는 리스트에 데드라인을 기준으로 오름차순 정렬한다.
• 이후 heap을 생성하여 n loop 만큼 아래 로직을 반복한다.
• heap에 ramen 수를 넣는다. 이때 만일 힙 개수가 ramen 리스트 내 데드라인보다 크다면 heap의 최소 크기를 빼준다.

• 결과적으로 힙에 남은 값들을 모두 더해주면 라면을 최대로 얻을 수 있다.

🎈 1261 알고스팟

미로 크기는 NXM이고 각 한 칸은 방으로 구성되어 있다. 미로는 빈 방 또는 벽으로 구성되어 있고 벽의 경우 부수고 이동해야 한다.

이동할 수 있는 칸은 상,하,좌,우 4방향이고 0,0에서 N,M으로 이동할 때 벽을 부수어야 하는 최소 개수를 구하는 문제.

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(m)]
# 벽 부순 횟수
visited = [[-1]*n for _ in range(m)]
# 상하좌우 4방향
dx = [-1, 1, 0, 0]
dy = [0 ,0 ,-1, 1]

queue = deque()
queue.append((0, 0))
visited[0][0] = 0

while queue:
    x, y = queue.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<m and 0<=ny<n:
            if visited[nx][ny] == -1:
                if graph[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y]
                    queue.appendleft((nx, ny))
                else:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx, ny))
print(visited[m-1][n-1])

< 해설 >

BFS를 이용한 풀이 방법.

1. deque 생성 후 시작점을 넣어주고 벽을 부순 횟수를 카운팅하는 visited 2차원 배열을 생성한 값에 초기 (0,0)의 값은 0으로 설정한다.
2. queue가 비지 않는 동안 주어진 범위 내 다음 과정을 반복한다. 2-1. 다음 위치가 방문하지 않은 곳이고, 빈 방인 경우 queue에 왼쪽에 삽입하고 이전 위치랑 값을 동일하게 설정한다. 2-2. 반대로 다음 위치가 벽인 경우 이전 값 + 1처리를 하고 큐에 오른쪽에 삽입한다.
3. 위 과정을 반복한다면 다음 위치가 방인 경우에 한해서만 큐가 계속해서 꺼내게 되고 결국 n,m 위치까지 이동하며 벽을 부순 횟수는 visited[m-1][n-1]이 된다.

🎈 11404 플로이드

n개의 도시가 있고 한 도시에서 출발해 다른 도시에 도착하는 m개의 버스가 있을 때 각 버스는 한 번 사용 시 일정 비용을 지불해야 한다. 모든 도시 쌍 A -> B로 이동 시 필요한 비용의 최솟값을 구하는 문제.

첫 줄에 N, 둘째 줄에 M, 셋째 줄부터 M+2줄까지 버스 정보가 주어진다. 버스 정보의 경우 출발 도시, 도착 도시, 필요한 비용으로 주어지고 비용은 100,000보다 작거나 같은 자연수이다.

출력값으로는 n줄만큼 i->j번째 도시로 가는데 필요한 최소 비용을 출력하는 문제

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
graph = [[1e9]*(n+1) for _ in range(n+1)]
# 자기 도시로 간 것은 0
for i in range(1, n+1):
    graph[i][i] = 0
# m줄만큼 입력값 처리 (단, 같은 목적지가 있을 수 있으니 append가 아닌 min값 비교)
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = min(graph[a][b], c)

for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] == 1e9:
            print(0, end = ' ')
        else:
            print(graph[i][j], end = ' ')
    print()

< 해설 >

O(N^3)의 복잡도를 갖는 플로이드 워셜 문제 정리하면 i, j, k 순으로 for loop를 돌되 j를 출발해 k로 가는 경로 중 최소 비용을 구하면 된다. 단 경로가 1개만 있는 것이 아니므로, 기존 append가 아닌 min으로 최솟값을 비교해주어야 한다. 주의할 점은 경로의 기준 즉, 경유지가 되는 i를 가장 위에 두고 j->k와 j->i->k를 비교해 더 최소 비용이 발생하는 경로를 선택하면 된다.

🎈 2109 순회강연

N개 대학에 순회 강연을 다니는데 각 대학에서 d일 안에 강연을 하면 p만큼의 강연료를 지불한다고 한다. 예시로 4개의 대학에서 각각 p, d로 50, 10, 20, 30 // 2, 1, 2, 1을 제시했을 때 첫 날 30, 둘째 날 50을 벌 수 있다.

입력값으로 첫 줄에 정수 N이 주이지고 다음 n줄 만큼 p,d가 주어질 때 최대로 벌 수 있는 돈을 구하기.

import sys, heapq
input = sys.stdin.readline

n = int(input())
day = []
for i in range(n):
    day.append(list(map(int, input().split())))
day.sort(key=lambda x:x[1])

heap = []
for i in day:
    heapq.heappush(heap, i[0])
    if len(heap) > i[1]:
        heapq.heappop(heap)
print(sum(heap))

< 해설 > 강연 비용, 강연 날짜를 각자 리스트로 나누어서 처리할 수도 있지만, heap을 이용해 day를 오름차순으로 정렬하고 비용을 더하고 길이보다 길면 pop하는 방식으로 처리하면 보다 쉽게 최대로 벌 수 있는 돈을 처리할 수 있다.