1. 통계 정보

MySQL 8.0 버전부터는 인덱스되지 않은 컬럼들에 대해서도 데이터 분포도를 수집해서 저장하는 히스토그램(Histogram) 정보가 도입되었다.

1) 테이블 및 인덱스 통계 정보

(1) MySQL 서버의 통계 정보

통계 정보를 테이블로 관리할지 여부 설정

• MySQL 5.6 버전부터 각 테이블의 통계 정보를 mysql 데이터베이스의 innodb_index_stats 테이블과 innodb_table_stats 테이블로 영구적으로 저장 및 관리할 수 있게 개선되었다. -> MySQL 서버가 재시작되어도 기존의 통계 정보를 유지할 수 있게 되었다.
  • 테이블 생성 시 STATS_PERSISTENT 옵션을 설정할 수 있는데, 이 설정값에 따라 테이블 단위로 영구적인 통계 정보를 보관할지 말지 결정할 수 있다.

    CREATE TABLE tab_test (fd1 INT, fd2 VARCHAR(20), PRIMARY KEY(fd1))
    ENGINE=InnoDB
    STATS_PERSISTENT={ DEFAULT | 0 | 1 }; // 테이블 생성 시점에 값 설정

    // 옵션 설정값 변경
    ALTER TABLE employees.empoyees STATS_PERSISTENT={ DEFAULT | 0 | 1 };

    STATS_PERSISTENT=0 : 테이블의 통계 정보를 테이블에 저장하지 않음. STATS_PERSISTENT=1 : 테이블의 통계 정보를 테이블에 저장해 관리함. STATS_PERSISTENT=DEFAULT : 테이블 생성 시 별도로 옵션 값을 설정하지 않았을 때의 디폴트 값이다. 테이블의 통계를 영구적으로 관리할지 말지를 innodb_stats_persistent 시스템 변수의 값으로 결정한다. innodb_stats_persistent 시스템 설정 변수는 기본적으로 ON(1)로 설정되어 있어서 옵션 없이 테이블을 생성하면 영구적으로 통계 정보를 저장한다.

통계 정보 자동 수집, 갱신 관련 설정

• innodb_stats_auto_recalc 시스템 변수의 설정 값을 ON으로 설정하면 InnoDB가 데이터가 충분히 변했다고 판단되는 시점에 자동으로 통계를 다시 계산하는데, OFF면 자동 재계산을 안 하고 ANALYZE TABLE 같은 수동 트리거에 의존하게 된다.

  • 테이블 통계 정보가 자주 갱신되면 동일 데이터/동일 쿼리에서 계획이 갑자기 바뀌는 당혹스러움을 막을 수 있다는 이유로 저자는 innodb_stats_auto_recalc을 OFF할 것을 권하고 있다. 테이블 생성 시점에 STATS_AUTO_RECALC 옵션을 이용해 개별 테이블 단위로 자동 수집 여부를 결정할 수 있기 때문에 이걸 활용하자는 것.

    STATS_AUTO_RECALC=1 : 테이블의 통계 정보를 자동으로 수집한다. STATS_AUTO_RECALC=0 : 테이블의 통계 정보는 ANAYLYZE TABLE 명령을 실행할 때만 수집된다. STATS_AUTO_RECALC=DEFAULT : 테이블 생성 시 별도로 옵션을 설정하면 이 값으로 설정된다. 테이블의 통계 정보 수집을 innodb_stats_auto_reclac 시스템 변수의 값으로 결정한다.

  전역 변수 값은 OFF하고 데이터가 자주 바뀌는 테이블에 대해서만 STATS_AUTO_RECALC=1로 설정해 자동 수집을 하자는 것. 굉장히 합리적이고 이상적인 조합이긴 하다. 근데,

  1. '이 테이블은 안정적이겠지' 하고 STATS_AUTO_RECALC=0으로 설정해놨는데 잘못된 판단이었던 경우
  2. 실수로 STATS_AUTO_RECALC 값을 설정 안 한 채로 테이블을 생성해버려서 자동 수집이 필요한데도 innodb_stats_auto_recalc OFF 설정대로 자동 수집이 안 되어버리는 경우 등등.... 생각보다 머리 아픈 리스크도 뒤따라온다. 이 모든 걸 감당할 수 있고 쿼리 최적화에 미쳐 있는 조직이라면 고려할 만하지만, 그렇지 않다면 그냥 innodb_stats_auto_recalc를 켜두는 것이 더 나을 수도 있을 것 같다.

• innodb_stats_transient_sample_pages : 자동으로 통계 정보 수집이 실행될 때 몇 개의 페이지를 임의로 샘플링해서 분석하고 그 결과를 통계 정보로 활용할지를 정할 수 있는 시스템 변수이다. 기본값은 8이다.
• innodb_stats_persistent_sample_pages : ANALYZE TABLE 명령으로 통계 정보 수집을 수동으로 진행할 때, 몇 개의 페이지를 임의로 샘플링해서 분석하고 그 결과를 통계 정보로 활용할지를 정할 수 있는 시스템 변수이다. 기본값은 20이다.

이 값들을 작게 설정하면 통계의 정확도가 낮아지고, 높게 설정하면 통계 정보 수집 시간이 길어질테니 적당히 설정하자.

테이블에 저장되는 통계 정보 조회

// 통계 정보 조회
SELECT *
FROM innodb_index_stats
WHERE database_name='employees' AND TABLE_NAME='employees';

• 통계 정보의 각 컬럼은 다음과 같은 값을 저장하고 있다.
  • innodb_index_stats.stat_name='n_diff_pfx%' : 인덱스가 가진 유니크한 값의 개수
  • innodb_index_stats.stat_name='n_leaf_pages' : 인덱스의 리프 노드 페이지 개수
  • innodb_index_stats.stat_name='size' : 인덱스 트리의 전체 페이지 개수
  • innodb_index_stats.n_rows : 테이블의 전체 레코드 건수
  • innodb_index_stats.clustered_index_size : PK의 크기(InnoDB 페이지 개수)
  • innodb_index_stats.sum_of_other_index_sizes : PK를 제외한 세컨더리 인덱스의 크기(InnoDB 페이지 개수)
    • 이 값은 STATS_AUTO_RECALC 옵션 값에 따라 0으로 보일 수도 있는데, 그 경우 다음과 같이 테이블에 대해 ANALYZE TABLE 명령을 실행하면 통곗값이 저장된다.

      ANALYZE TABLE employees.employees;

2) 히스토그램

https://dev.mysql.com/blog-archive/histogram-statistics-in-mysql/ MySQL 8.0으로 업그레이드되면서 MySQL 서버도 컬럼의 데이터 분포도를 참조할 수 있는 히스토그램 정보를 활용할 수 있게 되었다. 히스토그램은 버킷(Bucket) 단위로 레코드 건수나 컬럼값의 범위를 구분해 관리한다.

(1) 히스토그램 정보 수집 및 조회

// 히스토그램 수집
ANALYZE TABLE employees.employees
UPDATE HISTOGRAM ON gender, hire_date;

// 수집된 히스토그램 조회
SELECT *
FROM COLUMN_STASTICS
FROM SCHEMA_NAME='empolyees' AND TABLE_NAME='employees';

• 히스토그램 정보는 컬럼 단위로 관리된다.
• 자동으로는 수집되지 않고, ANALYZE TABLE ... UPDATE HISTOGRAM 명령을 실행함으로써 수동으로 수집 및 관리할 수 있다.
• 수집된 히스토그램 정보는 시스템 딕셔너리에 함께 저장되고, MySQL 서버가 시작될 때 딕셔너리의 히스토그램 정보를 information_schema 데이터베이스의 column_statistics 테이블로 로드한다.
  • 그래서 실제 히스토그램 정보를 조회하려면 column_statistics 테이블을 SELECT해서 참조할 수 있다.
  • information_schema.column_statstics 테이블의 HISTOGRAM 컬럼이 가진 나머지 필드들의 의미는 다음과 같다.
    • sampling-rate 히스토그램 정보를 수집하기 위해 스캔한 페이지의 비율을 저장한다. 샘플링 비율이 높아질수록 더 정확한 히스토그램이 되지만, 테이블을 전부 스캔하는 것은 부하가 높으며 시스템의 자원을 많이 소모한다. 그래서 MySQL 서버는 8.0.19버전부터 histogram_generation_max_mem_size 시스템 변수에 설정된 메모리 크기에 맞게 적절히 샘플링한다. 이 변수의 초기값은 20MB이다.
    8.0.19 미만의 버전에서는 풀 테이블 스캔을 하니 주의하자.
    • histogram-type 히스토그램의 종류를 저장한다.
    • number-of-buckets-specified 히스토그램을 생성할 때 설정했던 버킷의 개수를 저장한다. 기본값은 100개이다. 최대 1024개를 설정할 수 있지만, 100개면 충분하다고 한다.

(2) 지원되는 히스토그램 타입

MySQL 8.0 버전 기준

• 싱글톤 히스토그램(Singleton)
  • Value-Based 히스토그램 또는 도수 분포라고도 불린다.
  • 컬럼 값 개별로 레코드 건수를 관리하는 히스토그램이다. 컬럼이 가지는 값별로 버킷이 할당된다.
  • 각 버킷이 컬럼의 값, 발생 빈도의 비율이라는 2개의 값을 가진다.
  • 주로 코드 값과 같이 유니크한 값의 개수가 상대적으로 적은 경우 사용된다.
    
• 높이 균형 히스토그램(Equi-Height)
  • Height-Balanced 히스토그램이라고도 불린다.
  • 컬럼 값의 범위를 균등한 개수로 구분해서 관리하는 히스토그램이다. 개수가 균등한 컬럼 값의 범위별로 하나의 버킷이 할당된다.
  • 각 버킷이 범위 시작 값, 범위 마지막 값, 발생 빈도율, 각 버킷에 포함된 유니크한 값의 개수라는 4개의 값을 가진다.
  • 컬럼값의 각 범위에 대해 레코드 건수 비율이 누적으로 표시된다. 누적이기 때문에 위 높이 균형 히스토그램에서 뒤로 갈수록 건수가 많아지는 게 아니다! 그래프의 기울기가 일정하기 때문에 각 범위 내 레코드 건수가 비슷하다는 것을 알 수 있다.

(3) 히스토그램 삭제

히스토그램 자체를 삭제

ANALYZE TABLE employees.employees
DROP HISTOGRAM ON gender, hire_date;

• 히스토그램의 삭제 작업은 테이블의 데이터를 참조하는 것이 아니라 딕셔너리의 내용만 삭제하기 때문에 다른 쿼리의 성능에 영향을 주지 않고 즉시 완료된다.
• 히스토그램이 사라지면 쿼리의 실행 계획이 달라질 수 있으므로 주의하자.

옵티마이저가 히스토그램을 사용하지 않도록 하기

SET GLOBAL optimizer_switch='condition_fanout_filter=off';

• 위와 같이 optimizer_switch 시스템 변수 값을 글로벌로 변경하면 된다. 이렇게 하면 MySQL 서버의 모든 쿼리가 히스토그램을 사용하지 않는다. 그런데 condition_fanout_filter 옵션에 의해 영향을 받는 다른 최적화 기능들이 사용되지 않을 수도 있다고 한다. 임시로 잠깐동안만 히스토그램 사용을 끄고 싶은 상황에 사용하면 될 것 같다. 문제가 생겼을 때 그게 히스토그램 문제인지 알고 싶을 때 등등...

특정 커넥션 또는 특정 쿼리에서만 사용하지 않도록 하기

// 현재 커넥션에서 실행되는 쿼리만 히스토그램을 사용하지 않게 설정
SET SESSION optimizer_switch='condition_fanout_filter=off';

// 현재 쿼리에서만 히스토그램을 사용하지 않게 설정
SELECT /*+ SET_VAR(optimizer_switch='condition_fanout_filter=off') */ *
FROM ...

(4) 히스토그램의 용도

• 히스토그램이 도입되기 전에 MySQL 서버가 가지고 있던 통계 정보는 테이블의 전체 레코드 건수와 인덱스된 컬럼이 가지는 유니크한 값의 개수 정도였다.
  • 그래서 히스토그램 정보가 없으면 옵티마이저는 데이터가 균등하게 분포되어 있을 것이라고 예측한다.

  • 테이블의 레코드가 1000건이고 어떤 컬럼의 유니크한 값 개수가 100개였다면 MySQL 서버는 다음과 같은 동등 비교 검색에서 대략 10개의 레코드가 일치할 것이라고 예측하는 것이다.

     SELECT * FROM order WHERE user_id='matt.lee';

• 하지만 실제 응용 프로그램의 데이터는 항상 균등한 분포도를 가지지 않는다는 문제가 있다. -> 히스토그램은 각 범위(버킷)별로 레코드의 건수와 유니크한 값의 개수 정보를 가지기 때문에 훨씬 정확한 예측을 할 수 있다.
• 특정 범위의 데이터가 많고 적음을 식별할 수 있다*는 것이다. 이를 바탕으로 어느 테이블을 먼저 읽어야 조인의 횟수를 줄일 수 있을지 옵티마이저가 더 정확히 판단하게 되어, 쿼리의 성능에 상당한 영향을 미칠 수 있다.

(5) 히스토그램과 인덱스

인덱스 다이브

• MySQL 서버에서는 쿼리의 실행 계획을 수립할 때 사용 가능한 인덱스들로부터 조건절에 일치하는 레코드 건수를 대략 파악하고 최종적으로 가장 나은 실행 계획을 선택한다.
  • 이때 조건절에 일치하는 레코드 건수를 예측하기 위해 옵티마이저는 실제 인덱스의 B-Tree를 샘플링해서 살펴본다.

  • 이 작업을 인덱스 다이브(Index Dive)라고 한다.

• MySQL 8.0 서버에서는 인덱스된 컬럼을 검색 조건으로 사용하는 경우 그 컬럼의 히스토그램은 사용하지 않고 실제 인덱스 다이브를 통해 직접 수집한 정보를 활용한다. 실제 검색 조건의 대상 값에 대한 샘플링을 실행하는 것이므로 항상 히스토그램보다 정확한 결과를 기대할 수 있기 때문이다. 히스토그램은 레코드 전체를 대상으로 샘플링을 해서 나온 결과인데, 인덱스는 검색 조건에 부합하는 값에 대해서만 샘플링을 진행할 테니까.

(MySQL측에서 주장하는) 인덱스 대신 히스토그램을 고려해볼 수 있는 이유

1. Maintaining an index has a cost. If you have an index, every INSERT/UPDATE/DELETE causes the index to be updated. This is not free, and will have an impact on your performance. A histogram on the other hand is created once and never updated unless you explicitly ask for it. It will thus not hurt your INSERT/UPDATE/DELETE-performance. 대충 인덱스가 업데이트가 느리다는 단점을 커버할 수 있다는 얘기 같다. 히스토그램은 사용자가 ANALYZE TABLE을 실행할 때만 생성/갱신되니까.

2. If you have an index, the optimizer will do what we call “index dives” to estimate the number of records in a given range. This also has a certain cost, and it might become too costly if you have for instance very long IN-lists in your query. Histogram statistics are much cheaper in this case, and might thus be more suitable. 인덱스 다이브를 수행하는 것도 공짜가 아니다. 히스토그램은 이미 만들어져 있으니 쿼리 수행 시점에 새롭게 레코드 건수를 파악하고 하지 않고 그냥 가져다 쓰면 되는 거니까. 특히 IN 절의 조건이 엄청 많으면 그냥 전체 샘플링이랑 별 차이 없는 경우도 있다는 얘기를 하고 싶은 것 같다.

3) Cost Model

(1) 개요

https://dev.mysql.com/doc/refman/8.0/en/cost-model.html 쿼리를 처리할 때는 다음과 같은 다양한 작업을 필요로 한다.

• 디스크로부터 데이터 페이지 읽기
• 메모리로부터 데이터 페이지 읽기
• 인덱스 키 비교
• 레코드 평가
• 메모리 임시 테이블 작업
• 디스크 임시 테이블 작업

• MySQL 서버는 사용자의 쿼리에 대해 각각의 작업이 얼마나 많이 필요한지 예측하고 전체 작업 비용을 계산한 결과를 바탕으로 최적의 실행 계획을 찾는다.
• 전체 쿼리의 비용을 계산하는 데 필요한 단위 작업들의 비용을 코스트 모델(Cost Model)이라고 한다.
• MySQL 5.7 버전부터 이 값을 조정할 수 있도록 개선되었다. 하지만 전문 지식을 가지고 있지 않다면 기본값을 함부로 변경하지 않는 것이 좋다. 기본값으로도 MySQL 서버는 20년이 넘는 시간동안 잘 사용되어 왔다.
• 옵티마이저의 실행 계획 수립에 사용된다.

(2) Cost Model이 사용하는 테이블

두 테이블 모두 mysql DB에 존재한다.

• server_cost 인덱스를 찾고, 레코드를 비교하고, 임시 테이블을 처리하는 데 드는 비용 관리
• engine_cost 레코드를 가진 데이터 페이지를 가져오는 데 필요한 비용 관리

두 테이블이 공통적으로 가지고 있는 컬럼

• cost_name 코스트 모델의 각 단위 작업명
• default_value 각 단위 작업의 디폴트 비용 (MySQL 서버 소스 코드에 설정되어 있는 값)
• cost_value DBMS 관리자가 설정한 값 (이 값이 NULL이면 default_value 컬럼의 값을 사용)
• last_updated 단위 작업의 비용이 변경된 시점
• comment 비용에 대한 추가 설명

last_updated와 comment는 옵티마이저에 영향을 미치는 정보는 아니며, 단순 정보성으로 관리되는 컬럼이다.

engine_cost 테이블이 추가로 더 가지고 있는 컬럼(하지만 의미가 없음)

• engine 적용된 스토리지 엔진 (InnoDB만 쓴다면 그냥 냅두자.)
• device_type 디스크 타입 MySQL 8.0에서는 이 컬럼 값을 활용하지 않는다(???) 그래서 0으로만 설정할 수 있다. 찾아보니 MySQL 9 버전에서도 여전히 활용 안 하고 있다고 한다.

(3) Cost Model에서 지원하는 단위 작업

Cost Model에서 중요한 것은 각 단위 작업에 설정되는 비용 값이 커지면 어떤 실행 계획들이 고비용으로 바뀌고 어떤 실행 계획들이 저비용으로 바뀌는지 파악하는 것이다.

• io_block_read_cost
  • 이 값이 증가할수록 옵티마이저가 InnoDB 버퍼 풀에 데이터 페이지가 많이 적재되어 있는 인덱스를 사용하는 실행 계획을 선택할 가능성이 높아진다.
• memory_block_read_cost
  • 이 값이 증가할수록 InnoDB 버퍼 풀에 적재된 데이터 페이지가 상대적으로 적다고 하더라도 그 인덱스를 사용할 가능성이 높아진다.
• disk_temptable_create_cost와 disk_temptable_row_cost
  • 이 값이 증가할수록 옵티마이저가 디스크에 임시 테이블을 만들지 않는 방향으로 실행 계획을 선택할 가능성이 높아진다.
• key_compare_cost
  • 이 값이 증가할수록 옵티마이저가 가능하면 정렬을 수행하지 않는 방향의 실행 계획을 선택할 가능성이 높아진다.
• memory_temptable_create_cost와 memory_temptable_row_cost
  • 이 값이 증가할수록 옵티마이저가 메모리 임시 테이블을 만들지 않는 방향의 실행 계획을 선택할 가능성이 높아진다.
• row_evaluate_cost
  • 스토리지 엔진이 반환한 레코드가 쿼리의 조건에 일치하는지를 평가하는 단위 작업이다.
  • 이 값이 증가할수록 풀 테이블 스캔과 같이 많은 레코드를 처리하는 쿼리의 비용이 높아지고, 반대로 레인지 스캔과 같이 상대적으로 적은 수의 레코드를 처리하는 쿼리의 비용이 낮아진다.

2. 실행 계획 확인

1) 실행 계획 출력 포맷

FORMAT 옵션을 사용해 실행 계획의 표시 방법을 단순 테이블 형태, TREE, JSON 중 선택할 수 있다.

(1) 테이블 포맷

EXPLAIN
SELECT *
FROM employees e
  INNER JOIN salaries s ON s.emp_no=e.emp_no
WHERE first_name='ABC';

(2) 트리 포맷

EXPLAIN FORMAT=TREE
SELECT *
FROM employees e
  INNER JOIN salaries s ON s.emp_no=e.emp_no
WHERE first_name='ABC';

(3) JSON 포맷

EXPLAIN FORMAT=JSON
SELECT *
FROM employees e
  INNER JOIN salaries s ON s.emp_no=e.emp_no
WHERE first_name='ABC';

2) 쿼리 실행 시간 확인

(1) 개요

• MySQL 8.0.18 버전부터 쿼리의 실행 계획과 단계별 소요 시간 정보를 확인할 수 있는 EXPLAIN ANALYZE 기능이 추가되었다.
• 항상 결과를 TREE 포맷으로 보여주기 때문에 EXPLAIN 명령에 FORMAT 옵션을 사용할 수 없다.
• 실행 시간이 아주 오래 걸리는 쿼리라면 EXPLAIN ANALYZE 명령을 실행했을 때 쿼리가 완료되어야 실행 계획의 결과를 확인할 수 있다.
  • 쿼리의 실행 계획이 아주 나쁜 경우라면 EXPLAIN 명령으로 먼저 실행 계획만 확인해서 어느 정도 튜닝한 후 EXPLAIN ANALYZE 명령을 실행하는 것이 좋다.

• TREE 포맷의 실행 계획에서 들여쓰기는 호출 순서를 의미한다. 실제 실행 순서는 다음 기준으로 읽으면 된다.

  들여쓰기가 다른 레벨에서는 가장 안쪽에 위치한 라인이 먼저 실행

• 들여쓰기가 같은 레벨*에서는 상단에 위치한 라인이 먼저 실행

EXPLAIN ANALYZE
SELECT
    p1_0.id,
    p1_0.status,
    p1_0.payment_id,
    u1_0.name,
    u1_0.email,
    p2_0.category,
    p2_0.title,
    p1_0.total_amount,
    p2_0.platform,
    p1_0.requested_at,
    p1_0.cancelled_amount,
    p1_0.cancel_reason,
    p1_0.cancelled_at,
    m1_0.NAME
FROM
    payments p1_0
        LEFT JOIN
    users u1_0
    ON p1_0.user_id=u1_0.private_id
        LEFT JOIN
    MEMBER m1_0
    ON p1_0.member_id=m1_0.ID
        JOIN
    products p2_0
    ON p2_0.private_id=p1_0.product_id
ORDER BY
    p1_0.requested_at desc

-> Nested loop inner join  (cost=130 rows=113) (actual time=0.186..0.616 rows=113 loops=1)
    -> Nested loop left join  (cost=90.6 rows=113) (actual time=0.176..0.463 rows=113 loops=1)
        -> Nested loop left join  (cost=51.1 rows=113) (actual time=0.174..0.422 rows=113 loops=1)
            -> Sort: p1_0.requested_at DESC  (cost=11.6 rows=113) (actual time=0.156..0.169 rows=113 loops=1)
                -> Filter: (p1_0.product_id is not null)  (cost=11.6 rows=113) (actual time=0.038..0.118 rows=113 loops=1)
                    -> Table scan on p1_0  (cost=11.6 rows=113) (actual time=0.0366..0.11 rows=113 loops=1)
            -> Single-row index lookup on u1_0 using UK85bxs2b2qmo9xv6u02x0dv93q (private_id=p1_0.user_id)  (cost=0.251 rows=1) (actual time=0.00207..0.0021 rows=1 loops=113)
        -> Single-row index lookup on m1_0 using PRIMARY (ID=p1_0.member_id)  (cost=0.251 rows=1) (actual time=213e-6..215e-6 rows=0.0708 loops=113)
    -> Single-row index lookup on p2_0 using UK40t6qkxhq6et2gvdjdfy0i8rv (private_id=p1_0.product_id)  (cost=0.251 rows=1) (actual time=0.00117..0.0012 rows=1 loops=113)

(2) EXPLAIN ANALYZE 결과에서 필드들의 의미

-> Single-row index lookup on u1_0 using UK85bxs2b2qmo9xv6u02x0dv93q (private_id=p1_0.user_id)  (cost=0.251 rows=1) (actual time=0.00207..0.0021 rows=1 loops=113)

• actual time=0.00207..0.0021
  • payments 테이블에서 읽은 private_id 값을 기준으로 user 테이블에서 일치하는 레코드를 검색하는 데 걸린 시간(밀리초)을 의미한다.
  • 첫 번째 값은 첫 번째 레코드를 가져오는 데 걸린 평균 시간을 의미한다.
  • 두 번째 값은 마지막 레코드를 가져오는 데 걸린 평균 시간을 의미한다.
• rows=1
  • 검색 결과 일치하는 평균 레코드 건수를 의미한다.
• loops=113
  • payments 테이블에서 읽은 private_id 값을 기준으로 user 테이블에서 일치하는 레코드를 검색하는 작업이 반복된 횟수를 의미한다. payments에서 읽은 private_id의 개수가 113개였음을 알 수 있다.

여기서 말하는 '평균'은 loop를 돌며 반복된 작업들 간에 평균을 냈다는 뜻이다. loops=113이므로 113번의 작업을 실행하면서 나타난 평균 값이라는 것.

3) 실행 계획 분석

• 표의 각 레코드는 쿼리 문장에서 사용된 테이블(서브쿼리로 임시 테이블을 생성한 경우 그 임시 테이블까지 포함)의 개수만큼 출력된다.
• 테이블 포맷의 경우 실행 순서가 위에서 아래로 순서대로 표시된다.
  • UNION이나 상관 서브쿼리와 같은 경우 순서대로 표시되지 않을 수도 있다.

https://dev.mysql.com/doc/refman/8.0/en/explain-output.html

(1) id 컬럼

• 실행 계획에서 가장 왼쪽에 표시되는 컬럼이다.
• SELECT 쿼리별로 부여되는 식별자 값이다.
• 하나의 SELECT 문장이 하위 SELECT 문장을 포함하는 형태의 쿼리에서는 실행 계획에 최소 2개 이상의 id 값이 표시될 것이다.
• 조인하면 조인되는 테이블의 개수만큼 실행 계획 레코드가 출력되지만 같은 id 값이 부여된다.
• 실행 계획의 id 컬럼은 테이블의 접근 순서를 의미하지는 않는다.

(2) select_type 컬럼

• 각 단위 SELECT 쿼리가 어떤 타입의 쿼리인지를 표시하는 컬럼이다.

SIMPLE

• UNION이나 서브쿼리를 사용하지 않는 단순한 SELECT 쿼리인 경우이다.
• 쿼리 문장이 아무리 복잡하더라도 실행 계획에서 select_type이 SIMPLE인 단위 쿼리는 오직 1개만 존재한다.
• 일반적으로 가장 바깥에 있는 SELECT 쿼리에 표시된다.

PRIMARY

• UNION이나 서브쿼리를 가지는 SELECT 쿼리의 실행 계획에서 가장 바깥쪽에 있는 단위 쿼리에 표시된다.
• select_type이 PRIMARY인 단위 SELECT 쿼리는 오직 1개만 존재한다.

UNION

• UNION으로 결합하는 단위 SELECT 쿼리 가운데 첫 번째를 제외한 두 번째 이후 단위 SELECT 쿼리에 표시된다.

DEPENDENT UNION

• UNION으로 결합하는 단위 SELECT 쿼리 가운데 외부 쿼리에 의해 영향을 받는 것을 의미한다.

(3) table 컬럼

• 테이블 단위로 표시된다.
• 테이블명에 별칭이 부여된 경우 별칭이 표시된다.
• 별도의 테이블을 사용하지 않는 SELECT 쿼리의 경우(FROM 절이 없는 경우) NULL이 표시된다.
• '<>'로 둘러싸인 이름이 명시된 경우 임시 테이블을 의미한다.
  • 항상 숫자가 함께 표시되는데, 이 숫자는 단위 SELECT 쿼리의 id 값을 지칭한다.

(4) type 컬럼

• 각 테이블을 어떻게 읽고 있는지, 접근 방법을 나타낸다.
• 하나의 단위 SELECT 쿼리는 단 하나의 접근 방법만 사용할 수 있다.
• index_merge를 제외한 나머지 접근 방법은 하나의 인덱스만 사용한다.
• 다음에 나열될 type 컬럼의 값들은 성능이 빠른 순서대로 나열된 것이다.

const

EXPLAIN
SELECT * FROM employees WHERE emp_no=10001;

• 쿼리가 PK나 UK 컬럼을 이용하는 WHERE 절을 가지고 있으며, 반드시 1건을 반환하는 쿼리의 처리 방식을 의미한다.
• 다중 컬럼으로 구성된 PK나 UK 중에서 인덱스의 일부 컬럼만을 조건으로 사용할 때는 이 접근 방법을 사용할 수 없다.
  • PK의 일부만 조건으로 사용할 때는 const가 아닌 ref로 표시된다.
• type 컬럼이 const인 실행 계획은 옵티마이저가 쿼리를 최적화하는 단계에서 쿼리를 먼저 실행해서 통째로 상수화한다.

eq_ref

EXPLAIN
SELECT * FROM dept_emp de, employees e
WHERE e.emp_no=de.emp_no AND de.dept_no='d005';

책에서 이 쿼리에 조인이 있다길래 JOIN절이 없는데 뭔 소리지? 했는데 이렇게 하는 게 옛날 구식 조인 문법이란다. 킹받네...

• 여러 테이블이 조인되는 쿼리의 실행 계획에서만 표시된다.
• 조인에서 처음 읽은 테이블의 컬럼 값을, 그 다음에 읽어야 할 테이블의 PK나 UK 컬럼의 검색 조건에 사용함을 의미한다. 이때 두 번째 이후에 읽는 테이블의 type 컬럼에 eq_ref가 표시된다.
• 두 번째 이후에 읽히는 테이블을 UK로 검색할 때 그 유니크 인덱스는 NOT NULL이어야 하며, 다중 컬럼으로 만들어진 PK 혹은 UK라면 인덱스의 모든 컬럼이 비교 조건에 사용되어야만 이 접근 방법이 사용될 수 있다.
• 조인에서 두 번째 이후에 읽는 테이블에서 반드시 1건만 존재한다는 보장이 있어야 사용할 수 있는 접근 방법이다.

ref

• 인덱스의 종류와 관계 없이 동등(equal) 조건으로 검색할 때 사용된다.
• eq_ref와는 달리 조인의 순서와 관계 없이 사용되며, PK나 UK 등의 제약 조건도 없다. -> 반환되는 레코드가 반드시 1건이라는 보장이 없다. 그래서 const나 eq_ref보다 빠르진 않지만, 그래도 동등 조건으로만 비교되므로 매우 빠른 조회 방법 중 하나이다.

여기까지는 마음이 편안해지는 매우 좋은 접근 방법이다.

fulltext

• MySQL 서버의 전문 검색(Full-text Search) 인덱스를 사용해 레코드를 읽는 접근 방법을 의미한다.
• 전문 검색 인덱스를 사용하기 위해서는 전문 검색 인덱스가 테이블에 정의되어 있어야 한다.
• 전문 검색은 MATCH ... AGAINST ... 구문을 사용해서 실행한다.
• 전문 검색 조건은 우선순위가 상당히 높아서 전문 검색 인덱스와 (const, eq_ref, ref를 제외한) 일반 인덱스가 함께 사용됐다면 일반적으로 MySQL은 전문 인덱스를 사용해서 처리한다.
  • 하지만 fulltext보다 일반 인덱스를 이용하는 range가 더 빨리 처리되는 경우도 많으니 조건별로 성능을 확인해보자.

ref_or_null

• ref 접근 방법과 같은데, NULL 비교가 추가된 형태이다.
• 실제 업무에서 많이 활용되지는 않지만, 많약 사용된다면 나쁘지 않은 접근 방법 정도로 기억해 두면 충분하다.

unique_subquery

• WHERE 조건절에서 사용될 수 있는 IN(subquery) 형태의 쿼리를 위한 접근 방법이다.
• 서브쿼리에서 중복되지 않는 유니크한 값만 반환할 때 이 접근 방법을 사용한다.

index_subquery

• 업무 특성상 IN(subquery)에서 subquery가 중복된 값을 반환할 수도 있다. 이때 서브쿼리 결과의 중복된 값을 인덱스를 이용해서 제거할 수 있을 때 이 접근 방법이 사용된다.

range

EXPLAIN
SELECT * FROM employees WHERE emp_no BETWEEN 10002 AND 10004;

• 인덱스 레인지 스캔 형태의 접근 방법이다. 인덱스를 하나의 값이 아니라 범위로 검색하는 경우를 의미한다.
• 주로 <, >, IS NULL, BETWEEN, IN, LIKE 등의 연산자를 이용해 인덱스를 검색할 때 사용한다.
• 일반적으로 애플리케이션의 쿼리가 가장 많이 사용하는 접근 방법이다.
• 얘도 상당히 빠르다. 모든 쿼리가 이 접근 방법만 사용해도 최적의 성능이 보장된다.

index_merge

• 2개 이상의 인덱스를 이용해 각각의 검색 결과를 만들어낸 후, 그 결과를 병합해서 처리하는 방식이다.
• 하지만 이름만큼 그렇게 효율적으로 작동하는 것은 아니다.
  • 여러 인덱스를 읽어야 하므로 일반적으로 range보다 효율성이 떨어진다.
  • 전문 검색 인덱스를 사용하는 쿼리에서는 적용되지 않는다.
  • 이 접근 방법으로 처리된 결과는 항상 2개 이상의 집합이 되기 때문에 그 두 집합의 교집합이나 합집합, 또는 중복 제거와 같은 부가적인 작업이 더 필요하다.

• 구글링 좀 해보니 이 index_merge로 인한 피해자들의 하소연을 쉽게 찾을 수 있었다....;; https://kth990303.tistory.com/456 https://mattermost.com/blog/tuning-mysql-and-the-ghost-of-index-merge-intersection/ 이 접근 방식이 사용됐다면 꼭 검증해봐야 할 것 같다.

index

• 인덱스를 처음부터 끝까지 읽는 인덱스 풀 스캔을 의미한다.
• 비교해는 레코드의 건수는 풀 테이블 스캔과 같다. 하지만 일반적으로 인덱스는 데이터 파일 전체보다 크기가 작으므로 풀 테이블 스캔보다는 빠르게 처리되며, 쿼리의 내용에 따라 정렬된 인덱스의 장점을 이용할 수 있으므로 훨씬 효율적이다.
• 다음 조건 중 첫 번째+두 번째 조건을 충족하거나, 첫 번째+세 번째 조건을 충족하는 쿼리에서 사용할 수 있다.
  • range나 const, ref로 인덱스를 사용하지 못하는 경우.
  • 인덱스에 포함된 컬럼만으로 처리할 수 있어서 데이터 파일을 읽지 않아도 되는 쿼리인 경우
  • 인덱스를 이용해 정렬이나 그루핑 작업이 가능해서 별도의 정렬 작업을 피할 수 있는 경우

ALL

• 풀 테이블 스캔을 의미하는 접근 방법이다. 테이블을 냅다 처음부터 끝까지 전부 읽는다.
• 위에서 설명된 접근 방법으로는 처리할 수 없을 때 가장 마지막에 선택하는 가장 비효율적인 방법이다.
• 빠른 응답을 사용자에게 보내야 하는 웹 서비스 등과 같은 온라인 트랜잭션 처리 환경에는 적합하지 않다. 테이블이 매우 작지 않다면 실제로 테이블에 데이터를 어느 정도 저장한 상태에서 쿼리의 성능을 확인해 보고 적용하는 것이 좋다.

(5) possible_keys 컬럼

• 옵티마이저는 쿼리를 처리하기 위해 여러 가지 처리 방법을 고려하고 그중에서 비용이 가장 낮을 것으로 예상해는 실행 계획을 선택해 쿼리를 실행한다. possible_keys 컬럼에 있는 내용은 옵티마이저가 최적의 실행 계획을 만들기 위해 후보로 선정했던 접근 방법에서 사용되는 인덱스의 목록이다.
  • 이 컬럼의 내용이 모두 실제로 사용됐다는 게 아니다!

(6) key 컬럼

• 최종 선택된 실행 계획에서 사용하는 인덱스를 의미한다. 쿼리를 튜닝할 때는 이 컬럼에 의도했던 인덱스가 표시되는지 확인하는 것이 중요하다.
• 값이 PRIMARY인 경우 PK를 사용한다는 의미이며, 그 이외의 값은 모두 테이블이나 인덱스를 생성할 때 부여했던 고유 이름이다.
• 2개 이상의 인덱스를 사용하는 index_merge가 사용된 경우에는 여러 개의 인덱스가 ','로 구분되어 표시된다. 접근 방법이 ALL일 때와 같이 인덱스를 전혀 사용하지 못하면 값이 NULL로 표시된다.

(7) key_len 컬럼

• 쿼리를 처리하기 위해 다중 컬럼 인덱스에서 몇 개의 컬럼까지 사용했는지를 보여준다. 더 정확하게는 인덱스의 각 레코드에서 몇 바이트까지 사용했는지 알려준다.
• MySQL은 NOT NULL이 아닌, 즉 NULLABLE 컬럼에 대해서는 컬럼 값이 NULL인지 아닌지를 저장하기 위해 1바이트를 추가로 사용한다. 그래서 때로는 key_len 필드의 값이 데이터 타입의 길이보다 조금 길게 표시되는 경우도 발생할 수 있다.

• 다음 예제는 두 개의 컬럼(dept_no, emp_no)으로 구성된 PK를 가지는 dept_emp 테이블을 조회하는 쿼리이다. 그리고 이 쿼리는 PK 중 dept_no만 비교에 사용한다.

  EXPLAIN
  SELECT * FROM dept_emp WHERE dept_no='d005';

  dept_no 컬럼의 타입이 CHAR(4)인데, MySQL 서버는 문자 하나당 고정적으로 4바이트를 할당한다. (실제 utf8mb4 문자의 크기는 1바이트부터 4바이트까지 가변적이지만 최악의 경우로 계산하는 것.) 그러니 key_len 컬럼의 값이 16으로 표시되어 있는 건 PK에서 앞쪽 16바이트(4*4바이트)만 유효하게 사용했다는 의미이다.

• 위 예제와 똑같은 인덱스를 사용하지만 dept_no 컬럼과 emp_no 모두를 조건절에 사용하는 다음 쿼리가 있다고 해보자.

  SELECT * FROM dept_emp WHERE dept_no='d005' AND emp_no=10001;

  emp_no 컬럼은 INTEGER 타입이며, INTEGER 타입은 4바이트를 차지한다. 위 쿼리는 두 인덱스를 모두 사용했기 때문에 key_len 컬럼의 값이 dept_no 컬럼의 길이(16)와 emp_no 컬럼의 길이(4)의 합인 20으로 표시된 것이다.

이런 식으로 인덱스 컬럼 중 몇 개가 사용되었는지를 이 필드를 통해 확인할 수 있다.

(8) ref 컬럼

• 접근 방법이 ref인 경우, 참조 조건(Equals 비교 조건)으로 어떤 값이 제공되었는지 부여준다.
  • 상숫값을 지정했다면 const가 표시된다.
  • 다른 테이블의 컬럼 값이면 그 테이블명과 컬럼명이 표시된다.
• 이 컬럼 값은 크게 신경쓰지 않아도 무방하다.

• 하지만, 값이 func로 표시되면 조금 주의해서 볼 필요가 있다. 이는 참조값을 그대로 사용하지 않고 콜레이션 반환이나 연산을 거쳤다는 의미이다.

  EXPLAIN
  SELECT *
  FROM employees e
  JOIN dept_emp de ON e.emp_no=(de.emp_no-1);

  위 쿼리는 de.emp_no 값에서 1을 뺀 값으로 employees 테이블과 조인하고 있다. 이 경우 ref 값으로 조인 컬럼명 대신 func가 표시되고 있음을 알 수 있다.
  • 그런데 이렇게 사용자가 명시적으로 값을 변환할 때뿐만 아니라 MySQL 서버가 내부적으로 값을 변환해야 할 때도 컬럼 값이 func로 출력된다. 문자집합이 일치하지 않는 두 문자열 컬럼을 조인한다거나, 숫자 타입 컬럼과 문자열 타입의 컬럼을 조인할 때가 그 예이다.
  • 가능하다면 MySQL 서버가 이러한 변환을 하지 않을 수 있도록 조인 컬럼의 타입을 일치시키자.*

(9) rows 컬럼

• 실행 계획의 효율성 판단을 위해 예측했던 레코드 건수를 보여준다.
  • 옵티마이저는 각 조건에 대해 가능한 처리 방식을 나열하고, 각 처리 방식의 비용을 비교해 최종적으로 하나의 실행 계획을 수립한다.
    • 이때 각 처리 방식이 얼마나 레코드를 읽고 비교해야 하는지 예측해서 비용을 산정한다.
    • 대상 테이블에 얼마나 많은 레코드가 포함되어 있는지, 또는 각 인덱스 값의 분포도가 어떤지를 통계 정보를 기준으로 조사해서 예측한다.
  • 통계 정보를 참조해 옵티마이저가 산출해 낸 예상값이므로 정확하지는 않다.
  • 반환하는 레코드의 예측치가 아니라, 쿼리를 처리하기 위해 얼마나 많은 레코드를 읽고 처리해야 할지를 의미한다.
  • 옵티마이저는 이 값을 가지고 어떤 인덱스를 타야 할지, 혹은 그냥 테이블 풀 스캔을 하는 것이 더 효율적일지 등을 판단한다.

(10) filtered 컬럼

• 인덱스 조건에 일치하는 레코드(이것의 개수가 rows 컬럼 값이다.) 중에서 인덱스를 타지 않는 WHERE 조건에 의해 필터링되고 남은 레코드의 비율을 의미한다.

위 실행 계획에서 ix_firstname 인덱스 조건에 만족하는 레코드의 수는 대략 233건이며, 이중에서 16.03%의 레코드만이 인덱스를 사용하지 못하는 나머지 조건에 일치한다는 뜻이다. 즉, 필터링되고 남은 레코드 수는 대략 37(233 * 0.1603)건 정도이다. 조인을 수행할 레코드 건수가 대략 37건임을 의미한다.

위 이미지는 쿼리에서 조인 순서만 반대로 바꾼 후의 실행 계획이다. 이번에는ix_firstname 인덱스 조건에 만족하는 레코드의 수가 대략 3314건이며, 이중에서 11.11%의 레코드만이 인덱스를 사용하지 못하는 나머지 조건에 일치한다. 즉, 필터링되고 남은 레코드 수는 대략 368(3314 * 0.1111)건 정도이다. 조인 순서를 바꾸니 기존보다 10배에 가까운 조인을 해야 하는 것이다. 그러니 옵티마이저는 이 조인 순서 대신 전자를 선택할 것이다.

이처럼, filtered 컬럼의 표시되는 값이 얼마나 정확히 예측되느냐에 따라 조인의 성능이 달라진다. 그렇긴 한데 이런 예측은 옵티마이저가 알아서 하는 거라 쿼리 최적화와는 큰 관련이 없다.....

(11) Extra 컬럼

• 이름은 Extra지만 사실 중요한 내용들이 자주 표시된다.
• 일반적으로 고정된 몇 개의 문장이 2~3개씩 함께 표시된다.

const row not found

• 쿼리의 실행 계획에서 const 접근 방법으로 테이블을 읽었지만 실제로 해당 테이블에 레코드가 1건도 존재하지 않았다는 뜻이다.
• 테이블에 적절히 테스토용 데이터를 저장하고 다시 한 번 실행 계획을 확인해보자.

Distinct

• 중복된 값들은 모두 무시하고 필요한 것만 가져온다는 뜻이다.

FirstMatch

• 세미 조인에서 FirstMatch 전략이 사용되었다는 뜻이다. (9장 참고)

Full scan on NULL key

• col1 IN (SELECT col2 FROM ...) 과 같은 쿼리에서 자주 발생한다.
  • 이러한 쿼리에서 col1이 NULL이면 서브쿼리에 사용된 테이블에 대해서 풀 테이블 스캔을 할 것임을 알려주는 것이다.
  • col1이 NOT NULL로 정의된 컬럼이라면 표시되지 않는다.
  • NULLABLE 컬럼이라도 다음과 같이 WHERE절에 col1 IS NOT NULL이라는 조건을 지정함으로써 이 문장이 표시되지 않도록 할 수 있다. ```sql SELECT * FROM tb_test1 WHERE col1 IS NOT NULL // col1이 NULL이면 후속 조건이 아예 실행되지 않는다. AND col IN (SELECT col2 FROM tb_test2);
• col1 중에서 NULL인 값이 하나도 없다면 풀 테이블 스캔은 발생하지 않으니 걱정할 필요 없다.

Impossible HAVING / Impossible WHERE

• 쿼리에 사용된 HAVING 절 또는 WHERE절의 조건을 만족하는 레코드가 없다는 뜻이다.
• 이 문장들이 표시된다면 쿼리에 오류가 있는 경우가 대부분이니 쿼리를 다시 확인해보자.

LooseScan

• 세미 조인 최적화 중에서 LooseScan 최적화 전략이 사용되었다는 뜻이다. (9장 참고)

No matching min/max row

• MIN()이나 MAX()와 같은 집합 함수가 있는 쿼리의 조건절에 일치하는 레코드가 한 건도 없다는 뜻이다.
• 일치하는 레코드가 한 건도 없으니 집합 함수는 NULL을 반환할 것이다.

no matching row in const table

• 조인에 사용된 테이블에서 const 방법으로 접근할 때 일치하는 레코드가 없다는 뜻이다.

  EXPLAIN
  SELECT * 
  FROM dept_emp de
  JOIN (SELECT emp_no FROM employees WHERE emp_no=0) tb1 ON tb1.emp_no=de.emp_no
  WHERE de.dept_no='d005';

  위 쿼리에서 JOIN절 서브쿼리 결과 일치하는 레코드가 없다면 이 문장이 표시될 것이다.

No matching rows after partition prunung

• 파티션된 테이블에 대한 UPDATE 또는 DELETE 명령의 실행 계획에서 표시될 수 있다.
• 해당 파티션에서 UPDATE하거나 DELETE할 대상 레코드가 없다는 뜻이다.

No tables used

• FROM 절이 없는 쿼리 문장이라는 뜻이다.
• SELECT 1; 같은 쿼리.

Not exists

• 옵티마이저가 조인할 때 레코드가 존재하는지 아닌지만 판단한다는 것을 의미한다.
• 이거 뜨면 그냥 그렇구나~ 하고 넘어가자.

Plan isn't ready yet

https://dev.mysql.com/doc/refman/8.0/en/explain-for-connection.html

• EXPLAIN FOR CONNECTION 명령을 실행했을 때 표시될 수 있다.

  SHOW PROCESSLIST; // <process_id> 확인
  EXPLAIN FOR CONNECTION <process_id>;

  일반 EXPLAIN은 쿼리 실행 중 이렇게 할 예정이라고 말해주는 일종의 계획표다. 반면 EXPLAIN FOR CONNECTION은 이미 실행 중인 살아있는 쿼리 세션이 실제로 쓰고 있는 실행 계획을 훔쳐볼 수 있는 명령이다. 한 마디로 CCTV 같은 친구. 실행 계획이랑 실제 실행이 다를 때 유용하게 사용할 수 있다. 다만 너무 빨리 끝나는 쿼리라면 못 본다.

• Plan isn't ready yet은 해당 커넥션에서 아직 쿼리의 실행 계획을 수립하지 못한 상태에서 EXPLAIN FOR CONNECTION 명령이 실행된 것을 의미한다.
• 대상 커넥션의 쿼리가 실행 계획을 수립할 여유 시간을 좀 더 주고 다시 명령을 실행하자.

Range checked for each record(index map: N)

Recursive

• CTE를 이용한 재귀 쿼리의 실행 계획임을 의미한다.

Rematerialize

• MySQL 8.0 버전부터 래터럴 조인(LATERAL JOIN) 기능이 추가됐는데, 래터럴로 조인되는 테이블은 선행 테이블의 레코드별로 서브쿼리를 실행해서 그 결과를 임시 테이블에 저장한다. 이렇게 임시 테이블이 생성되는 경우 이 문장이 표시된다.

Select tables optimized away

• MIN() 또는 MAX()만 SELECT 절에 사용되거나, GROUP BY로 MIN(), MAX()를 조회하는 쿼리가 인덱스를 오름차순 또는 내림차순으로 1건만 읽는 형태의 최적화가 적용된다는 뜻이다.

Start temporary, End temporary

• 세미 조인 최적화 중 Duplicate Weed-out 최적화 전략이 사용된다는 뜻이다.

unique row not found

• 두 개의 테이블이 각각 유니크 컬럼으로 아우터 조인을 수행하는 쿼리에서, 아우터 테이블에 일치하는 레코드가 존재하지 않음을 의미한다.

Using filesort

• ORDER BY 처리가 인덱스를 사용하지 못함을 의미한다.
• 조회된 레코드를 정렬용 메모리 버퍼에 볷해 퀵 소트 또는 힙 소트 알고리즘을 이용해 정렬을 수행하게 된다.
• Using filesort가 출력되는 쿼리는 많은 부하를 일으키므로 가능하다면 퀴리를 튜닝하거나 인덱스를 생성하는 것이 좋다.

Using index

• 커버링 인덱스로 처리됨을 의미한다. 개꿀 최적화이다.
• 인덱스 레인지 스캔을 사용하지만 쿼리의 성능이 만족스럽지 못한 경우 인덱스에 있는 컬럼만 사용하도록 쿼리를 변경해 큰 성능 향상을 볼 수 있다.
• InnoDB의 경우 모든 테이블이 클러스터링 인덱스로 구성되어 있어 PK는 항상 인덱스에 포함되어 있다. 이 특성 때문에 쿼리가 커버링 인덱스로 처리될 가능성이 상당히 높다. 인덱스 컬럼을 추가로 하나 더 가지고 있는 효과를 얻을 수 있는 것.
• 하지만 무조건 커버링 인덱스로 처리하려고 인덱스에 많은 컬럼을 추가하면 더 위험한 상황이 초래될 수도 있다. 인덱스의 크기가 커져서 메모리 낭비가 심해지고 레코드를 저장하거나 변경하는 작업이 매우 느려질 수도 있다.

Using index condition

• 인덱스가 Index condition pushdown 최적화를 사용한다는 뜻이다. (9장 참고)

Using index for group-by

1. 타이트 인덱스 스캔을 통한 GROUP BY 처리

• 인덱스를 이용해 GROUP BY 절을 처리할 수 있더라도 AVG(), SUM(), COUNT()와 같이 조회하려는 값이 모든 인덱스를 다 읽어야 하는 경우.

• 이러한 경우는 Loose Index Scan이라고 하지 않는다.

• 이러한 경우에는 실행 계획에 'Using index for group-by' 메시지가 출력되지 않는다.

2. Loose Index Scan을 통한 GROUP BY 처리

• 단일 컬럼 인덱스라면, 그루핑 컬럼 말고는 아무것도 조회하지 않는 쿼리인 경우.
• 다중 컬럼 인덱스라면, GROUP BY 절이 인덱스를 사용할 수 있으면서 MIN()이나 MAX()와 같이 조회하는 값이 인덱스의 첫 번째 또는 마지막 레코드만 읽어도 되는 쿼리인 경우.

• Loose Index Scan이 사용될 수 있다. (인덱스를 듬성듬성 필요한 부분만 읽는다.)

1. WHERE 조건절이 없는 경우

• GROUP BY 절의 컬럼과 SELECT로 가져오는 컬럼이 Loose Index Scan을 사용할 수 있는 조건만 갖추면 된다.

2. WHERE 조건절이 있지만 검색을 위해 인덱스를 사용하지 못하는 경우

• 이 경우에는 Loose Index Scan을 이용할 수 없다.

3. WHERE 절의 조건이 있고, 검색을 위해 인덱스를 사용하는 경우

• WHERE 절의 조건과 GROUP BY 처리가 똑같은 인덱스를 공통으로 사용할 수 있을 때만 Loose Index Scan을 사용할 수 있다.
  • WHERE 절의 조건과 GROUP BY 처리가 사용할 수 있는 인덱스가 다른 경우 일반적으로 옵티마이저는 WHERE 조건절이 인덱스를 사용하도록 실행 계획을 수립하는 경향이 있기 때문.
  • 하지만 이런 경우라도, WHERE 조건에 의해 검색된 레코드 건수가 적으면 Loose Index Scan을 사용하지 않아도 매우 빠르게 처리될 수 있기 때문에 옵티마이저가 적절히 판단하여 사용하지 않을 수도 있다.

Using index for skip scan

• 옵티마이저가 인덱스 스킵 스캔 최적화를 사용하였음을 나타낸다.

Using join buffer(Block Nested Loop / Batched Key Access / hash join)

• 조인 버퍼가 사용되는 실행 계획을 의미한다.

  • 조인 버퍼는 드라이빙 테이블의 행들을 모아두는 메모리 공간이다. 드리븐 테이블을 스캔하며 조인 버퍼의 내용과 한 번에 비교함으로써 I/O를 줄이기 위함이다.

  • 조인 조건에 인덱스를 못 쓰는 경우 사용된다.

    1. 조인 컬럼에 인덱스가 없는 경우
    2. 함수, 연산, 타입 변환 때문에 인덱스 사용이 불가한 경우
    3. 드라이빙 테이블은 인덱스로 읽지만, 드리븐 테이블은 풀 스캔해야 하는 경우 등등...

  • 이렇게 조인 버퍼를 사용하는 조인 방식(알고리즘)에는 Block Nested Loop, Batched Key Access, hash join이 있다. 원래는 Block Nested Loop만 있었는데 8.0 버전에서 다른 두 방식이 추가되면서 알고리즘명도 실행 계획에 함께 포함되도록 바뀌었다고 한다.

  • join_buffer_size라는 시스템 변수에 최대로 할당 가능한 조인 버퍼 크기를 설정할 수 있다.

    • 조인되는 컬럼에 인덱스가 적절하게 준비되어 있다면 조인 버퍼는 크게 신경쓰지 않아도 된다.
    • 만약 그렇지 않다면, 조인 버퍼를 너무 부족하거나 너무 과다하게 사용되지 않게 적절하게 설정하는 것이 좋다. (일반적인 온라인 웹 서비스용이라면 1MB 정도도 충분하다.)

• 조인 조건이 없는 카테시안 조인을 수행하는 쿼리는 항상 조인 버퍼를 사용한다.

• 만약 조인 시 인덱스를 탈 것을 기대했는데 이 메시지가 출력됐다면, 조인 시 인덱스를 안 타고 있다는 뜻이니 확인이 필요하다.

Using MRR

• MRR(Multi Range Read)
  • PK 값들 하나하나에 대해 클러스터드 인덱스를 읽는데, 이 PK 값 순서가 랜덤하게 되어 있으면 랜덤 I/O 지옥이 펼쳐진다.
  • 이를 막기 위해 MMR은
    1. 보조 인덱스에서 조건에 맞는 PK들을 수집한다.
    2. 이 PK들을 메모리 버퍼에 모은다.
    3. PK들을 정렬한다.
    4. 정렬된 순서대로 클러스터디 인덱스를 읽는다. 이런 식으로 순차 I/O에 가까워지도록 함으로써 디스크 접근 횟수를 감소시킨다.

1) 개념

• 노드 간에 정보를 올바르게 주고받기 위해 합의된 규칙이나 방법.
• 네트워크 통신이 원활하게 이뤄지려면, 서로가 사용하는 프로토콜을 양쪽이 모두 이해할 수 있어야 한다.
• 일상 속 언어와는 달리 통신 과정에서는 일반적으로 여러 프로토콜을 함께 사용한다.
• 어떤 프로토콜이 사용되느냐에 따라 패킷 헤더가 가지는 정보가 달라질 수 있다.

2) 모든 프로토콜에는 목적과 특징이 있다.

• IP는 패킷을 수신지까지 전달하기 위해 사용되는 프로토콜이다.

• IP의 목적: 패킷을 수신지까지 전달하기 위한 것.

• ARP는 192.168.1.1과 같은 형태의 IP 주소를 A1:B2:C3:D4:E5:F6과 같은 형태의 MAC 주소로 대응하기 위해 사용되는 프로토콜이다.

• ARP의 목적: IP 주소를 MAC 주소로 대응하기 위한 것.

• HTTPS는 HTTP에 비해 보안상 더 안전한 프로토콜이다.
• TCP는 UDP에 비해 일반적으로 느리지만 신뢰성이 높은 프로토콜이다.

이처럼, 모든 프로토콜은 저마다의 목적과 특징이 있다. 이것이 프로토콜 학습의 중점이 되어야 한다.

2. 네트워크 참조 모델

1) 개념

• 네트워크를 통해 통신하는 각 과정을 여러 단계로 나누어 정형화한 모델이다.
• 각 단계는 계층적으로 표현 가능하다.
• 메시지를 송신하기 위해 거치는 단계와 수신하기 위해 거치는 단계는 서로 반대이다. 위 이미지는 네트워크 참조 모델의 한 예시이다.

2) 목적

(1) 네트워크 구성과 설계의 용이성

• 각 계층에서 수행되어야 하는 역할을 명확하게 정의할 수 있다.

• 프로토콜과 네트워크 장비를 각 계층별로 구성할 수 있다.

  (2) 네트워크 문제 진단과 해결의 용이성

  

• 어떤 계층에서 문제가 발생했는지를 확인함으로써 문제의 원인을 보다 쉽게 파악할 수 있다.

3) 대표적인 네트워크 참조 모델

(1) OSI 7 계층

• 국제 표준화 기구인 ISO에서 만든 네트워크 참조 모델이다.
• 물리 계층(physical layer) OSI 모델의 최하단. 1과 0으로 표현되는 비트 신호를 주고받는 계층이다. 전기 신호, 빛 등 각 통신 매체별 신호 정보가 비트 데이터로 정의된다.
• 데이터 링크 계층(data link layer) 네트워크 내 주변 장치 간의 정보를 올바르게 주고받기 위한 계층이다. 오류 검출이 이루어진다. 네트워크 주변 장치의 식별을 위해 MAC 주소가 사용된다.
• 네트워크 계층(network layer) 메시지를 다른 네트워크에 속해 있는 수신지까지 전달하는 계층이다. LAN과 LAN 간의 통신을 위한 기술인 IP 주소, 라우팅 등의 기술이 이용된다.
• 전송 계층(transport layer) 패킷 전송의 신뢰성과 안정성을 위한 계층이다. 패킷의 순서나 유실 및 손상 여부 등을 관리한다. 사용자 프로세스를 식별하기 위해 포트가 이용된다.
• 세션 계층(session layer) 세션(통신을 주고받는 호스트의 응용 프로그램 간 연결 상태)을 관리하는 계층이다.
• 표현 계층(presentation layer) 문자를 컴퓨터가 이해할 수 있는 코드로 변환(인코딩)하거나, 압축 혹운 암호화하는 계층이다.
• 응용 계층(application layer) 사용자 및 사용자가 이용하는 응용 프로그램의 다양한 네트워크 서비스를 제공하는 계층이다.

(2) TCP/IP 4 계층

• 인터넷 프로토콜 스위트(internet protocol suite), TCP/IP 프로토콜 스택(TCP/IP protocol stack)이라고도 한다.

• 프로토콜을 중심으로 하여 OSI 7 계층에 비해 실용성을 강조한 모델이다.

• 네트워크 엑세스 계층(network access layer) 링크 계층, 네트워크 인터페이스 계층이라고도 한다. OSI 7 계층의 데이터 링크 계층과 유사하다.

• 인터넷 계층(internet layer) OSI 7 계층의 네트워크 계층과 유사하다.

• 전송 계층(transport layer) OSI 7 계층의 전송 계층과 유사하다.

• 응용 계층(application layer) OSI 7 계층의 세션+표현+응용 계층과 유사하다.

(3) OSI 7 계층, TCP/IP 4 계층은 사실 아무것도 해주지 않는다.

네트워크 참조 모델을 처음 학습하면 네트워크 지식 == 네트워크 참조 모델이라고 오해하기 쉽다. 하지만,

• 네트워크 참조 모델은 반드시 지켜져야 하는 규칙이 아니다.
• 네트워크 참조 모델이나 각 계층이 네트워크를 작동시키는 주체가 아니다. 네트워크를 작동시키는 주체는 네트워크 참조 모델에 속해 있는 프로토콜과 네트워크 장비이다.
• 모든 프로토콜이나 네트워크 장비가 반드시 특정 계층에 완벽히 대응되지는 않는다. 프로토콜과 네트워크 장비는 계속해서 새롭게 만들어지고 있다.

네트워크 참조 모델은 말 그대로 '참조'를 위한 밑그림일 뿐이다. 따라서 네트워크 학습의 중점은 프로토콜과 네트워크 장비가 되어야 하지, 네트워크 참조 모델이 되어서는 안 된다.

3. 캡슐화와 역캡슐화

1) 개념

(1) 캡슐화

• 메시지 송신 과정에서 이루어진다.
• 네트워크 참조 모델의 가장 높은 계층에서부터 가장 낮은 계층으로 이동하며 이루어진다.
• 각 계층별 프로토콜의 목적과 특징에 부합하는 헤더(+트레일러)를 추가하는 과정이다.
• 이전 계층에서의 패킷(헤더+페이로드)은 다음 계층에서의 페이로드가 된다.
• 위 사진처럼 각 계층을 지나면서 헤더가 추가되며, 데이터 링크 계층에서는 트레일러도 함께 추가된다.

  (2) 역캡슐화

• 메시지 수신 과정에서 이루어진다.
• 네트워크 참조 모델의 가장 낮은 계층에서부터 가장 높은 계층으로 이동하며 이루어진다.
• 각 계층별 프로토콜의 목적과 특징에 부합하는 헤더를 제거하는 과정이다.

2) PDU(Protocol Data Unit)

• 각 계층에서 송수신되는 메시지의 단위를 의미한다.
• 현재 계층의 PDU == 상위 계층의 데이터 + 현재 계층의 프로토콜 헤더(및 트레일러)

4. 트래픽과 네트워크 성능 지표

1) 트래픽(traffic)

• 네트워크 내의 정보량을 의미한다.
• 주로 노드에서 측정이 이루어진다. (특정 시점에 노드를 경유하는 정보량)
• 과도한 트래픽은 과부하(성능 저하)를 발생시킨다.

2. 네트워크 성능 지표

(1) 처리율(throughput)

• 단위 시간당 네트워크를 통해 실제로 전송되는 정보량.
• 실시간성이 강조된 지표이다.
• 표현 단위
  • bps(bit/s): bits per second
  • Mbps(Mbit/s): megabits per second
  • Gbps(Gbit/s): gigabits per second
  • pps(p/s): packets per second

(2) 대역폭(bandwidth)

• 단위 시간동안 통신 매체를 통해 송수신할 수 있는 최대 정보량.
• 통신 매체의 최대 역량을 나타내는 지표로 사용된다. (어떤 통신 매체를 통해 정보를 주고받을 수 있는 폭이 얼마나 넓은가?)
• bps, Mbps, Gbps 단위 사용.

(3) 패킷 손실(packet loss)

• 손실된 패킷 수, 전체 패킷 / 유실된 패킷(백분위) 단위 사용.

노드와 노드를 연결하는 간선으로 이루어진 자료구조의 형태이다.

1) 호스트

• 주로 가장자리에 위치해 있는 노드이다.
• 네트워크를 통해서 주고받는 메시지를 최초로 생성해서 송신하거나 최종적으로 수신하는 대상이다.
• 스마트폰, 데스크탑 컴퓨터, 서버 컴퓨터 등.

호스트는 그 역할에 따라 클라이언트 혹은 서버 중 하나로서 동작한다.

(1) 클라이언트(client)

• 서버에 요청을 보내는 호스트이다.

(2) 서버(server)

• 클라이언트의 요청에 대한 응답을 하는 호스트이다.

2) 네트워크 장비

• 호스트 간 주고받을 정보가 거쳐가는 중간 노드이다.
• 호스트 간 주고받는 정보가 수신지까지 안정적으로, 안전하게 전송될 수 있도록 한다.
• 이더넷 허브, 스위치, 라우터, 공유기 등

⭐️ 서버, 클라이언트, 네트워크 장비는 역할과 네트워크 구조에 따라 구분한 개념일 뿐 완전히 배타적인 개념은 아니다.

• 호스트로 동작하는 노드도 때로는 네트워크 장비의 역할을 수행할 수 있다.
• 서버로 동작하는 노드도 때로는 클라이언트의 역할을 수행할 수 있다.
• 클라이언트로 동작하는 노드도 때로는 서버의 역할을 수행할 수 있다.

3) 통신 매체

• 노드 간의 연결을 짓는 유무선의 연결 매체이다.
• 유선 매체, 무선 매체로 나뉜다.

4) 메시지

• 통신 매체로 연결되어 있는 노드가 서로 주고 받는 정보를 의미한다.
• 웹 페이지, 파일, 메일 등.

2. 네트워크의 분류

1) 범위에 따른 분류

(1) LAN (Local Area Network)

• 가까운 지역을 연결한 근거리 통신망이다.
• 가정, 사무실 등 한정된 공간 내에 있는 개인이나 소규모 조직에서 주로 구성한다.
• 개발자가 구축, 관리하는 대부분의 네트워크가 여기에 속한다.

(2) WAN (Wide Area Network)

• 먼 지역을 연결하는 광역 통신망이다.
• ISP에서 주로 구축 및 관리한다.
• 다른 LAN에 속한 호스트와 메시지를 주고 받아야 할 때 필요하다.
• 인터넷 등.

⭐️ ISP(Internet Service Provider)란?

• 사용자에게 인터넷과 같은 WAN에 연결 가능한 회선을 임대하는 등 WAN과 관련한 다양한 서비스를 제공하는 주체이다.
• KT, LG유플러스, SK브로드밴드 등.

2) 메시지 교환 방식에 따른 분류

(1) 회선 교환 네트워크

• 회선 교환 방식으로 메시지를 주고받는 네트워크이다. : 호스트 간 메시지를 주고받기 전 (메시지의 전송로인) 회선을 미리 설정(연결, 예약, 확보)한 뒤, 해당 회선을 통해 메시지를 주고받는 방식이다.
  • 장점: 두 호스트 사이에 연결을 확보한 후 메시지를 주고받는 것이 보장된다는 특성 덕분에 주어진 시간동안 전송되는 정보의 양이 비교적 일정하다.
  • 단점: 회선의 이용 효율이 낮아질 수 있다. 가능한 모든 회선에 끊임없이 메시지가 흐르고 있어야만 회선의 이용 효율이 높아진다.

  • 메시지를 거의 주고받지 않으면서 회선을 점유하고 있다면 낭비하는 것이다.

• 회선 스위치 : 회선 교환 방식으로 메시지를 주고받을 수 있도록 하는 네트워크 장비이다. 호스트 사이에 일대일 전송로를 확보한다.

(2) 패킷 교환 네트워크

• 패킷 교환 방식으로 메시지를 주고받는 네트워크이다. : 메시지를 패킷(packet) 단위로 쪼개어 전송하는 방식이다. 쪼개어 전송된 패킷들은 수신지에서 재조립된다. 쪼개어 전송되는 패킷들은 각기 다른 전송로를 통해 전송될 수 있으며, 수신지에 도착하는 순서가 일정하지 않다.

• 회선 교환 네트워크의 단점을 보완한다. 전송로의 이용 효율이 높고, 전송로의 공유가 더 쉽다. -> 현대 인터넷은 대부분 패킷 교환 방식을 이용한다.

• 패킷 스위치 : 패킷 교환 방식으로 메시지를 주고받을 수 있도록 하는 네트워크 장비이다. 패킷의 송수신지를 식별하고, 패킷이 이동할 최적의 경로를 결정한다. 라우터(router), 스위치(switch) 등.

3. 주소와 송수신지 유형에 따른 전송 방식

1) 패킷의 구조

패킷은 페이로드에 헤더 또는 트레일러가 붙어 있는 구조로 이루어져 있다.

(1) 페이로드(payload)

네트워크를 통해 주고받고자 하는 실질적인 데이터.

(2) 헤더(header), 트레일러(trailer)

부가 정보 또는 제어 정보.

2) 주소

• 송수신지를 특정할 수 있는 정보이다. -> 주소를 통해 다양한 유형의 수신지에 패킷을 전송할 수 있다. (단일 기기, 같은 네트워크 내 모든 기기, 같은 그룹에 속한 모든 기기 등.)
• 패킷의 헤더에 담기는 대표적인 정보 중 하나이다.
• IP 주소, MAC 주소 등.

3) 송수신지의 유형에 따른 전송 방식

앞서 주소를 통해 다양한 유형의 수신자에게 전송이 가능해진다고 했다. 이때, 각 송수신지의 유형에 따라 다음과 같은 여러 방식 중 한 가지를 사용한다.

(1) 유니캐스트(unicast)

• 하나의 수신지에 메시지를 전송하는 방식이다.
• 송신지와 수신지가 일대일로 메시지를 주고받는 경우에 사용된다.
• 가장 일반적인 송수신 형태이다.

  (2) 브로드캐스트(broadcast)

• 네트워크상의 모든 호스트에게 메시지를 전송하는 방식이다.
• 브로드캐스트 도메인(broadcast domain) : 브로드캐스트가 전송되는 범위. 사실상 네트워크 전체라고 보면 된다. LAN의 범위를 브로드캐스트 도메인으로 보는 경우가 많다.

  (3) 멀티캐스트(multicast)

• 네트워크 내의 동일 그룹에 속한 호스트에게 메시지를 전송하는 방식이다.

  (4) 애니캐스트(anycast)

• 네트워크 내의 동일 그룹에 속한 호스트 중 가장 가까운 호스트에게만 메시지를 전송하는 방식이다.

유니캐스트와 브로드캐스트가 가장 중요하다!

https://www.acmicpc.net/problem/3190

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

입력 첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력 첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

접근

완전히 까먹고 있었는데 내가 이 문제를 작년에 하다가 때려 쳤는지 IDE에 하다 만 코드가 처박혀 있더라... 지금 보니까 전혀 어려운 문제는 아닌데 그때 내가 많이 못하긴 했나보다^^

문제에서 하라는 대로 잘 구현하면 되는 시뮬레이션 문제였다. 상하좌우 중 한 방향으로 머리를 옮겨야 하기 때문에, 다음으로 머리를 옮겨야 할 방향을 direction이라는 변수에 저장해 관리해 주었다. 현재 초의 이동이 끝난 후 해당 초의 방향 변경이 있으면 해당 방향으로 머리를 방향을 갱신해주면 되고, 방향 변경이 없다면 그대로 두면 된다.

벽에 부딪혔는지 여부는 인덱스가 격자 범위 밖으로 나갔는지만 확인하면 되니까 어렵지 않았는데, 자기 자신의 몸과 부딪혔는지를 확인하려면 뱀의 몸이 어느 칸들에 걸쳐 있는지를 저장해야 했다. 처음에는 단순히 boolean 배열에만 저장을 했었는데, 이렇게 하니까 머리가 도달한 위치에 자기 자신의 몸이 있었는지는 바로 알 수 있었지만, 꼬리가 어디인지는 한 번에 알 수가 없었다. 그래서 덱을 추가로 활용했다. 덱의 앞 부분을 머리, 끝 부분을 꼬리로. 머리가 새로운 위치에 도달했다면 덱의 맨 앞에 추가하고, 해당 칸에 사과가 없다면 덱의 맨 끝에 있는 원소를 삭제함으로써 꼬리를 줄여주었다.

뱀의 방향 변환 정보는 시간순으로 주어진다는 조건이 없기 때문에 우선순위 큐에 넣어서 정렬을 해줬다. 매초가 끝날 때마다 우선순위 큐의 맨 위에 있는 방향 변환 정보의 초가 현재 초를 비교해서 같으면 방향 전환을 수행하는 식으로 구현했다.

구현

import java.io.*;
import java.util.*;

class Main {
    static class Movement {
        int time;
        char direction;
        Movement(int time, char direction) {
            this.time = time;
            this.direction = direction;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Movement> movements = new PriorityQueue<>((m1, m2) -> m1.time - m2.time);
        int N = Integer.parseInt(br.readLine());
        boolean[][] hasApple = new boolean[N][N];
        int K = Integer.parseInt(br.readLine());
        for (int k = 0; k < K; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());
            hasApple[row - 1][col - 1] = true;
        }
        int L = Integer.parseInt(br.readLine());
        for (int l = 0; l < L; l++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            movements.add(new Movement(Integer.parseInt(st.nextToken()), st.nextToken().charAt(0)));
        }

        int headRow = 0;
        int headCol = 0;
        int direction = 1; // 0: 위쪽, 1: 오른쪽, 2: 아래쪽, 3: 왼쪽
        boolean[][] hasBody = new boolean[N][N];
        Deque<int[]> bodies = new ArrayDeque<>();
        hasBody[0][0] = true;
        bodies.add(new int[] {0, 0});
        for (int sec = 1; sec < N * N; sec++) {
            if (direction == 0) {
                headRow--;
            } else if (direction == 1) {
                headCol++;
            } else if (direction == 2) {
                headRow++;
            } else {
                headCol--;
            }

            if (headRow < 0 || headRow >= N || headCol < 0 || headCol >= N || hasBody[headRow][headCol]) {
                System.out.println(sec);
                return;
            }
            hasBody[headRow][headCol] = true;
            bodies.addFirst(new int[] {headRow, headCol});

            if (hasApple[headRow][headCol]) {
                hasApple[headRow][headCol] = false;
            } else {
                int[] tail = bodies.pollLast();
                hasBody[tail[0]][tail[1]] = false;
            }

            if (!movements.isEmpty() && movements.peek().time == sec) {
                Movement nextMove = movements.poll();
                direction = (nextMove.direction == 'D')? direction + 1 : direction - 1;
                if (direction == 4) {
                    direction = 0;
                } else if (direction == -1) {
                    direction = 3;
                }
            }
        }
    }
}

https://www.acmicpc.net/problem/1103

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

동전이 있는 곳에 쓰여 있는 숫자 X를 본다. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다. 만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

입력 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

출력 첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.

예제 입력 1 3 7 3942178 1234567 9123532 예제 출력 1 5

예제 입력 2 1 10 2H3HH4HHH5 예제 출력 2 4

예제 입력 3 4 4 3994 9999 9999 2924 예제 출력 3 -1

예제 입력 4 4 6 123456 234567 345678 456789 예제 출력 4 4

예제 입력 5 1 1 9 예제 출력 5 1

예제 입력 6 3 7 2H9HH11 HHHHH11 9HHHH11 예제 출력 6 2

접근

처음에 DP인가? 했었는데, 이 문제처럼 격자인데 상하좌우로 모두 이동할 수 있는 경우에는 어느 방향에서 왔는지를 알 수 없어 메모이제이션이 불가하다고 해서 DP로 못 풀 거라고 1차원적으로 생각했었다. 그래서 그냥 DFS로 풀었는데 시간 초과가 나서 분류를 보니까 DP 문제라는 거다... 생각해 보니까, 이 문제에서 메모이제이션해야 할 값은 지나온 경로나 방향에 전혀 의존하지 않고, 오직 동전을 움직인 횟수에만 의존하기 때문에 어느 방향에서 왔는지 따위는 전혀 영향을 주지 않았다. 무작정 안 된다고 생각하지 말고 생각이란 걸 좀 하자... 아무튼 그래서 기존에 DFS(재귀)로 구현한 코드에 메모이제이션 로직을 추가해서 코드를 수정했다.

이 문제에서 또 고민해봐야 하는 것이 사이클 판별이다. 사실 사이클 판별이라고 해서 대단한 건 없고 그냥 백트래킹 식으로 visited 배열을 관리하면서 visited[i][j]가 true인 위치에 다시 도달했다면, 왔던 자리로 다시 돌아올 수 있다는 뜻이니 사이클이 존재한다는 걸 알 수 있다. 사이클이 존재한다는 건 무한 번 움직일 수 있다는 뜻이니 -1을 출력해주면 된다.

구현

import java.io.*;
import java.util.*;

class Main {
    static int N;
    static int M;
    static int[][] board;
    static boolean[][] visited;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new int[N][M];
        visited = new boolean[N][M];
        dp = new int[N][M];
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                board[i][j] = (input.charAt(j) == 'H')? 0 : input.charAt(j) - '0';
                dp[i][j] = -1;
            }
        }

        visited[0][0] = true;
        System.out.println(dfs(0, 0));
    }

    private static int dfs(int row, int col) {
        if (dp[row][col] >= 0) {
            return dp[row][col];
        }
        if (board[row][col] == 0) {
            return 0;
        }

        int[] dx = {-1 * board[row][col], board[row][col], 0, 0};
        int[] dy = {0, 0, -1 * board[row][col], board[row][col]};

        for (int i = 0; i < 4; i++) {
            int nextRow = row + dx[i];
            int nextCol = col + dy[i];
            if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M) {
                dp[row][col] = Math.max(dp[row][col], 1);
                continue;
            }
            if (visited[nextRow][nextCol]) {
                System.out.println(-1);
                System.exit(0);
            }

            visited[nextRow][nextCol] = true;
            dp[row][col] = Math.max(dp[row][col], dfs(nextRow, nextCol) + 1);
            visited[nextRow][nextCol] = false;
        }

        return dp[row][col];
    }
}

https://www.acmicpc.net/problem/1600

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다.

근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다.

이제 원숭이는 머나먼 여행길을 떠난다. 격자판의 맨 왼쪽 위에서 시작해서 맨 오른쪽 아래까지 가야한다. 인접한 네 방향으로 한 번 움직이는 것, 말의 움직임으로 한 번 움직이는 것, 모두 한 번의 동작으로 친다. 격자판이 주어졌을 때, 원숭이가 최소한의 동작으로 시작지점에서 도착지점까지 갈 수 있는 방법을 알아내는 프로그램을 작성하시오.

입력 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.

출력 첫째 줄에 원숭이의 동작수의 최솟값을 출력한다. 시작점에서 도착점까지 갈 수 없는 경우엔 -1을 출력한다.

예제 입력 1 1 4 4 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 예제 출력 1 4

예제 입력 2 2 5 2 0 0 1 1 0 0 0 1 1 0 예제 출력 2 -1

접근

처음에 DFS+DP로 접근했다가 한 3프로쯤에서 틀렸다... 이 문제처럼 이동 방향이 한 방향으로 정해져 있지 않으면 부분 문제로 쪼개지지가 않아서 DP로 못 푸는데 이걸 간과하고 너무 생각 없이 풀었다ㅠ 그리고 BFS로 풀면 최단 거리 발견하는 즉시 바로 종료하니까 깊이가 별로 안 깊어지는데 DFS(재귀)로 푸니까 스택 오버플로우 문제도 있었다. 최단 거리니까 BFS로 풀면 되는데 왜 그랬을까...... 그냥 일반적인 BFS 하듯이 큐에 넣는데, 말처럼 이동하는 횟수를 함께 관리해주는 식으로 구현하면 쉽게 풀 수 있었다.

구현

import java.io.*;
import java.util.*;

class Main {
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[] horseX = {2, -2, 2, -2, 1, -1, 1, -1};
    static int[] horseY = {1, -1, -1, 1, -2, 2, 2, -2};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int W = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());
        boolean[][] isPlain = new boolean[H][W];

        for (int h = 0; h < H; h++) {
            st = new StringTokenizer(br.readLine());
            for (int w = 0; w < W; w++) {
                if (st.nextToken().charAt(0) == '0') {
                    isPlain[h][w] = true;
                }
            }
        }

        if (W == 1 && H == 1) {
            System.out.println(0);
            return;
        }

        boolean[][][] visited = new boolean[H][W][K + 1];
        Queue<Status> queue = new LinkedList<>();
        queue.offer(new Status(0, 0, 0, 0));
        visited[0][0][0] = true;
        while (!queue.isEmpty()) {
            Status curr = queue.poll();
            if (curr.horseCount < K) {
                for (int i = 0; i < 8; i++) {
                    int nextRow = curr.row + horseX[i];
                    int nextCol = curr.col + horseY[i];
                    if (nextRow >= 0 && nextRow < H && nextCol >= 0 && nextCol < W
                            && isPlain[nextRow][nextCol] && !visited[nextRow][nextCol][curr.horseCount + 1]) {
                        if (nextRow == H - 1 && nextCol == W - 1) {
                            System.out.println(curr.moveCount + 1);
                            return;
                        }
                        visited[nextRow][nextCol][curr.horseCount + 1] = true;
                        queue.offer(new Status(nextRow, nextCol, curr.horseCount + 1, curr.moveCount + 1));
                    }
                }
            }
            for (int i = 0; i < 4; i++) {
                int nextRow = curr.row + dx[i];
                int nextCol = curr.col + dy[i];
                if (nextRow >= 0 && nextRow < H && nextCol >= 0 && nextCol < W
                        && isPlain[nextRow][nextCol] && !visited[nextRow][nextCol][curr.horseCount]) {
                    if (nextRow == H - 1 && nextCol == W - 1) {
                        System.out.println(curr.moveCount + 1);
                        return;
                    }
                    visited[nextRow][nextCol][curr.horseCount] = true;
                    queue.offer(new Status(nextRow, nextCol, curr.horseCount, curr.moveCount + 1));
                }
            }
        }

        System.out.println(-1);
    }

    static class Status {
        int row;
        int col;
        int horseCount;
        int moveCount;

        Status(int row, int col, int horseCount, int moveCount) {
            this.row = row;
            this.col = col;
            this.horseCount = horseCount;
            this.moveCount = moveCount;
        }
    }
} 

https://www.acmicpc.net/problem/15685

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대 0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

출력 첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

예제 입력 1 3 3 3 0 1 4 2 1 3 4 2 2 1 예제 출력 1 4

예제 입력 2 4 3 3 0 1 4 2 1 3 4 2 2 1 2 7 3 4 예제 출력 2 11

예제 입력 3 10 5 5 0 0 5 6 0 0 5 7 0 0 5 8 0 0 5 9 0 0 6 5 0 0 6 6 0 0 6 7 0 0 6 8 0 0 6 9 0 0 예제 출력 3 8

예제 입력 4 4 50 50 0 10 50 50 1 10 50 50 2 10 50 50 3 10 예제 출력 4 1992

접근

격자가 100*100 크기밖에 안 되기 때문에 일단 드래곤 커브를 잘 그리기만 하면 격자를 순회하면서 네 꼭짓점에 모두 마킹이 되어 있는지 직접 확인할 수 있겠다 생각했다.

그래서 이 드래곤 커브를 어떻게 그리느냐가 문제였는데, 이전 세대 전체를 그대로 회전한다고 생각하면 너무 어려웠고, 이전 세대에서 마지막으로 도달한 점에서부터 맨 처음 시작점까지 거슬러 올라가며 회전했을 때의 알맞은 위치가 어디일지 찾아주는 식으로 했다.

항상 시계 방향으로 회전하기 때문에, 이전 세대의 선분을 반대 방향으로(다음 세대를 정방향으로 그리려면 반대 방향으로 따라가야 한다!) 거슬러 따라갔을 때

1. 이전 세대에서 위에서 아래로 갔으면 다음 세대에서는 오른쪽에서 왼쪽으로.
2. 이전 세대에서 왼쪽에서 오른쪽으로 갔으면 다음 세대에서는 위에서 아래로.
3. 이전 세대에서 아래에서 위로 갔으면 다음 세대에서는 왼쪽에서 오른쪽으로.
4. 이전 세대에서 오른쪽에서 왼쪽으로 갔으면 다음 세대에서는 아래에서 위로.

그려져야 한다는 규칙이 있었다. 이걸 따라서 다음 점이 어디에 찍힐지를 찾아서 마킹을 했다. 드래곤 커브가 겹쳐져 있어서 여러 번 마킹되더라도 아무 문제가 없다.

그리고 이 문제에서 또 소소하게 헷갈릴 수 있던 지점은 보통 x를 행, y를 열로 많이 생각하는데 이 문제에서는 x축이 열 방향, y 축이 행 방향이었다는 점이다. 그래도 입력에서 방향에 대해 친절하게 화살표까지 주며 알려줘서 실수하지 않고 풀었다.

구현

import java.io.*;
import java.util.*;

class Main {
    static boolean[][] isMarked = new boolean[101][101];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for (int n = 0; n < N; n++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            markDragonCurve(x, y, d, g);
        }

        int count = 0;
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if (isMarked[i][j] && isMarked[i + 1][j] && isMarked[i][j + 1] && isMarked[i + 1][j + 1]) {
                    count++;
                }
            }
        }

        System.out.println(count);
    }

    private static void markDragonCurve(int x, int y, int d, int g) {
        List<int[]> dragonCurves = new ArrayList<>();
        isMarked[y][x] = true;
        dragonCurves.add(new int[] {y, x});
        if (d == 0) {
            isMarked[y][x + 1] = true;
            dragonCurves.add(new int[] {y, x + 1});
        } else if (d == 1) {
            isMarked[y - 1][x] = true;
            dragonCurves.add(new int[] {y - 1, x});
        } else if (d == 2) {
            isMarked[y][x - 1] = true;
            dragonCurves.add(new int[] {y, x - 1});
        } else {
            isMarked[y + 1][x] = true;
            dragonCurves.add(new int[] {y + 1, x});
        }

        for (int i = 1; i <= g; i++) {
            increaseGeneration(dragonCurves);
        }
    }

    private static void increaseGeneration(List<int[]> path) {
        int size = path.size();
        for (int i = size - 2; i >= 0; i--) {
            int[] prev = path.get(i + 1);
            int[] curr = path.get(i);
            int[] last = path.get(path.size() - 1);
            if (prev[0] == curr[0]) {
                // 왼 -> 오
                if (prev[1] + 1 == curr[1]) {
                    isMarked[last[0] + 1][last[1]] = true;
                    path.add(new int[] {last[0] + 1, last[1]});
                } else { // 오 -> 왼
                    isMarked[last[0] - 1][last[1]] = true;
                    path.add(new int[] {last[0] - 1, last[1]});
                }
            } else {
                // 위 -> 아래
                if (prev[0] + 1 == curr[0]) {
                    isMarked[last[0]][last[1] - 1] = true;
                    path.add(new int[] {last[0], last[1] - 1});
                } else { // 아래 -> 위
                    isMarked[last[0]][last[1] + 1] = true;
                    path.add(new int[] {last[0], last[1] + 1});
                }
            }
        }
    }
}

https://www.acmicpc.net/problem/3015

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 $2^{31}$ 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력 서로 볼 수 있는 쌍의 수를 출력한다.

예제 입력 1 7 2 4 1 2 2 5 1 예제 출력 1 10

접근

그냥 음~ 단조 스택이네~ 이러고 풀기 시작했는데 영원히 $O(N^2)$ 풀이밖에 안 떠올랐다. 그리고 키가 동일한 사람이 연속해서 나올 때는 어떻게 처리해야 할지가 문제였다. 그래서 풀이를 봤는데, 스택에 (키, 해당 키의 연속 등장 횟수) 쌍을 저장하더라. 이 쌍을 (input, count)라고 해보자.

현재 키 input을 처리할 때

1. 스택 꼭대기의 키가 input보다 작은 동안 pop하며 ans += 그 묶음의 count.
2. 꼭대기 키가 input과 같으면 ans += 그 묶음의 count를 수행한다. (새롭게 추가된 사람과 이미 스택에 있던 키가 동일한 사람끼리는 모두 서로 볼 수 있기 때문.) 그리고 그 묶음의 count를 1 늘린다. 그 후, 스택에 그 묶음 아래에 뭐가 더 남아 있다면 (즉, 더 큰 키가 뒤에 있다면) 그 더 큰 키 1명도 더 보이므로 ans++.
3. 꼭대기 키가 input보다 커지면 ans++ 하고 (input,1)을 푸시.

모든 입력 키에 대해 위 과정을 반복하면 된다. 아 뭔가 무슨 얘긴지 알 것 같긴 한데 헷갈린다....

구현

import java.io.*;
import java.util.Stack;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long ans = 0;
        Stack<int[]> stack = new Stack<>(); // (키, 해당 키를 가진 사람이 몇 명 연속해 있는지)

        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(br.readLine());

            while (!stack.isEmpty() && stack.peek()[0] < input) {
                ans += stack.pop()[1];
            }

            if (stack.isEmpty()) {
                stack.push(new int[] {input, 1});
                continue;
            }

            int[] top = stack.peek();
            if (top[0] == input) {
                ans += top[1];
                top[1]++;
                if (stack.size() > 1) {
                    ans++;
                }
            } else {
                ans++;
                stack.push(new int[] {input, 1});
            }
        }

        System.out.println(ans);
    }
}

https://www.acmicpc.net/problem/15683

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.

CCTV의 최대 개수는 8개를 넘지 않는다.

출력 첫째 줄에 사각 지대의 최소 크기를 출력한다.

예제 입력 1 4 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 6 0 0 0 0 0 0 0 예제 출력 1 20

예제 입력 2 6 6 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 6 0 0 6 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 5 예제 출력 2 15

예제 입력 3 6 6 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 예제 출력 3 6

예제 입력 4 6 6 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 5 0 0 0 0 5 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 예제 출력 4 2

예제 입력 5 1 7 0 1 2 3 4 5 6 예제 출력 5 0

예제 입력 6 3 7 4 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 4 예제 출력 6 0

접근

N과 M의 최댓값이 8밖에 되지 않기 때문에, 말 그대로 모든 경우를 다 해보면 되는 브루트포스 문제이다. 입력을 받을 때 CCTV를 발견한 경우에는 별도의 리스트에 저장해두고, 리스트의 인덱스를 depth로 해서 백트래킹을 수행했다. CCTV의 각 방향을 1, 2, 3, 4로 번호를 매겨서 파라미터로 들어오는 방향 번호에 따라 CCTV를 회전하는 식으로 했는데, 그냥 그렇게만 간단하게 했으면 됐을 것을 초기 상태에서부터 바뀐 부분만 업데이트하려고 하니까 꼬여서 한 네 번 틀렸다 하...

구현

import java.io.*;
import java.util.*;

class Main {
    static int N;
    static int M;
    static char[][] office;
    static List<CCTV> CCTVs = new ArrayList<>();
    static int result = 64;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        office = new char[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                office[i][j] = st.nextToken().charAt(0);
                if (office[i][j] > '0' && office[i][j] < '6') {
                    CCTVs.add(new CCTV(i, j, office[i][j] - '0'));
                }
            }
        }

        backtracking(0);
        System.out.println(result);
    }

    private static void backtracking(int depth) {
        if (depth == CCTVs.size()) {
            result = Math.min(result, findBlindSpots());
            return;
        }

        CCTV curr = CCTVs.get(depth);
        int dirLimit = 4;
        if (curr.num == 2) {
            dirLimit = 2;
        } else if (curr.num == 5) {
            dirLimit = 1;
        }

        for (int dir = 1; dir <= dirLimit; dir++) {
            curr.changeDirection(dir);
            backtracking(depth + 1);
        }
    }

    private static int findBlindSpots() {
        char[][] copied = new char[N][M];
        for (int i = 0; i < N; i++) {
            copied[i] = new char[M];
            System.arraycopy(office[i], 0, copied[i], 0, M);
        }

        for (CCTV cctv : CCTVs) {
            if (cctv.up) {
                for (int i = cctv.row - 1; i >= 0; i--) {
                    if (copied[i][cctv.col] == '6') {
                        break;
                    }
                    if (copied[i][cctv.col] == '0') {
                        copied[i][cctv.col] = '7';
                    }
                }
            }
            if (cctv.down) {
                for (int i = cctv.row + 1; i < N; i++) {
                    if (copied[i][cctv.col] == '6') {
                        break;
                    }
                    if (copied[i][cctv.col] == '0') {
                        copied[i][cctv.col] = '7';
                    }
                }
            }
            if (cctv.left) {
                for (int i = cctv.col - 1; i >= 0; i--) {
                    if (copied[cctv.row][i] == '6') {
                        break;
                    }
                    if (copied[cctv.row][i] == '0') {
                        copied[cctv.row][i] = '7';
                    }
                }
            }
            if (cctv.right) {
                for (int i = cctv.col + 1; i < M; i++) {
                    if (copied[cctv.row][i] == '6') {
                        break;
                    }
                    if (copied[cctv.row][i] == '0') {
                        copied[cctv.row][i] = '7';
                    }
                }
            }
        }
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (copied[i][j] == '0') {
                    count++;
                }
            }
        }

        return count;
    }

    static class CCTV {
        int row;
        int col;
        int num;
        boolean up;
        boolean down;
        boolean left;
        boolean right;

        CCTV (int row, int col, int num) {
            this.row = row;
            this.col = col;
            this.num = num;
        }

        public void changeDirection(int direction) {
            if (num == 1) {
                if (direction == 1) {
                    up = false;
                    down = false;
                    right = true;
                    left = false;
                } else if (direction == 2) {
                    up = false;
                    down = true;
                    right = false;
                    left = false;
                } else if (direction == 3) {
                    up = false;
                    down = false;
                    right = false;
                    left = true;
                } else if (direction == 4) {
                    up = true;
                    down = false;
                    right = false;
                    left = false;
                }
            } else if (num == 2) {
                if (direction == 1) {
                    up = true;
                    down = true;
                    left = false;
                    right = false;
                } else if (direction == 2) {
                    up = false;
                    down = false;
                    left = true;
                    right = true;
                }
            } else if (num == 3) {
                if (direction == 1) {
                    up = false;
                    down = true;
                    right = true;
                    left = false;
                } else if (direction == 2) {
                    up = false;
                    down = true;
                    right = false;
                    left = true;
                } else if (direction == 3) {
                    up = true;
                    down = false;
                    left = true;
                    right = false;
                } else if (direction == 4) {
                    up = true;
                    down = false;
                    right = true;
                    left = false;
                }
            } else if (num == 4) {
                if (direction == 1) {
                    up = true;
                    down = true;
                    right = true;
                    left = false;
                } else if (direction == 2) {
                    up = false;
                    down = true;
                    right = true;
                    left = true;
                } else if (direction == 3) {
                    up = true;
                    down = true;
                    right = false;
                    left = true;
                } else if (direction == 4) {
                    up = true;
                    down = false;
                    right = true;
                    left = true;
                }
            } else {
                up = true;
                down = true;
                right = true;
                left = true;
            }
        }
    }
}

https://www.acmicpc.net/problem/20303

Trick or Treat!!

10월 31일 할로윈의 밤에는 거리의 여기저기서 아이들이 친구들과 모여 사탕을 받기 위해 돌아다닌다. 올해 할로윈에도 어김없이 많은 아이가 할로윈을 즐겼지만 단 한 사람, 일찍부터 잠에 빠진 스브러스는 할로윈 밤을 즐길 수가 없었다. 뒤늦게 일어나 사탕을 얻기 위해 혼자 돌아다녀 보지만 이미 사탕은 바닥나 하나도 얻을 수 없었다.

단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음을 먹는다. 다른 아이들보다 몸집이 큰 스브러스에게 사탕을 빼앗는 건 어렵지 않다. 또한, 스브러스는 매우 공평한 사람이기 때문에 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버린다. (친구의 친구는 친구다?!)

사탕을 빼앗긴 아이들은 거리에 주저앉아 울고 $K$명 이상의 아이들이 울기 시작하면 울음소리가 공명하여 온 집의 어른들이 거리로 나온다. 스브러스가 어른들에게 들키지 않고 최대로 뺏을 수 있는 사탕의 양을 구하여라.

스브러스는 혼자 모든 집을 돌아다녔기 때문에 다른 아이들이 받은 사탕의 양을 모두 알고 있다. 또한, 모든 아이는 스브러스를 피해 갈 수 없다.

입력 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ( $1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, $1 \leq K \leq \min\left{N, 3\ 000\right}$)

둘째 줄에는 아이들이 받은 사탕의 수를 나타내는 정수 $c_1, c_2, \cdots, c_N$이 주어진다. ( $1 \leq c_i \leq 10\ 000$)

셋째 줄부터 $M$개 줄에 갈쳐 각각의 줄에 정수 $a$, $b$가 주어진다. 이는 $a$와 $b$가 친구임을 의미한다. 같은 친구 관계가 두 번 주어지는 경우는 없다. ( $1 \leq a, b \leq N$, $a \neq b$)

출력 스브러스가 어른들에게 들키지 않고 아이들로부터 뺏을 수 있는 최대 사탕의 수를 출력한다.

예제 입력 1 10 6 6 9 15 4 4 1 5 19 14 20 5 1 3 2 5 4 9 6 2 7 8 6 10 예제 출력 1 57

예제 입력 2 5 4 4 9 9 9 9 9 1 2 2 3 3 4 4 5 예제 출력 2 0

접근

한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모두 뺏어야 하기 때문에 친구로 연결되어 있는 관계인 경우 하나의 집합으로 보면 된다. 유니온 파인드를 사용해 집합을 나누고, 각 집합에 속해 있는 친구의 수와 빼앗게 되는 사탕 수의 합을 구해주었다. 그리고 나서 K명 미만에게 뺏을 수 있는 사탕 개수의 최댓값을 구하면 되는데, 완전 탐색을 하면 시간 초과가 난다. K - 1을 가방 크기라고 생각하고 각 집합에 '속해 있는 친구 수'를 물건의 무게, '사탕의 수'를 물건의 가치라고 생각하면 0-1 knapsack 문제임을 알 수 있다.

구현

import java.io.*;
import java.util.*;

class Main {
    static int N;
    static int M;
    static int K;
    static int[] c;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        c = new int[N + 1];
        parent = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            c[i] = Integer.parseInt(st.nextToken());
            parent[i] = i;
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            union(a, b);
        }

        Map<Integer, int[]> map = new HashMap<>(); // (속해 있는 아이 수, 사탕 수)
        for (int i = 1; i <= N; i++) {
            if (!map.containsKey(find(i))) {
                map.put(parent[i], new int[2]);
            }
            map.get(parent[i])[0]++;
            map.get(parent[i])[1] += c[i];
        }

        int length = map.size();
        int[] dp = new int[K];
        int[][] children = new int[length + 1][2];
        int idx = 1;
        for (int[] child : map.values()) {
            children[idx][0] = child[0];
            children[idx++][1] = child[1];
        }
        for (int i = 1; i <= length; i++) {
            for (int j = K - 1; j >= children[i][0]; j--) {
                dp[j] = Math.max(dp[j], children[i][1] + dp[j - children[i][0]]);
            }
        }

        System.out.println(dp[K - 1]);
    }

    private static int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a > b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }
}

https://www.acmicpc.net/problem/17471

백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

아래 그림은 6개의 구역이 있는 것이고, 인접한 구역은 선으로 연결되어 있다.

아래는 백준시를 두 선거구로 나눈 4가지 방법이며, 가능한 방법과 불가능한 방법에 대한 예시이다.

공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 한다. 백준시의 정보가 주어졌을 때, 인구 차이의 최솟값을 구해보자.

입력 첫째 줄에 구역의 개수 N이 주어진다. 둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다. 인구는 공백으로 구분되어져 있다.

셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다. 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다. 모든 값은 정수로 구분되어져 있다.

구역 A가 구역 B와 인접하면 구역 B도 구역 A와 인접하다. 인접한 구역이 없을 수도 있다.

출력 첫째 줄에 백준시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력한다. 두 선거구로 나눌 수 없는 경우에는 -1을 출력한다.

제한 2 ≤ N ≤ 10 1 ≤ 구역의 인구 수 ≤ 100

예제 입력 1 6 5 2 3 4 1 2 2 2 4 4 1 3 6 5 2 4 2 2 1 3 1 2 1 2 예제 출력 1 1 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.

예제 입력 2 6 1 1 1 1 1 1 2 2 4 4 1 3 6 5 2 4 2 2 1 3 1 2 1 2 예제 출력 2 0 선거구를 [1, 3, 4], [2, 5, 6]으로 나누면 인구 차이가 0이다.

예제 입력 3 6 10 20 10 20 30 40 0 0 0 0 0 0 예제 출력 3 -1 두 선거구로 나눌 수 있는 방법이 없다.

예제 입력 4 6 2 3 4 5 6 7 2 2 3 2 1 3 2 1 2 2 5 6 2 4 6 2 4 5 예제 출력 4 9

접근

아 처음에 너무 이상하게 접근해서 시간을 너무 많이 버렸다...ㅜㅜ 그냥 백트래킹 하면서 구역을 일단 둘로 쪼갠 다음에 쪼개기가 끝나면 마지막에만 각 구역이 서로 연결되어 있는지 확인하면 코드도 훨씬 간단하고 시간 복잡도 면에서도 더 효율적인데, 처음부터 연결되어 있는 애들끼리 선택하려고 하다보니까 매 선택마다 연결 여부를 확인하는 미친 짓을 하다가 코드를 엎었다...^^ 아 너무 바보 같다. 생각을 좀 하면서 풀어야겠다고 생각했다.

구현

import java.io.*;
import java.util.*;

class Main {
    static int N;
    static int result = Integer.MAX_VALUE;
    static int[] population;
    static List<Integer>[] graph;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        population = new int[N + 1];
        graph = new List[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int n = 1; n <= N; n++) {
            population[n] = Integer.parseInt(st.nextToken());
            graph[n] = new ArrayList<>();
        }

        for (int n = 1; n <= N; n++) {
            st = new StringTokenizer(br.readLine());
            int total = Integer.parseInt(st.nextToken());
            for (int i = 0; i < total; i++) {
                int neighbor = Integer.parseInt(st.nextToken());
                graph[n].add(neighbor);
                graph[neighbor].add(n);
            }
        }

        backtracking(1, new ArrayList<>(), new ArrayList<>(), 0, 0);

        if (result == Integer.MAX_VALUE) {
            System.out.println(-1);
            return;
        }
        System.out.println(result);
    }

    private static void backtracking(int depth, List<Integer> A, List<Integer> B, int sumOfA, int sumOfB) {
        if (depth > N) {
            if (isConnected(A, B)) {
                result = Math.min(result, Math.abs(sumOfA - sumOfB));
            }
            return;
        }

        A.add(depth);
        sumOfA += population[depth];
        backtracking(depth + 1, A, B, sumOfA, sumOfB);

        A.remove(A.size() - 1);
        sumOfA -= population[depth];
        B.add(depth);
        sumOfB += population[depth];
        backtracking(depth + 1, A, B, sumOfA, sumOfB);
        B.remove(B.size() - 1);
    }

    private static boolean isConnected(List<Integer> A, List<Integer> B) {
        if (A.isEmpty() || B.isEmpty()) {
            return false;
        }

        Queue<Integer> q = new LinkedList<>();
        Set<Integer> set = new HashSet<>(A);
        q.offer(A.get(0));
        set.remove(A.get(0));
        while (!q.isEmpty()) {
            int curr = q.poll();
            for (int neighbor : graph[curr]) {
                if (!set.contains(neighbor)) {
                    continue;
                }
                set.remove(neighbor);
                q.offer(neighbor);
            }
        }
        if (!set.isEmpty()) {
            return false;
        }

        set.addAll(B);
        q.offer(B.get(0));
        set.remove(B.get(0));
        while (!q.isEmpty()) {
            int curr = q.poll();
            for (int neighbor : graph[curr]) {
                if (!set.contains(neighbor)) {
                    continue;
                }
                set.remove(neighbor);
                q.offer(neighbor);
            }
        }
        return set.isEmpty();
    }
}

1.1. 엔티티 매니저

• 엔티티를 저장하고, 수정하고, 삭제하고, 조회하는 등 엔티티와 관련된 모든 일을 처리한다.
• 엔티티 매니저 팩토리에서 생성되며, 생성하는 비용이 거의 들지 않는다.
• 스레드 안전하지 않다. 따라서 하나의 엔티티 매니저에 여러 스레드가 동시에 접근할 경우 동시성 문제가 발생하므로 스레드 간 공유할 수 없다.
• 데이터베이스 연결이 꼭 필요한 시점(ex. 트랜잭션이 시작된 경우)이 되기 전까지는 데이터베이스와의 커넥션을 획득하지 않는다.

1.2. 엔티티 매니저 팩토리

• 엔티티 매니저를 생성하는 공장이다.
• 생성하는 비용이 상당히 크다. 따라서, 일반적으로 하나의 엔티티 매니저 팩토리만을 생성하여 애플리케이션 전체에서 공유하도록 설계되어 있다.
• 스레드 안전하다. 즉, 하나의 엔티티 매니저 팩토리에 여러 스레드가 동시에 접근해도 문제가 없다.

2. 영속성 컨텍스트(Persistence Context)

개념

• 엔티티를 영구 저장하는 환경이라는 뜻이다.
• 일반적으로 엔티티 매니저를 생성할 때 하나가 만들어진다.
• 엔티티 매니저는 영속성 컨텍스트에 엔티티를 보관하고 관리한다.
• 엔티티 매니저를 통해 영속성 컨텍스트에 접근할 수 있고, 영속성 컨텍스트를 관리할 수 있다.

2.1. 특징

2.1.1. 식별자 값을 통한 구분

영속성 컨텍스트는 엔티티를 식별자 값(@Id로 테이블의 기본 키와 매핑한 값)으로 구분한다. 따라서 영속 상태의 엔티티는 반드시 식별자 값을 가져야 한다. 엔티티에 식별자 값이 없으면 예외가 발생한다.

2.1.2. 1차 캐시

• 영속성 컨텍스트가 내부에 가지고 있는 캐시이다.
• 영속 상태의 엔티티가 모두 이곳에 저장된다.
• key(식별자 값)-value(엔티티 인스턴스) 형태로 저장된다. 식별자 값은 데이터베이스의 기본 키와 매핑되어 있기 때문에 기본 키는 영속성 컨텍스트에 데이터를 저장하고 조회하는 기준이 된다.

2.1.3. 트랜잭션을 지원하는 쓰기 지연(transactional write-behind)

엔티티 매니저는 트랜잭션을 커밋하기 직전까지 데이터베이스에 엔티티를 저장하지 않고 내부 쿼리 저장소(쓰기 지연 SQL 저장소)에 SQL을 차곡차곡 모아둔다. 그리고 트랜잭션을 커밋할 때 모아둔 쿼리를 데이터베이스에 보낸다(flush). 이것을 트랜잭션을 지원하는 쓰기 지연이라고 한다.

데이터베이스의 트랜잭션이라는 작업 단위가 이 쓰기 지연을 가능하게 한다. 커밋 시점에 쿼리 내용을 반영하기 때문에, 트랜잭션 커밋 직전에만 변경 내용을 데이터베이스에 보내 동기화하면 되는 것이다.

2.1.4. 변경 감지(dirty checking)

JPA에서는 엔티티의 변경 사항이 있을 경우 별도의 처리 없이도 데이터베이스에 자동으로 반영된다. 따라서 엔티티를 수정할 때 SQL 수정 쿼리를 작성할 필요 없이 단순히 엔티티를 조회한 후 데이터를 변경하기만 하면 된다. 변경 감지는 영속 상태의 엔티티에만 적용된다. 자세한 엔티티 수정 과정은 하단 동작 과정에 작성해 두었다.

• 스냅샷 JPA는 엔티티를 영속성 컨텍스트에 보관할 때 최초 상태를 복사해서 저장해두는데, 이것을 스냅샷이라고 한다.
• 플러시 시점에 스냅샷과 현재 엔티티의 상태를 비교함으로써 엔티티의 변경 여부를 감지*한다.

2.2. 플러시(flush)

영속성 컨텍스트에 새로 저장된 엔티티는 트랜잭션을 커밋하는 순간에 데이터베이스에 반영된다. 이렇게 영속성 컨텍스트의 변경 내용을 데이터베이스에 동기화하는 작업을 플러시(flush)라고 한다.

2.2.1. 플러시 동작 과정

1. 변경 감지가 동작해서 영속성 컨텍스트에 있는 모든 엔티티를 스냅샷과 비교하여 수정된 엔티티를 찾는다.
2. 수정된 엔티티에 대한 수정 쿼리를 생성한 후 쓰기 지연 SQL 저장소에 등록한다.
3. 쓰기 지연 SQL 저장소의 등록, 수정, 삭제 쿼리를 데이터베이스에 전송한다.

2.2.2. 영속성 컨텍스트 플러시 방법

• 직접 호출 em.flush()를 직접 호출하여 강제로 플러시한다. 사용할 일이 거의 없다.
• 트랜잭션 커밋을 통한 플러시 자동 호출 JPA는 영속성 컨텍스트의 변경 내용이 데이터베이스에 반영되지 않는 문제를 예방하기 위해 트랜잭션을 커밋할 때 플러시를 자동으로 호출한다.
• JPQL 쿼리 실행을 통한 플러시 자동 호출 작성된 JPQL을 실행하면 JPQL은 SQL로 변환되어 데이터베이스에서 엔티티를 조회한다. 그런데 영속성 컨텍스트가 플러시되기 전이라면 아직 변경 내용이 데이터베이스에 반영되지 않은 상태이기에 조회가 되지 않을 것이다. 이러한 문제를 예방하기 위해 JPA는 JPQL을 실행하기 전 플러시를 자동으로 호출한다.

2.2.3. 주의점

• em.find() 메서드를 호출할 때는 플러시가 실행되지 않는다.
• 플러시는 영속성 컨텍스트에 보관된 엔티티를 삭제하는 것이 아니다.

3. 엔티티의 생명주기

3.1. 비영속(new/transient)

엔티티 객체를 생성한 후 em.persist()를 호출하기 전, 순수한 객체 상태이다. 즉, 아직 데이터베이스에 저장되지 않았으며 영속성 컨텍스트와도 관계가 없는 상태이다.

3.2. 영속(managed)

em.persist()를 호출함으로써 엔티티 매니저를 통해 영속성 컨텍스트에 저장된 엔티티가 영속성 컨텍스트에 의해 관리되고 있는 상태이다. 영속 상태에 있는 엔티티는 em.find()나 JPQL을 통해서 조회된다.

3.2.1. 비영속/준영속 상태의 엔티티를 영속 상태로 변경

비영속/준영속 상태의 엔티티를 영속 상태로 변경하려면 병합을 사용하면 된다. merge(entity) 메서드를 호출하면 병합이 수행된다.

동작 과정은 다음과 같다.

1. merge()를 실행한다.
2. 파라미터로 넘어온 준영속 엔티티의 식별자 값으로 1차 캐시에서 엔티티를 조회한다.
3. 만약 1차 캐시에 엔티티가 없으면 데이터베이스에서 엔티티를 조회하고 1차 캐시에 저장한다.
4. 조회한 영속 상태의 엔티티에 파라미터로 받은 엔티티의 값을 채워 넣는다.
5. 영속 상태의 엔티티를 반환한다.

결과적으로 merge()는 다음과 같이 save or update 기능을 수행하게 된다.

1. 파라미터로 받은 엔티티가 영속 상태라면 해당 엔티티의 값을 파라미터로 받은 엔티티의 값으로 변경(병합)한다.
2. 파라미터로 받은 엔티티가 비영속/준영속 상태라면 파라미터로 받은 비영속/준영속 상태의 엔티티 정보를 가지고 새로운 영속 상태의 엔티티를 생성해 반환한다.

3.3. 준영속(detached)

영속성 컨텍스트가 관리하던 영속 상태의 엔티티가 영속성 컨텍스트에서 분리되어 더 이상 영속성 컨텍스트가 관리하지 않게 된 상태이다.

3.3.1. 영속 상태의 엔티티를 준영속 상태로 만드는 방법

• em.detach(entity) 특정 entity를 영속성 컨텍스트에서 분리해 준영속 상태로 만든다. 이 메서드를 호출하는 순간 1차 캐시부터 쓰기 지연 SQL 저장소까지 영속성 컨텍스트에서 해당 엔티티를 관리하기 위해 존재하던 모든 정보가 제거된다.
• em.close() 영속성 컨텍스트를 닫는다(종료한다). 영속성 컨텍스트가 관리하던 모든 영속 상태의 엔티티가 준영속 상태가 된다.
• em.clear() 영속성 컨텍스트를 초기화한다. 영속성 컨텍스트가 관리하던 모든 영속 상태의 엔티티가 준영속 상태가 된다.

3.3.2. 준영속 상태인 엔티티의 특징

1. 거의 비영속 상태에 가깝다. 준영속 상태의 엔티티는 영속성 컨텍스트가 제공하는 기능을 사용할 수 없다. 특히, 엔티티의 변경 사항 또한 감지되지 않기 때문에 변경 사항이 데이터베이스에 반영되지 않는다.
2. 식별자 값을 가지고 있다. 이전에는 영속 상태였기 때문이다.
3. 지연 로딩(Lazy Loading)을 할 수 없다. 지연 로딩은 실제 객체 대신 프록시 객체를 로딩해두었다가, 해당 객체를 실제로 사용할 때 영속성 컨텍스트에서 데이터를 불러오는 방법이다. 하지만 준영속 상태의 엔티티는 영속성 컨텍스트가 더는 관리하지 않으므로 지연로딩이 불가하다.

3.4. 삭제(removed)

엔티티를 영속성 컨텍스트와 데이터베이스에서 삭제한 상태이다. em.remove()를 호출함으로써 가능하다.

4. 동작 과정

4.1. 엔티티 조회

4.1.1. 과정

1. em.find()를 호출한다.
2. 영속성 컨텍스트의 1차 캐시에서 식별자 값으로 엔티티를 찾는다.
3. 영속성 컨텍스트에 찾는 엔티티가 있다면? : 데이터베이스를 조회하지 않고 메모리에 있는 1차 캐시에서 해당 엔티티를 조회한다. 영속성 컨텍스트에 찾는 엔티티가 없다면? : 엔티티 매니저는 데이터베이스를 조회해서 엔티티를 생성하고, 해당 엔티티를 1차 캐시에 저장한 후 영속 상태의 엔티티를 반환한다.

4.1.2. 엔티티 조회 시 1차 캐시를 이용함으로써 얻는 이점

1차 캐시에 저장되어 있는 영속 상태의 엔티티의 경우 데이터베이스를 거치지 않고 바로 반환된다. 이를 통해 다음과 같은 이점을 누릴 수 있다.

1. 성능 엔티티를 1차 캐시에 저장해 두고 바로 불러오면 데이터베이스를 조회할 필요가 없기에 성능상 이점을 누릴 수 있다.
2. 엔티티의 동일성 보장 동일한 엔티티에 대해 em.find(Entity.class, "entity1")를 반복해서 호출하더라도 영속성 컨텍스트는 1차 캐시에 있는 같은 엔티티 인스턴스를 반환한다. 따라서 동일한 엔티티에 대한 동일성 비교, 즉 참조 비교가 성공한다.

4.2. 엔티티 등록

4.2.1. 과정

1. em.persist(entity)가 호출된다.
2. 영속성 컨텍스트는 1차 캐시에 entity를 저장하면서 동시에 등록 쿼리를 만든다.
3. 만들어진 등록 쿼리를 쓰기 지연 SQL 저장소에 보관한다.
4. em.persist()가 호출될 때마다 2, 3번 과정이 반복되며 등록 쿼리가 쌓인다.
5. transaction.commit()이 호출되면 트랜잭션이 커밋된다.
6. 엔티티 매니저는 영속성 컨텍스트를 플러시한다. 이때 쓰기 지연 SQL 저장소에 모인 쿼리를 데이터베이스에 보내 변경 내용을 데이터베이스에 한꺼번에 동기화한다.
7. 실제 데이터베이스 트랜잭션을 커밋한다.

4.3. 엔티티 수정

4.3.1. 과정

1. transaction.commit()이 호출되면 트랜잭션이 커밋된다.
2. 엔티티 매니저 내부에서 flush()가 호출된다.
3. 엔티티와 스냅샷을 비교해서 변경된 엔티티를 찾는다.
4. 변경된 엔티티가 있으면 UPDATE 쿼리를 생성해서 쓰기 지연 SQL 저장소에 저장한다.
5. 쓰기 지연 저장소의 SQL을 데이터베이스에 보낸다.
6. 데이터베이스 트랜잭션을 커밋한다.

4.3.2. JPA가 생성 및 실행하는 UPDATE 쿼리의 특징

JPA는 기본적으로 UPDATE 쿼리 생성 시 수정된 특정 필드에 대해서만 값을 변경하지 않고, 엔티티의 모든 필드를 업데이트하도록 쿼리를 생성한다. 이렇게 하면 데이터베이스에 보내는 데이터 전송량이 증가한다는 단점이 있지만, 수정 쿼리가 항상 동일하기 때문에 다음과 같은 이점을 누릴 수 있다.

1. 애플리케이션 로딩 시점에 UPDATE 쿼리를 미리 생성해두고 재사용하는 것이 가능하다.
2. 데이터베이스에 동일한 쿼리를 보내면 데이터베이스는 이전에 파싱된 쿼리를 재사용할 수 있다.

4.4. 엔티티 삭제

4.4.1. 과정

1. em.find()를 호출해 삭제하고자 하는 엔티티를 조회한다.
2. em.remove()를 호출하고, 앞서 조회한 삭제 대상 엔티티를 파라미터로 넘겨준다.
3. 삭제 쿼리를 쓰기 지연 SQL 저장소에 저장한다.
4. transaction.commit()이 호출되면 트랜잭션이 커밋된다.
5. 엔티티 매니저 내부에서 flush()가 호출된다.
6. 쓰기 지연 저장소의 SQL을 데이터베이스에 보낸다.
7. 데이터베이스 트랜잭션이 커밋되며 데이터베이스에 전달된 삭제 쿼리가 실행된다.

삭제된 엔티티는 재사용하지 않고 자연스럽게 가비지 컬렉션의 대상이 되도록 두는 것이 좋다.

객체와 RDB 간의 패러다임 불일치 문제

비즈니스 요구사항을 정의한 도메인 모델을 객체로 모델링하면 객체지향 언어가 가진 장점들을 활용할 수 있다. 하지만 문제는 객체 인스턴스를 생성한 후이다.

• RDB는 데이터 중심으로 구조화되어 있고, 집합적인 사고를 요구한다.
• 객체 지향에서의 추상화, 상속, 다형성 등의 개념이 존재하지 않는다.

이처럼 객체와 RDB는 지향점이 서로 다르므로, 둘의 기능과 표현 방법도 다르다. 그러므로 상속이나 참조 관계 등 복잡한 상태를 갖는 객체 구조를 RDB의 테이블 구조에 저장하는 데에는 어려움이 있다. 이러한 문제를 객체와 관계형 데이터베이스의 패러다임 불일치 문제라고 하며, 개발자가 중간에 이 문제를 해결해 주어야 한다. 문제는 이 불일치 문제를 해결하는 데에 너무 많은 시간과 코드가 소비된다는 것이다.

ORM을 통한 패러다임 불일치 문제 해결

ORM(Object-Relational Mapping)은 객체와 관계형 데이터베이스를 매핑한다는 뜻이다. ORM 프레임워크는 객체와 테이블을 매핑해서 위에 서술한 객체와 RDB 간 패러다임 불일치 문제를 개발자 대신 해결해 준다. 그래서 ORM 프레임워크를 사용하면 객체를 데이터베이스에 저장할 때라도 SQL문을 직접 작성하는 대신 객체를 자바 컬렉션에 저장하듯이 저장하면 된다. 그러면 ORM 프레임워크가 적절한 INSERT문을 생성해서 데이터베이스에 해당 객체를 직접 저장해준다. 즉, 객체와 테이블을 어떻게 매핑하고자 하는지 ORM 프레임워크에게 알려주기만 하면 ORM 프레임워크가 이후의 과정을 수행해주기 때문에, 개발자는 객체 지향 애플리케이션 개발에만 집중할 수 있게 된다. 자바 진영에서는 하이버네이트 프레임워크가 가장 많이 사용된다. 하이버네이트는 거의 대부분의 패러다임 불일치 문제를 해결해주는 성숙한 ORM 프레임워크이다.

JPA란?

JPA(Java Persistence API)는 자바 진영의 ORM 기술 표준이다. 즉, 자바 진영의 ORM 프레임워크 인터페이스를 모아둔 것이다. 따라서 JPA를 사용하려면 JPA를 구현한 ORM 프레임워크 중 하나를 선택해야 하는데, 앞서 언급했듯 이 중에서 하이버네이트가 가장 대중적이다.

JPA를 통한 패러다임 불일치 문제 해결 사례

1. 상속 JPA를 사용하면 자동으로 부모, 자식 테이블 각각에 데이터를 저장해주며, 조회할 때도 자동으로 부모-자식 테이블 간의 조인 쿼리를 생성 및 실행해준다.
2. 연관 관계 객체에서는 연관 관계가 참조로 표현되며, 참조를 통해 연관 객체에 접근한다. 반면 테이블에서는 연관 관계가 외래키로 표현되며, 조인을 통해 연관 테이블에 접근한다. JPA를 사용하면 개발자가 객체 간의 참조 관계를 설정하고 저장하기만 해도 JPA가 참조를 외래키로 변환하여 적절한 INSERT문을 데이터베이스에 전달한다. 그리고 조회할 때도 외래키를 참조로 변환해준다.
3. 객체 그래프 탐색 SQL을 직접 다루면 처음 실행하는 SQL에 따라 탐색할 수 있는 객체 그래프 범위에 제약이 생긴다. 하지만 JPA를 사용하면 연관된 객체를 사용하는 시점에 적절한 SELECT문을 실행해주는 즉시 로딩/지연 로딩 설정이 간단하게 가능하기 때문에 자유롭고 신뢰할 수 있는 객체 그래프 탐색이 가능하다.
4. 동일성 비교(참조 비교) 테이블 내에서 PK 값이 동일하다면 동일한 객체로 취급되어야 할 것이다. 하지만 JPA를 사용하지 않고 테이블에서 동일한 회원 객체를 2번 조회하면 조회 메서드가 호출될 때마다 새로운 인스턴스를 생성하게 되어 동일성 비교가 실패하게 된다. 반면 JPA를 사용하면 같은 트랜잭션일 때 같은 객체가 조회되는 것을 보장해주어 동일 컬럼에 대한 동일성 비교가 성공하게 된다.

https://www.acmicpc.net/problem/11286

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1 18 1 -1 0 0 0 1 1 -1 -1 2 -2 0 0 0 0 0 0 0 예제 출력 1 -1 1 0 -1 -1 1 1 -2 2 0

접근

양수의 경우 값이 작을수록 절댓값도 작고, 음수의 경우 반대로 값이 클수록 절댓값이 작다. 그러니까 배열에 있는 가장 작은 양수와 가장 큰 음수 간의 절댓값을 비교해서 더 작은 애를 출력하면 된다. 이를 위해서 양수를 저장하는 우선순위 큐와 음수를 저장하는 우선순위 큐를 따로 생성했다. 음수는 값이 큰 수가 먼저 나와야 하기 때문에 내림차순으로 설정해줬다.

구현

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> positive = new PriorityQueue<>();
        PriorityQueue<Integer> negative = new PriorityQueue<>(Collections.reverseOrder());
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(br.readLine());
            if (x == 0) {
                if (positive.isEmpty()) {
                    if (negative.isEmpty()) {
                        sb.append(0);
                    } else {
                        sb.append(negative.poll());
                    }
                } else {
                    if (negative.isEmpty()) {
                        sb.append(positive.poll());
                    } else {
                        if (positive.peek() >= Math.abs(negative.peek())) {
                            sb.append(negative.poll());
                        } else {
                            sb.append(positive.poll());
                        }
                    }
                }
                sb.append('\n');
            } else if (x > 0) {
                positive.offer(x);
            } else {
                negative.offer(x);
            }   
        }

        System.out.print(sb.toString());
    }
}

POJO 기반의 경량 컨테이너 제공

Spring Framework에서 개발자는 POJO 클래스를 개발하고 스프링 컨테이너는 이 POJO 객체(스프링 빈)를 관리한다. POJO 객체는 특정 기술에 종속되지 않는 순수 자바 객체를 의미한다. Spring Framework에서는 프레임워크의 메서드가 사용자 클래스에 구현되지 않아 프레임워크 코드와 사용자 코드 간의 결합이 느슨해진다. 개발자가 개발하는 클래스는 프레임워크의 코드와 분리되어 있어 개발자는 비즈니스 로직을 구현하는 데 집중할 수 있다.

복잡한 비즈니스 영역의 문제를 쉽게 개발하고 운영 가능하게 하는 설계 철학

제어의 역전(IoC, Inversion of Control)

객체의 생명 주기를 관리할 책임을 프레임워크(스프링 컨테이너, IoC 컨테이너)에 위임함으로써 개발자가 비즈니스 로직에 집중할 수 있도록 한다.

의존성 주입(DI, Dependency Injection)

제어 역전의 방법 중 하나이다. 사용할 객체를 직접 생성하지 않고 외부 컨테이너가 생성한 객체를 주입받아 사용하는 방식이다. 이렇게 하면 클래스 간의 복잡한 관계를 개발자가 직접 관리할 필요가 없게 된다.

스프링에서 의존성 주입을 받는 방법은 다음의 세 가지가 있다.

• 생성자 주입
• 필드 주입
• setter 주입

이중에서 스프링에서 권장하는 의존성 주입 방법은 생성자 주입인데, 그 이유는 다음과 같다.

1. 주입된 객체에 대한 불변성 확보 생성자 주입은 생성자의 호출 시점에 1회만 수행되는 것이 보장된다. 그래서 주입된 객체의 불필요한 변경을 막을 수 있다.
2. 테스트 코드 작성 용이 생성자 주입을 사용하면 스프링의 @Autowirde 없이도 컴파일 시점에 객체를 주입받아 테스트 코드를 작성할 수 있다. 즉, 프레임워크에 의존하지 않더라도 순수 자바 코드만으로 테스트 코드를 작성할 수 있게 된다.
3. final 키워드 사용 가능 final로 선언된 필드는 생성자에서 반드시 초기화가 이뤄져야 한다. 다른 주입 방법은 생성자 호출이 끝난 후 주입이 이뤄지기에 필드 객체를 final로 선언할 수 없는 반면, 생성자 주입을 사용하면 필드 객체에 final 키워드를 사용할 수 있어 컴파일 시점에 누락된 의존성을 감지할 수 있다.

관점 지향 프로그래밍(AOP, Aspect Oriented Programming)

AOP는 관점을 기준으로 묶어 개발하는 방식을 의미한다. 어떤 기능을 구현할 때 그 기능을 '핵심 기능'과 '부가 기능'으로 구분해 각각을 다른 관점으로 보는 것이다. 스프링은 부가 기능을 핵심 기능과 분리하는 기능을 제공함으로써 코드의 복잡성을 낮추고 재사용성을 높인다.

• 핵심 기능 비즈니스 로직이 처리하고자 하는 목적에 해당하는 기능이다. 상품 정보를 데이터베이스에 저장하고, 저장된 상품 정보 데이터를 보여주는 코드 등이 여기에 속한다.
• 부가 기능 비기능적 요구 사항에 해당하는 기능이다. 핵심 기능을 구현하기 위해 부수적으로 추가되는 기능이다. 비즈니스 로직 사이의 로깅 처리나 트랜잭션 처리 코드 등이 여기에 속한다.

AOP의 관점이 적용되지 않은 경우, 각 핵심 기능을 수행하는 로직마다 부가 기능을 수행하는 로직이 함께 구현이 되어 있을 것이다. 하지만 부가 기능이 수행해야 하는 로직은 모든 핵심 기능에 공통적으로 적용될 확률이 높기에 코드의 중복이 발생하게 된다.

반면 AOP의 관점에서는 이렇게 반복되는 부가 기능을 하나의 공통 로직으로 처리할 수 있도록 모듈화한다.어떤 핵심 기능이 수행되는지와 무관하게 로직이 수행되기 전 또는 후에 부가 기능이 수행될 수 있도록 하는 것이다. 이렇게 하면 모듈화된 객체를 편하게 적용할 수 있게 되어 개발자가 비즈니스 로직을 구현하는 데에만 집중할 수 있게 된다. 스프링에서는 프록시 패턴(Proxy Pattern)을 통해 AOP 기능을 제공하고 있다.

서비스 추상화(PSA, Portable Service Abstraction)

스프링 프레임워크는 수많은 기능을 일정한 수준의 추상화를 한 클래스로 제공하여 어떤 기능(구현체)를 사용하든지 간에 일관된 방식으로 접근할 수 있도록 한다. 대표적인 예가 트랜잭션 기능이다. 스프링 프레임워크에서는 데이터를 저장하여 객체를 계속 유지할 수 있도록 하는 다양한 영속성 프레임워크를 붙여 사용할 수 있다. 스프링 프레임워크가 RDB의 트랜잭션 기능을 정리한 PlatformTransaction 인터페이스를 제공함으로써 각 영속성 프레임워크에 적합한 구현 클래스를 제공하기 때문이다. 따라서 개발자는 어떤 구현체 혹은 프레임워크를 사용하더라도 추상화되어 있는 PlatformTranscationManager의 메서드만 사용하면 된다.

모듈식 프레임워크

스프링 프레임워크는 애플리케이션을 개발할 수 있는 여러 기능을 포함하고 있으며, 기능들을 성격에 따라 분류하여 '모듈'이라는 단위로 관리한다. 개발자는 필요한 모듈들을 조합하여 필요한 기능만 사용할 수 있다. 스프링 프레임워크는 약 20여개의 모듈로 구성되어 있다. 스프링 부트에서는 스프링 프레임워크의 모든 모듈을 기본으로 포함한다.

높은 확장성과 범용성

스프링 프레임워크는 여러 가지 기술과 연동 및 확장할 수 있는 다양한 형태의 프로젝트를 제공한다. 따라서 스프링 프레임워크를 사용하면 확장이 용이한 범용적인 애플리케이션을 만들 수 있다.

• Spring Batch
• Spring Security
• Spring Data

Spring Boot의 특징

스프링 부트의 목적

스프링 부트는 빠른 개발을 목적으로 '설정보다 관례'라는 패러다임을 채택한 프레임워크이다. 그래서 스프링 부트 프로젝트에서는 가장 보편적으로 많이 사용하는 형태로 스프링 애플리케이션을 미리 설정해 두었다. 직접 설정하는 대신 관례(CoC)에 맞게 코드를 작성하면 미리 설정된 형태로 애플리케이션을 개발할 수 있다. 기존 스프링 프레임워크로 개발할 때는 필요한 라이브러리를 찾고 애플리케이션에 적합한 버전을 선택하며 이를 설정하고 테스트하는 데 많은 시간이 필요했다. 스프링 부트는 컨트리뷰터와 커미터가 이미 적절한 라이브러리를 선택하고 이를 일반적인 형태로 설정하고 테스트까지 완료했기 때문에, 개발자는 그저 사용하기만 하면 되어 시간이 훨씬 단축된다.

스프링 부트에서 추가적으로 제공하는 기능들

모든 스프링 프로젝트는 스프링 프레임워크를 반드시 포함한다. 따라서 위에 작성한 스프링 프레임워크의 특징 역시 스프링 부트에도 적용된다. 그리고 스프링 프레임워크에서 제공하는 모든 기능을 스프링 부트에서도 똑같은 방법으로 사용할 수 있다. 그렇다면 스프링 부트가 추가적으로 제공하는 기능에는 무엇이 있을까?

단독 실행 가능한 스프링 애플리케이션

스프링 부트 프로젝트는 빌드 플러그인을 제공하고, 이를 실행하면 단독 실행이 가능한 JAR 파일을 만들 수 있다. 그리고 java 명령어와 -jar 옵션을 사용하면 간단하게 애플리케이션을 실행할 수 있다. 그래서 전통적인 배포 방법에 비해 매우 간단하고 빠르게 배포할 수 있다는 장점이 있다.

starter 의존성 제공

스프링 부트 프로젝트는 기능별로 라이브러리 의존성을 포함한 스타터(starter)를 제공한다. Gradle의 경우, build.gradle에 다음과 같이 의존성을 추가함으로써 사용할 수 있다.

dependencies {
    implementation 'org.springframework.boot:spring-boot-starter-data-jpa'
    implementation 'org.springframework.boot:spring-boot-starter-validation'
    implementation 'org.springframework.boot:spring-boot-starter-web'
    implementation 'org.springframework.boot:spring-boot-starter-actuator'
    implementation 'org.springframework.boot:spring-boot-starter-security'
    implementation 'org.springframework.boot:spring-boot-starter-oauth2-client'
}

스타터 내부에 라이브러리 의존성 설정이 포함되어 있어 한 줄만 추가하면 기능을 사용하는 데 필요한 모든 라이브러리를 한 번에 추가할 수 있다.

Auto Configuration 제공

스프링 부트의 모듈인 spring-boot-autoconfigure가 제공하는 자동 구성 기능은 특정 조건들이 충족되면 미리 설정된 자바 설정 클래스가 동작하고 애플리케이션을 구성할 수 있도록 한다. 자동 구성을 충족하는 특정 조건들은 여러 가지 형태이다. 예를 들어 애플리케이션에 특정 스프링 빈이 있거나 class path에 특정 라이브러리가 포함되어 있거나 환경 설정 값이 있으면 실행되는 방식이다. 그리고 이러한 특정 조건들은 다양하게 조합하여 사용할 수 있다.

health-check를 위한 actuator 제공

스프링 부트를 이용해서 애플리케이션을 개발했다면 기본 모니터링 지표와 헬스 체크 기능을 기본으로 제공한다. 그래서 모니터링 솔루션을 이용해서 각 서버들의 상태와 지표를 수집하기가 매우 쉽다. 이 기능을 제공하는 모듈이 spring-boot-actuator이다.

애플리케이션에 내장된 WAS

스프링 부트의 spring-boot-starter-web 스타터를 이용하여 웹 애플리케이션을 개발한 경우 톰캣이 내장되어 있다. 내장된 WAS 덕분에 앞서 언급한 단독 실행이 가능한 애플리케이션 배포가 가능하다. 톰캣 대신 다른 WAS가 필요하다면 쉽게 교체할 수 있다.

Spring Boot의 동작 과정

스프링 부트에서 spring-boot-starter-web 스타터를 사용하면 기본적으로 톰캣을 사용하는 스프링 MVC 구조를 기반으로 동작한다.

서블릿(Servlet)과 서블릿 컨테이너(Servlet Container)

서블릿은 클라이언트의 요청을 처리하고 결과를 반환하는 자바 웹 프로그래밍 기술이다. 서블릿을 사용하여 웹 페이지를 동적으로 생성할 수 있다. 그리고 이 서블릿이 관리되는 곳이 서블릿 컨테이너이다.

서블릿 컨테이너의 특징은 다음과 같다.

• 서블릿 인스턴스를 생성, 초기화, 호출, 종료하는 생명주기를 관리한다.
• 서블릿 객체는 싱글톤 패턴으로 관리된다.
• 멀티 스레딩을 지원한다.
• 톰캣은 WAS와 서블릿 컨테이너의 역할을 수행하는 대표적인 컨테이너이다.

DispatcherServlet

들어온 요청을 가장 먼저 받고, 요청을 적절하게 처리할 컨트롤러를 찾아서 정해주는 역할을 하는 서블릿이다. 다음과 같은 과정을 거쳐 동작한다.

1. DispatcherServlet에 요청(HttpServletRequest)이 들어온다.
2. DispatcherServlet은 핸들러 매핑(Handler Mapping)을 통해 요청 URI에 매핑된 핸들러(Controller)를 탐색한다.
3. 핸들러 어댑터(HandlerAdapter)를 통해 탐색된 컨트롤러를 호출한다.
4. 핸들러 어댑터에서 응답이 돌아오면 ModelAndView로 응답을 가공해 반환한다.
5. 뷰 형식으로 리턴하는 컨트롤러를 사용한 경우 뷰 리졸버(View Resolver)를 통해 뷰를 받아 리턴한다. @ResponseBody를 사용하면 뷰 리졸버를 호출하지 않고 MessageConverter를 거쳐 JSON 형식으로 변환해 리턴한다.

• 핸들러 매핑(Handler Mapping) 요청 정보를 기준으로 어떤 컨트롤러를 사용할지 선정하는 인터페이스이다. 여러 구현체를 가진다.
• 뷰 리졸버(View Resolver) ModelAndView 객체에 대해 응답 생성에 적절한 뷰를 결정하고 매핑하는 역할을 한다.
• 메시지 컨버터(MessageConverter) 요청과 응답에 대해 Body 값을 변환하는 역할을 수행한다. 스프링 부트는 자동 설정을 통해 HttpMessageConverter 인터페이스를 빈으로 등록해 사용한다. 해당 인터페이스를 기반으로 하는 구현체 클래스는 다양하며, Content-Type을 참고해서 이중에서 적절한 Converter를 선정한다.

https://www.acmicpc.net/problem/1946

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력 각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

예제 입력 1 2 5 3 2 1 4 4 1 2 3 5 5 7 3 6 7 3 4 2 1 4 5 7 2 5 6 1 예제 출력 1 4 3

접근

동석차가 있으면 문제가 어려울 뻔했지만,,, 동석차가 없어서 매우 쉬워졌다. 서류심사 순위를 기준으로 정렬을 한 후 정렬된 순서대로 면접 심사 순위를 확인하게 되면, 현재 확인하고 있는 지원자는 이전에 확인한 지원자보다 서류심사 순위가 낮음이 자명하게 된다. 그러니까 이전에 확인한 지원자 중 어느 한 명보다 면접 순위가 낮은지만 확인하면 된다. 한 명이라도 낮은 사람이 있으면 안 되기 때문에 현재까지 확인한 지원자 중 면접 순위가 가장 높은 사람의 순위를 저장해 놓고 그 값보다 작은지(순위가 높은지)만 확인하면 된다. 현재까지 확인한 지원자 중 면접 순위가 가장 높은 사람보다 면접 순위가 더 높다면, 해당 지원자는 선발하고 가장 높은 면접 순위를 갱신한 후 계속 확인하면 된다.

구현

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            int[][] ranks = new int[N][2];
            for (int n = 0; n < N; n++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                ranks[n][0] = Integer.parseInt(st.nextToken());
                ranks[n][1] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(ranks, (o1, o2) -> o1[0] - o2[0]);
            int max = ranks[0][1];
            int count = 1;
            for (int i = 1; i < N; i++) {
                if (ranks[i][1] < max) {
                    count++;
                    max = ranks[i][1];
                }
            }
            sb.append(count).append('\n');
        }
        System.out.print(sb.toString());
    }
}

프로그래머스에서 이 문제랑 비슷한데 동석차가 있는 형태의 문제를 풀었던 거 같은데 어떤 문제였는지 잘 기억이 안 난다... 찾아봐야지.

찾았다...! 인사고과라는 문제였다. 조만간 다시 한 번 풀어봐야겠다..

면접 보기 전까지의 과정

지난 달에 에타 학과 게시판에 현직자 선배님이 구글 여름 인턴 뽑는 중이라고 글 올려주신 걸 봤다. 될 가능성은 없다고 생각했지만 지원하는 건 무료고 ict 글로벌 인턴 준비하면서 영문 레쥬메 써둔 것도 있고 해서 걍 회사 이름만 구글로 바꿔서ㅋㅋㅋㅋ 제출했다.

무엇보다 인턴 공고글 보니까 최대한 빨리 지원해 달라고 해서 차일피일 미루는 거보다 빨리 내는 게 나을 거 같다 싶었다. 한국 기업들처럼 자기소개서 써라, 포트폴리오 내라 어쩌구 저쩌구 구구절절한 채용 절차가 없는 게 너무 좋더라. ict 글로벌 인턴십도 광탈하긴 했지만 그 짧은 시간 동안 없는 말 지어내고 플젝 부풀리느라 진이 다 빠졌는데 구글은 그런 거 하나도 없이 걍 다룰 줄 아는 기술 몇 개 선택하고 한 쪽짜리 레쥬메 하나만 띡 내도 된다. 오히려 장황한 것보다 그렇게 깔끔한 걸 더 선호한단다.

뭐 아무튼 제출하고 손가락 빨고 있었는데 한 3일쯤 뒤에 정말로 구글 직원분께 메일이 왔다.

난 솔직히 지원서를 읽기는 할까? 싶었는데 무려 3일만에 피드백이 오다니…

면접 일정 조율, 면접 언어 선택 등등 하기 위한 구글 폼이었는데 보자마자 바로 뚝딱 해서 제출했다.

그랬더니 진짜 면접 준비 안내 메일이 왔다….

설마 진짜 내가 구글 면접을 보나…?? 이왜진?

일단 보자마자 확인했다고 메일 답장 보냈는데

얼마 안 지나서 인터뷰 일정 잡혔다고 또 메일이 오는 거다….ㄷㄷ

지원서에 써 있는 내용은 진짜 별 게 없어서… 서류에서 걸러진 사람은 거의 없는 것 같다. 고작 그 정도 서류만 가지고 거르면 그건 또 그거대로 말이 안 되기 때문에… 병역 문제 비자 문제 없고 폼 제출한 사람들한테는 다 면접 기회를 준 게 아닌가 싶다.

난 딱히 한 것도 없는데 구글 인턴 면접 본다고 주변에 말하니까 다들 와 대단하다 축하한다 이래서 머쓱;;했다;;

그리고 생각보다 프로세스가 빠르게 진행돼서 놀랐다. 20일에 지원했는데 29일에 인터뷰 날짜 픽스되고 일주일 후 바로 인터뷰… 지원한 후 인터뷰 본 오늘까지 2~3주밖에 지나지 않았다.

인터뷰 준비

솔직히 처음에는 에이 내가 구글 인턴 면접을 준비한다고 되겠어? 이런 마인드였어서 별 생각이 없었다. 게다가 난 코테 준비가 거의 안 되어 있었기 때문에…

그래도 뭐라도 해야 되니까 구글링을 좀 해서 다른 분들의 인터뷰 후기를 찾아봤다.

그런데 한국 기업들의 코테 문제처럼 괴랄한 백준 골드 문제 이런 거보다 알고리즘 자료구조 기본기가 튼튼한지를 보는 문제들이 출제된다는 얘기들이 많았다. 그리고 문제를 맞혔느냐보다 인터뷰어와 어떻게 소통하는지, 어떻게 논리적으로 문제를 해결해 나가는지 그 과정을 주로 본다고 하더라.

(위 이미지를 클릭하면 유튜브 영상으로 연결됩니다.) 구글에서 올려준 예시 영상이다. 방향을 잡는 데 큰 도움이 됐다. 막 괴랄한 문제가 나오지 않는다는 것도 영상 속 문제를 보니까 좀 이해가 됐고.

구글 코리아 면접 후기 이분의 블로그 글도 도움이 많이 됐다!

무작정 한 번에 최상의 답을 내지 못하더라도, 인터뷰어와 소통하면서 자신의 코드의 문제를 파악하고 그걸 해결하기 위해서 어떤 알고리즘, 자료구조를 사용해야 하는지를 논리적으로 도출해 나가는 과정을 보고 싶어 하는 거 같았다. 괴랄한 문제를 지금 당장 풀어내지 못하더라도 이런 식의 논리적인 사고 흐름을 할 줄 아는 사람, 그리고 기본기가 탄탄한 사람은 인턴으로 입사했을 때 충분히 성장할 수 있다고 보는 게 아닐까?

인터뷰 후기를 이것저것 찾아보면서 아주 조금이나마 희망이 생긴 것 같았다. 왜냐면 코테 문제를 주야장천 푼 사람들은 내가 절대 이길 수가 없는데 이런 기본기는 대부분의 사람들의 이해도가 비슷할 것 같았다. 그리고 어려운 코테 문제는 푸는 방법을 모르면 아예 접근조차 어려운데 논리적인 문제 해결력 이런 건 단기간에 기르기 어렵지만 인터뷰 당일날 머리가 좀 잘 돌아가거나 나에게 잠재적인 천재성이 있다면(?) 좋은 인터뷰를 할 수도 있지 않을까 싶었다.

그래서 예전에 알고리즘 공부하면서 정리해뒀던 sorting, searching 알고리즘들이랑 스택 큐 set map 등등 자료 구조들 한 번에 모아서 컨닝 페이퍼 같은 걸 만들었다ㅋㅋ 자바로 구현해놨던 코드들이랑 시간 복잡도 다 정리해서. 그리고 자바 컬렉션에 있는 Vector Array Map Set 이런 것들 특징이랑 대표적인 메소드도 한 번 싹 훑었다. 이게 진짜 도움이 많이 됐다.

그리고 구글에서 추천해준 leetcode라는 사이트에서 미디엄 수준의 문제가 나온다길래 몇 개 찍먹해봤다. 들은 대로 막 난해하지는 않더라. 내가 아직 구현이 익숙지 못하니까 예시 코드들 구글링해가면서 이런 문제들은 이런 식으로 코딩하면 되겠구나~ 하는 감 정도만 익혔다. 백트래킹이나 dp 이런 거. 내가 지금껏 코테 문제 조금이나마 풀어보면서 느낀 게, 내가 아는 지식이 너무 부족한 상태에서 맨 땅에 헤딩을 하니까 오히려 잘못된 방향으로 코딩하면서 시간을 버리고 있는 것 같기도 했다. 그래서 이 코딩 인터뷰 준비하면서 이렇게 잘 된 코드들 리뷰하며 감을 먼저 익힌 다음에 문제 풀이를 하는 것도 괜찮겠다 싶은 생각을 했다. 마치 필사하듯이….

더 제대로 연습하고 싶었지만 시간이 얼마 없어서 일단 눈에 바르고 컨닝 페이퍼 참고하는 정도로 만족하기로 했다.

인터뷰 당일(오늘)

오늘 12시 반부터 첫 번째 인터뷰가 있었고, 2시 15분부터 두 번째 인터뷰가 있었다. 원래 학교 수업 듣는 중간 중간에 하려고 했는데 어차피 수업에 집중도 안 될 것 같고… 집에서 편하게 하는 게 나을 것 같아서 그냥 집에서 하기로 마음 먹었다. 근데…. 하필 오늘 아랫집에서 대공사를 하느라고 집안이 떠나갈 듯이 시끄러웠다. 결국엔 집을 나왔는데 카페에서 하긴 시끄러울 거 같고 스터디룸 대관해주는 곳도 없어서 진짜 약간 멘붕이 왔었다. 학원에까지 연락해서 잠깐 강의실 써도 되냐고 여쭤봤더니 12시 반이면 초딩들 올 시간이라고 하고… 스터디룸 있다는 근처 독서실은 갔더니 운영을 안 한다고, 대신 휴게실에서 하는 건 어떻겠냐고 하시더라…. 영어로도 면접 봐야 하는데 사람들 왔다 갔다 하면 신경 쓰일 거 같고, 너무 큰 소리 내면 안 된다니까 걱정돼서 처음에는 그냥 나왔는데, 인터뷰 시작 30분 전까지 장소를 못 찾아서 결국에는 그 독서실로 돌아가서 면접을 봤다. 근데 다행히 내가 있던 4시간 내내 휴게실에 사람이 거의 아무도 안 들어와서ㅋㅋ 나름 쾌적하게 면접 볼 수 있었다.

첫 번째 인터뷰

첫 번째는 영어 인터뷰였다. 맨 처음 메일로 받은 구글폼에서 둘 다 한국어로 할지, 한국어 한 번 영어 한 번 할지, 둘 다 영어로 할지 선택할 수 있었다. 인턴으로 입사하게 되면 영어 쓸 일이 많을 테니까 그래도 영어 조금은 한다는 걸 보여주면 좋지 않을까? 싶어서 한국어 한 번 영어 한 번으로 선택했는데 후회가 막심하다… ict 글로벌 인턴십이야 영어 실력이 중요했지만 이 구글 인턴십 인터뷰는 진짜 그냥 편한 언어 선택해서 봐도 상관 없는 거 같더라. 그걸 좀 나중에야 알았다. 그래서 바꿔 달라고 요청을 드릴까 하다가… 어차피 그 분들이 내 영어 실력 보려고 하시는 것도 아니고 의사 표시만 제대로 되면 된다고 생각해서 그냥 하기로 했다.

아무튼 첫 번째 영어 인터뷰가 시작됐는데, 시작하자마자 문제를 냅다 그냥 한 번에 영어로 쭉 읽어주셔서;; 처음에 하나도 못 알아들었다…. 나는 구글 독스에 쓰면서 설명해주시거나 문제를 보여주시거나 할 줄 알았는데 그냥 한 번 읽어주시고 끝이길래 존나 당황했다. 구글 미트에 있는 자막 기능을 켜둔 게 그나마 다행이었다… 그거 아니었으면 이해하는데 더 오래 걸렸을 것 같다. 못 알아들었다고 다시 한 번만 말씀해 달라고 했더니 그제야 테케로 예시를 보여주셨다. (혹시나 문제될까 싶어 구체적인 문제 내용은 생략합니다.) 들은 대로 진짜 straightforward한 문제…

처음에는 걍 (생략) 않을까요? 했는데 (생략)면 그땐 안 된다는 걸 뒤늦게 알았다. 그래서 어떻게 하지 하다가 (생략) 식으로 하겠다고 말씀드렸다. 아마 그렇게 하면 동작할 것 같다고 하시면서 좀 더 디벨롭해보겠냐, 바로 구현해보겠냐 하시길래 더 마땅한 게 떠오르지 않을 것 같아서 바로 구현해보겠다고 했다. 근데 내가 구글 독스 수정하는 게 인터뷰어 분 화면에는 안 보인다길래… 뭐 어떻게 해야 되나 얼타고 있다가 시간 허비했다;; 새로고침하니까 되더라… 이런 기술적인 문제가 생각보다 많은 것 같았다.

아무튼 일단 정렬해야 될 거 같아서 컨닝 페이퍼 보면서ㅋㅋㅋ 퀵소트 구현하고 나머지 부분도 뚝딱뚝딱 코딩하고 나서 그분이 이러이러하면 안 되지 않을까요? 하셔서 그거 고치고… 이 정도면 될까요? 했더니 코드에 문제가 좀 더 보이긴 하는데 시간이 끝났다면서 여기까지 하자고 하셨다.

아니 그리고… 수행 시간이 어떻게 되냐고 물어보셨는데 리스트 묶기 전에 퀵소트 한 건 까먹고 원소 5개씩 묶는 for문만 생각해서 O(N)이라고 했다;; 에라이… 하……

위에 임베드한 영상이나 다른 인터뷰 후기들 보면서 인터뷰어와 티키타카해가며 문제 푸는 그런 분위기를 생각했는데, 첫 번째 인터뷰어 분은 말씀을 거의 안 하셨다. 나도 말 안 하면 오디오가 비니까 그건 또 안 될 거 같아서 나 혼자 코드 설명해 가면서 코딩했는데 듣고는 계셨던 건지….. 피드백도 없으시고 묻는 질문에만 대답하시더라. 솔직히 별로 나와 얘기하고 싶지 않으신 것처럼 느껴졌다…… 벽 보고 혼자 떠드는 느낌. 그래서 뭔가 말 걸기도 조심스럽고 어색했다.

그리고 거기에 더해서 내 영어가 부족한 탓에 편하게 말을 못 이어가는 게 너무 답답했다. 말 한 마디 한 마디 할 때마다 생각을 해야 되니까 할 말도 안 하게 되고…. 나 영어 그래도 좀 늘었다고 생각했는데 아닌가보다^^

쩝… 잘한 건 같진 않지만 그래도 동작하는 구현 방향 생각해 낸 걸로 만족하기로 했다.

두 번째 인터뷰

두 번째 인터뷰는 한국어라 그나마 좀 마음이 편했다…^^

첫 번째와 두 번째 인터뷰 사이에 1시간이 비었는데 막간을 이용해 커피랑 초콜릿 사와서 먹으면서 마음의 준비를 했다.

두 번째 문제는 알고리즘이라기보다는 구현 문제였다. 두 번째 인터뷰어 분께서는 문제를 읽어주지 않으시고 구글 독스에 미리 써두셔서 읽고 하면 됐다. 근데 영어로 써 있어서… 솔직히 해석하는데 조금 애먹었다;; 로그 파일 입출력까지 직접 구현해야 하는 줄 알고 식겁했는데 알고 보니 그거 파싱해주는 메소드는 이미 있다고 가정하고 하는 거였다. 내 부족한 영어로 인하여…. 내가 이해를 잘 못하니까 부연 설명을 더 해주셔서 겨우 제대로 이해했다.

이해하고 보니까 이것도 대단히 어려운 문제는 아니었다. 근데 문제에 파싱 메소드의 리턴 데이터가 [(”사람1”, 5), (”사람1”, 7), (”사람2”, 5), … ] 이런 식으로 key value 형식으로 되어 있길래 나는 해시맵으로 리턴받으면 되나? 했는데 그게 아니라고 하셔서…. 뭐지 했는데 나한테 map이라는 자료구조의 특징을 말해달라고 하시더라. 그래서 그거 설명하면서 key 값이 중복될 수 있어서 해시맵에 저장하면 안 되는구나를 깨달았다.

(생략) 것이 문제의 의도였던 것 같다. 말씀해 주신 대로 클래스 정의하고 또 퀵소트 쓰고ㅋㅋ 대충 구현 마무리했다. 시간이 부족하니 퀵소트는 수도코드로만 작성해라, Map 메소드가 기억 안 나면 그냥 임의로 지정해서 해도 된다 하신 걸 보면 이 코드가 실제로 돌아가는지보다는 내가 프로그램의 전체적인 흐름을 파악하고 있는지를 중점적으로 보시려는 것 같았다.

두 번째 인터뷰를 진행하는 도중에는 내 버즈가 자꾸 연결이 끊겼다;; 지금껏 맥북에서 버즈 쓰면서 이랬던 적이 없는데 당황스러웠다. 중간에는 갑자기 인터뷰어 분 목소리가 안 들려서 나갔다 들어오기도 했다. 시간 꽤 허비했는데 이거 때문에 추가 시간 주시진 않더라ㅎ….

두 번째 인터뷰어 분은 첫 번째 분보다 훨씬 티키타카가 잘 됐고 말씀도 많이 해주셔서 좋았다. 역시 한국어여서 그랬던 것도 크고ㅎ 구현도 첫 번째보다는 훨씬 만족스럽게 한 것 같다. Map 관련 질문하신 것도 잘 대답했고 시간 복잡도도 O(NlogN)이라고 똑바로 말했다ㅋㅋ

그리고 이분께서는 5분 정도 남기고 질문할 시간도 주셨다. 솔직히 딱히 궁금한 게 없어서ㅋㅋㅋ 구글 밥이 진짜 맛있는지 이딴 거나 여쭤봤다;;; 쩝….

총평(?)

듣도 보도 못한 문제가 나와서 아무 것도 못하면 어쩌나 걱정했는데 그 정도의 상황은 펼쳐지지 않아서 그나마 다행이었다. 듣던 대로 정말 기본기에 충실한 문제들이었다.

면접 내내 그 흔한 지원 동기 한 번 물어보지 않으셨다. 쓰잘데기 없는 형식적인 절차 없이 본인들이 궁금해 하는 역량만을 45분동안 보려고 하는 게 느껴졌다. 여타 다른 기업 면접처럼 제가 뭘 할 줄 알아요. 저 이런 것도 해봤어요. 이러면서 뽐내는 자리가 아니라 정말 오직 CS 역량 그 하나만 보고 채용하는 것 같다. 다른 사람들의 화려한 포트폴리오를 보면 은근히 기죽을 때도 많았는데 구글은 그런 것들은 본인들이 잘 가르칠 수 있다는 자신감이 있고, 그보다 그런 지식들을 잘 받아들일 수 있는 사람인지, 그 알맹이를 보려는 것 같아서 좋았다.

이런 식의 코딩 인터뷰는 당연히 처음이었는데 생각보다 재밌었고 유익했다. 떨어지든 붙든 구글러 분들과 이야기할 수 있는 기회를 가졌다는 것 자체로 의미 있는 경험이었다. 지원하길 잘한 것 같다.

그래도 합격은 어렵겠지….? 라고 쓰지만 또 은근히 기대하고 있는 나ㅎ……

떨어지더라도 다음에 다시 도전해보고 싶다. 그땐 둘 다 한국어로…ㅋㅋㅋㅋㅋㅋㅋㅋ

이 글을 읽으시는 분들을 위해 덧붙이는 말

위 글은 제가 면접을 끝낸 당일 일기처럼 구구절절 쓴 글이라 조금은 생략된 내용이 많기에 보시는 분들을 위해 몇 마디 덧붙입니다.

1. 인터뷰가 이뤄지는 방식

위에 언급한 것처럼 인터뷰는 총 두 round로 진행됩니다. 한 round당 45분씩 진행되고, 인터뷰어 분들은 이후에 다른 분의 인터뷰 일정이 있으시기 때문에 45분이 진행되면 칼 같이 종료하십니다. 기술적인 문제가 있어서 잠시 지연됐더라도 추가 시간 같은 건 절대 주지 않습니다.

사전에 협의한 날짜와 시간에, 메일로 받은 구글 미트 링크로 접속하면 인터뷰어 분께서도 접속해 1대1로 화상 인터뷰가 진행됩니다. 코딩 인터뷰이기 때문에 코드를 작성해야 하는데, 이때 코드는 인터뷰이와 인터뷰어가 함께 접속해 있는 구글 독스에 작성합니다. 이 구글 독스는 ide가 아니기 때문에 여기에는 단순히 정답 코드만 작성하는 것이 아니라, 서로 간의 이해를 돕기 위해 그림을 그릴 수도 있고 메모장처럼 활용할 수도 있습니다. 이 구글 독스를 잘 활용하셔서 인터뷰어와 소통하며 문제 하나를 풀어나간다고 생각하시면 됩니다. 코드라는 결과보다도 45분이라는 시간 동안의 문제 해결 과정과 소프트 스킬을 보는 것이기 때문에 이 구글 독스를 잘 활용하셔야 합니다. 가능하다면 구글 독스보다 더 자유롭게 그림을 그릴 수 있는 화이트 보드가 비춰지는 곳에서 인터뷰를 보는 것도 매우매우 추천드립니다. 화이트 보드가 여의치 않다면 종이에 굵은 펜으로 그려서 화면에 보여주셔도 됩니다. (실제로 구글에서 이렇게 참여하도록 권장하고 있습니다.)

2. 드리고 싶은 말씀

위에도 어느 정도 녹아 있는 내용이긴 합니다만, 제가 느끼기에 중요했던 부분을 다시 한 번 정리해 드리고자 합니다.

1) 영어로 프리 토킹이 가능하지 않다면 무조건 한국어로 면접에 임할 것.

면접에서 사용하는 언어는 라운드 별로 사전에 지정할 수 있습니다.

물론 인턴으로 입사하게 된다면 영어를 매우 매우 자주 쓰게 되므로 영어 실력이 중요하다고 합니다.

하지만 인터뷰 과정에서는 한국인이 영어 면접을 선택했다고 해서 더 좋게 봐주거나 하지는 않는다고 합니다.

전 당시에 영어 과외 4개월차라 우매함의 봉우리에 있어서 제가 영어를 잘한다고 착각하고 패기 있게 첫 번째 라운드를 영어 면접으로 선택했다가 대차게 망했습니다.

여러분들은 저와 같은 실수를 하지 마시고 본인이 가장 편한 언어로 인터뷰에 임하시길 권합니다.

2) 최대한 빨리 지원할 것.

대략적인 서류 지원 마감 날짜가 정해져 있지만 마감 날짜가 지난 후부터 서류 심사를 하는 것이 아니고 바로 바로 서류를 받아 면접 날짜를 잡아주기 때문에 최대한 빠른 시일 내에 지원하는 것이 무엇보다 중요한 것 같습니다.

그래야만 인터뷰까지 갈 확률이 더 높아집니다.

3) 무작정 문제 풀이에 덤비지 말고, 충분히 질문해서 문제 풀이의 제한 사항이나 조건을 명확히 할 것.

문제 조건이 백준 문제처럼 명료하게 주어지지 않습니다. 그렇기 때문에 문제 풀이에서 애매하거나 정해져 있지 않은 것에 대해서는 반드시 질문하셔야 합니다. 무작정 답을 내려고 하는 것이 아니라 이러한 엣지 케이스도 하나 하나 고려하는지, 그 과정에서 어떻게 소통하는지 또한 중요한 평가 대상입니다. 질문을 드리면 답을 주기도 하고, 스스로 정의해 보라고 말씀해 주시기도 합니다.

• input data들이 서로 unique한지?
• input data가 정수가 아닐 수도 있는지?
• input의 범위가 어디부터 어디까지인지? 음수도 가능한지?
• output이 어떤 순서로 출력되어야 하는지?
• input이 정렬되어 주어지는지?

등등의 것들을 문제를 풀기 전 확인해 보고, 문제에 명확히 나와 있지 않다면 반드시 질문하시길 바랍니다.

4) 기본에 충실할 것.

https://youtu.be/6ZZX9iIgFoo?si=DmHg77FGSkmMCAXu

다음은 구글에서 업로드한 위 interview tip 영상에 언급된, 인터뷰이가 알아야 하는 자료구조와 알고리즘 목록입니다.

제가 구글 코딩 인터뷰를 준비하면서 가장 크게 느꼈던 것은 어마어마한 알고리즘 지식을 요구하는 것이 절대 아니라는 점입니다. 위에 나와 있는 기본적인 자료구조와 알고리즘에 대해서만 확실하게 숙지하시고, 어떤 상황에 그것들을 쓰는지(주어진 문제에 이 자료구조나 알고리즘이 적합한 이유가 무엇인지) 정확하게 설명할 수 있으시다면 충분하지 않을까 싶습니다.

https://www.acmicpc.net/problem/4195

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력 친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

예제 입력 1 2 3 Fred Barney Barney Betty Betty Wilma 3 Fred Barney Betty Wilma Barney Betty 예제 출력 1 2 3 4 2 2 4

접근

친구 관계가 생길 때마다, 즉 각 줄의 입력이 들어올 때마다 두 사람이 속해 있는 네트워크가 하나로 합쳐지므로 유니온 파인드로 분리 집합을 구현하면 되는 문제이다.

다른 분리 집합 문제와 조금 달랐던 부분은 다음과 같다.

1. 노드가 번호가 아닌 문자열 형태로 주어짐 보통 유니온 파인드는 정수 배열을 자신의 인덱스 값으로 초기화한 후 원소의 부모 노드에 인덱스로 접근하는데, 이 문제는 입력이 문자열로 주어져서 입력을 그대로 인덱스로 사용할 수가 없었다. 그래서 HashMap을 사용해서 각 입력 문자열을 정수 인덱스로 치환해 관리하는 식으로 구현했다.

2. 집합에 속하는 원소의 개수를 구해야 함 유니온 파인드를 수행하고 끝나는 게 아니라, 방금 유니온한 집합에 속해 있는 원소의 개수를 출력해야 했다. 개수 구하는 건 한 번도 해본 적이 없어서 처음에는 그냥 친구 관계가 생길 때마다 모든 배열 원소를 순회하며 parent 값이 동일한 원소의 개수를 세었는데, 이렇게 하니까 시간 초과가 났다. 찾아보니까 매번 셀 필요가 없고, 원소의 개수를 저장하는 배열을 따로 생성한 다음 유니온을 수행하는 시점에 합칠 두 집합의 원소 개수 값을 한 쪽으로 합쳐주면 되더라. 이렇게 개수 구하는 문제는 앞으로도 자주 보게 될 것 같아서 기억해둬야겠다고 생각했다.

구현

import java.io.*;
import java.util.*;

class Main {
    static int[] parent;
    static int[] size;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            Map<String, Integer> map = new HashMap<>();
            int F = Integer.parseInt(br.readLine());
            parent = new int[F << 1];
            size = new int[F << 1];
            for (int i = 0; i < (F << 1); i++){
                parent[i] = i;
                size[i] = 1;
            }

            int index = 0;
            for (int i = 0; i < F; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String a = st.nextToken();
                String b = st.nextToken();
                if (!map.containsKey(a)) {
                    map.put(a, index++);
                }
                if (!map.containsKey(b)) {
                    map.put(b, index++);
                }
                int parentA = find(map.get(a));
                int parentB = find(map.get(b));
                sb.append(union(parentA, parentB)).append('\n');
            }
        }
        System.out.print(sb.toString());
    }

    private static int find(int x) {
        if (x == parent[x]) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    private static int union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) {
            return size[a];
        }

        if (a > b) {
            parent[b] = a;
            size[a] += size[b];
            return size[a];
        }

        parent[a] = b;
        size[b] += size[a];
        return size[b];
    }
}

https://www.acmicpc.net/problem/1937

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력 첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력 첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

예제 입력 1 4 14 9 12 10 1 11 5 4 7 15 2 13 6 3 16 8 예제 출력 1 4

접근

시작점이 안 정해져 있는데 n이 500으로 크지 않고 시간 제한도 그래도 2초로 넉넉한 편이라 모든 칸에 대해 대해 각각을 시작점으로 해서 최대 이동 횟수를 구한 다음에 그중 최댓값을 찾아도 되겠다고 생각했다. 물론 무작정 탐색을 하면 당연히 안 되고... 이차원 배열에 현재 위치에서 시작해 이동할 수 있는 최대 칸 수를 메모이제이션해두어 불필요한 중복 탐색을 줄여야 한다. 어떤 칸에서부터 시작해서 이동할 수 있는 최대 칸 수는 max(상하좌우에 인접해 있는 칸에서부터 시작해서 이동할 수 있는 최대 칸 수 + 1)이다. 물론 상하좌우에 인접해 있더라도 현재 위치한 칸보다 작은 숫자로는 이동할 수 없다고 했으니 그 경우는 고려할 필요 없고. 어떤 칸을 시작점으로 했을 때의 최댓값을 이전에 이미 구한 적 있다면 그대로 쓰고, 구한 적 없다면 dfs로 더 이상 이동할 수 없을 때까지 (상하좌우에 현재 자신의 위치보다 큰 칸이 없을 때까지) 탐색해서 구하면 된다.

구현

import java.io.*;
import java.util.*;

class Main {
    static int n;
    static int[][] arr;
    static int[][] dp;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int answer = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                answer = Math.max(answer, dynamicProgramming(i, j));
            }
        }

        System.out.println(answer);
    }

    private static int dynamicProgramming(int row, int col) {
        if (dp[row][col] == 0) {
            dp[row][col] = 1;
            for (int i = 0; i < 4; i++) {
                int nextRow = row + dx[i];
                int nextCol = col + dy[i];
                if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n && arr[nextRow][nextCol] > arr[row][col]) {
                    dp[row][col] = Math.max(dp[row][col], 1 + dynamicProgramming(nextRow, nextCol));
                }
            }
        }

        return dp[row][col];
    }
}

dp와 dfs가 결합되어 있긴 한데 풀이 방향은 명확해서 어렵지 않게 풀었다.

https://www.acmicpc.net/problem/13334

집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다.

양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i ≤ n,이 주어져 있다. 여기서 hi와 oi는 사람 i의 집과 사무실의 위치이다. 길이 d의 모든 선분 L에 대하여, 집과 사무실의 위치가 모두 L에 포함되는 사람들의 최대 수를 구하는 프로그램을 작성하시오.

그림 1. 8 명의 집과 사무실의 위치

그림 1 에 있는 예를 고려해보자. 여기서 n = 8, (h1, o1) = (5, 40), (h2, o2) = (35, 25), (h3, o3) = (10, 20), (h4, o4) = (10, 25), (h5, o5) = (30, 50), (h6, o6) = (50, 60), (h7, o7) = (30, 25), (h8, o8) = (80, 100)이고, d = 30이다. 이 예에서, 위치 10 과 40 사이의 빨간색 선분 L이, 가장 많은 사람들에 대하여 집과 사무실 위치 모두 포함되는 선분 중 하나이다. 따라서 답은 4 이다.

입력 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,000이하의 서로 다른 정수이다. 마지막 줄에, 철로의 길이를 나타내는 정수 d (1 ≤ d ≤ 200,000,000)가 주어진다.

출력 출력은 표준출력을 사용한다. 길이 d의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다.

예제 입력 1 8 5 40 35 25 10 20 10 25 30 50 50 60 30 25 80 100 30 예제 출력 1 4

예제 입력 2 4 20 80 70 30 35 65 40 60 10 예제 출력 2 0

예제 입력 3 5 -5 5 30 40 -5 5 50 40 5 -5 10 예제 출력 3 3

슬라이딩 윈도우 이용

접근

예전에 풀다가 너무 열받아서 때려쳤던 2018 카카오 신입 공채 1차 추석 트래픽 문제랑 비슷한 느낌인 것 같다고 생각했다. 결국 그 문제를 제대로 못 풀긴 했지만 해설에서 윈도우를 사용해 풀 수 있다고 했던 걸 봤던 기억이 있어서 이 문제도 그런 식으로 접근해봤다. 좌표 전체 범위 내에서 윈도우를 1씩 이동시키면서 윈도우에 들어오는 입력은 넣고, 범위에서 벗어난 입력은 빼는 식이다. h와 o 중 더 작은 값을 start, 더 큰 값을 end라고 해보자.

1. 윈도우 범위 내에 들어온 새로운 원소 추가 문제에 따르면 start와 end 값 둘 다 철로 선분 안에 들어와 있어야 유효한 상태이기 때문에 end 값까지 윈도우 안에 들어와야 유효한지 판단할 가치가 생긴다. 그래서 아직 윈도우 안에 안 들어오고 대기 중인 입력들을 waiting이라는 우선순위 큐에 넣어두고, end 값이 작을수록 높은 우선순위를 갖도록 했다. 윈도우를 1 이동시킬 때마다 waiting에 있는 입력들 중 end 값이 윈도우 내에 있는 애들을 차례로 하나씩 확인하고, start까지 윈도우 내에 있으면 inRange(현재 윈도우에 있는 입력들을 저장하는) 우선순위 큐에 넣었다. start 값이 윈도우를 벗어나 있으면 그냥 버리고.

2. 윈도우 범위에서 벗어난 원소 삭제 inRange 내에서는 end 값이 아직 윈도우 범위 내에 있더라도 start 값이 윈도우를 벗어났다면 더 이상 유효하지 않다. 따라서 inRange는 start 값이 작을수록 높은 우선순위를 갖도록 했다. 윈도우를 1 이동시킬 때마다 inRange에 있는 입력들을 하나씩 확인하고, start 값이 윈도우를 벗어났다면 inRange에서 삭제했다.

위와 같은 식으로 우선순위 큐 2개를 이용해 구현을 했다.

구현

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Route> waiting = new PriorityQueue<>((r1, r2) -> r1.end - r2.end);
        int under = Integer.MAX_VALUE;
        int upper = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int o = Integer.parseInt(st.nextToken());
            if (h < o) {
                under = Math.min(under, h);
                upper = Math.max(upper, o);
            } else {
                under = Math.min(under, o);
                upper = Math.max(upper, h);
            }
            waiting.offer(new Route(h, o));
        }

        int d = Integer.parseInt(br.readLine());
        PriorityQueue<Route> inRange = new PriorityQueue<>((r1, r2) -> r1.start - r2.start);
        while (!waiting.isEmpty()) {
            Route next = waiting.peek();
            if (next.end > under + d) {
                break;
            }
            waiting.poll();
            if (next.start >= under) {
                inRange.offer(next);
            }
        }
        int result = inRange.size();
        for (int i = under + 1; i + d <= upper; i++) {
            // 윈도우를 벗어난 입력 제거
            while (!inRange.isEmpty() && inRange.peek().start < i) {
                inRange.poll();
            }
            // 새롭게 윈도우에 추가된 입력을 inRange에 추가
            while (!waiting.isEmpty()) {
                Route next = waiting.peek();
                if (next.end > i + d) {
                    break;
                }
                waiting.poll();
                if (next.start >= i) {
                    inRange.offer(next);
                }
            }
            result = Math.max(result, inRange.size());
        }

        System.out.println(result);
    }

    static class Route {
        int start;
        int end;
        Route (int h, int o) {
            if (h < o) {
                this.start = h;
                this.end = o;
            } else {
                this.start = o;
                this.end = h;
            }
        }
    }
}

시간 복잡도

이렇게 해서 정답 처리되긴 했는데, java 11로 제출한 사람 중 뒤에서 3등이라는 좀 불미스러운 실행 시간이 나왔다.

시간 복잡도를 생각해보면 윈도우 좌표를 1씩 이동시키고, 그때마다 우선순위 큐의 힙 연산(O(logN))을 수행하기 때문에 최종적으로 O((좌표범위) log n)이 된다. 문제에서 주어진 좌표 범위의 최솟값은 -1억, 최댓값은 +1억이기 때문에 최악의 경우 시간 복잡도가 O(2억logN)이 될 수도 있다. 그래서 시간 복잡도를 개선할 수 있는 다른 풀이를 찾아보았고, 그것이 아래에 있는 스위핑을 이용한 풀이이다.

스위핑 이용

접근

나는 윈도우를 한 칸씩 밀며 모든 가능한 철로 선분의 경우를 다 확인했는데, 사실 그럴 필요가 없었다. 왜냐하면 이 문제에서 윈도우 내 원소 개수가 바뀌는 지점은 어떤 입력 선분이 끝나는 순간에 한정되어 있기 때문이다. 철도 선분의 끝점이 변할 때만 윈도우 포함 여부가 달라지는 것이다. 그렇기 때문에 각 입력별 end 값을 윈도우 끝 경계로 하는 경우만 확인을 해줘도 충분하다. 그러니까 기본적인 흐름은 다음과 같다.

0. 입력쌍 중 start와 end 사이의 거리가 d를 초과하는 입력은 미리 버린다.
1. 입력을 end 값을 기준으로 오름차순 정렬해 리스트에 저장한다.
2. 리스트에 저장된 입력을 하나씩 확인한다.
3. 현재 확인하고 있는 입력을 기준으로 [end - d, end]라는 윈도우 사이에 몇 개의 집과 사무실 쌍이 있는지를 확인한다. (end값으로부터 스위핑)

1번에서 입력을 end 값 기준으로 오름차순 정렬하는 이유가 3번에서[end - d, end] 사이에 있는 입력쌍의 개수를 찾기 위함이다. 입력이 end 값 기준 오름차순 정렬되어 있으니 앞에서 확인한 입력은 현재 확인하고 있는 입력보다 end 좌표가 더 앞에 있었을 것이고, 이후에 확인할 입력은 end 좌표가 더 뒤에 있을 것이다. 그러니 [end - d, end] 범위 내의 입력들은 이전에 확인한 입력쌍들 중에 있을 것이다.

이전에 확인한 입력쌍들 중에서도 start 값 역시 이 범위 내에 있는 입력이라면 윈도우 범위 내에 있음을 알 수 있다. 위 사진에서 별 표시된 부분이 이전에 확인한 입력의 start 값이다. 두 start 값 모두 범위 내에 있고, 이전에 확인한 입력이니 end 값도 당연히 현재 end 값보다 작을 수밖에 없기에 현재 윈도우 내에 있는 입력쌍임을 알 수 있다.

end 값은 리스트를 순회할수록 커지기 때문에, 윈도우도 점점 뒤로 간다. 그러니 한 번 start 범위를 벗어난 입력이 다시 윈도우 내로 돌아올 수는 없다. 위 사진에서 세모에 해당하는 start 값은 윈도우 범위를 벗어났기 때문에 end 값이 범위 내에 있는지와 상관 없이 이후에도 더 이상 유효할 수 없다. 따라서 이 입력은 제거해주면 된다.

정리하면, 이후에 확인하게 될 입력쌍들은 신경을 안 써도 되고, 이전에 확인한 입력쌍들 중에서 start 값이 범위 내에 있는 게 몇 개인지만 확인하면 된다. 이를 위해서는 이미 확인한 입력쌍의 start 값만을 우선순위 큐에 저장하고, start 값이 작은 순으로 하나씩 확인하며 그 값이 [end - d, end] 범위에 있는지 확인하면 될 것이다.

구현

import java.io.*;
import java.util.*;

class Main {
    static class Interval {
        int s, e;
        Interval(int a, int b) {
            if (a <= b) { s = a; e = b; }
            else { s = b; e = a; }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        List<Interval> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int o = Integer.parseInt(st.nextToken());
            list.add(new Interval(h, o));
        }
        int d = Integer.parseInt(br.readLine());

        // 길이 d 초과는 제거
        List<Interval> cand = new ArrayList<>();
        for (Interval it : list) {
            if (it.e - it.s <= d) cand.add(it);
        }
        if (cand.isEmpty()) {
            System.out.println(0);
            return;
        }

        // end 오름차순, tie 시 start 오름차순
        cand.sort((a, b) -> {
            if (a.e != b.e) return Integer.compare(a.e, b.e);
            return Integer.compare(a.s, b.s);
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 시작점 최소힙
        int ans = 0;
        for (Interval it : cand) {
            pq.offer(it.s);
            int threshold = it.e - d;
            while (!pq.isEmpty() && pq.peek() < threshold) {
                pq.poll();
            }
            ans = Math.max(ans, pq.size());
        }
        System.out.println(ans);
    }
}

시간 복잡도

앞서 설명했듯 확인해야 하는 경우의 수가 입력의 개수로 한정된다. 그리고 각 입력에 대해 우선순위 큐의 힙 연산(O(logN))을 수행한다. 따라서 최종적인 시간 복잡도는 O(nlogN)이 된다. 여기서 n은 입력 값의 개수인데, 슬라이딩 윈도우를 사용했을 때에는 logN에 곱해지는 값이 최악의 경우 2억까지 될 수 있는 반면 n은 최대 10만에 불과하므로 보다 효율적이라고 할 수 있다.

처음에 소개한 추석 트래픽 문제에 대한 카카오 해설을 보면 '효율적인 알고리즘을 쓴다면 O(nlogn)으로 풀 수 있는 방법도 있다.'라고 하는데, 이 방법도 이것과 비슷한 맥락이 아닐까 싶다. 이 문제 풀다가 포기했었는데 조만간 다시 한 번 풀어보려고 한다.