0. 학습 목적크루스칼 알고리즘의 목적과 작동원리를 이해한다.최소 스패닝 트리가 무엇인지 이해한다.트리와 그래프의 차이점을 이해한다.1. 크루스칼 (Kruskal) 알고리즘이란?주어진 그래프 내에서 최소 스패닝 트리를 찾는 알고리즘이다.그리디한 방식을 진행되며, 내부에서 트리 구성원 여부를 가리기 위해 유니온 파인드를 활용한다. (1) 그래프와 트리의 차이둘 다 간선과 정점으로 이루어져 있지만, 다음 항목에서 차이를 보인다. 구분그래프트리사이클의 여부사이클이 존재할 수 있다.사이클이 없다.간선의 개수간선의 개수를 특정할 수 없다.정점이 N개라면 간선의 개수는 N-1개이다.(2) 최소 스패닝 트리란?그래프 내에 트리의 조건을 만족하면서도 가중치 비용이 최소 비용인 부분집합을 의미한다.여기서 트리의 조건은 ..

0. 학습 목적인터페이스의 구성요소에 대해 이해한다.인터페이스는 언제 쓰는지 이해한다.1. 인터페이스란?인터페이스 란, '무엇을 할 것인가' 에 대한 명세만 적혀있는 계약 형 추상 자료형이다.(1) 계약이란?계약은 실생활에서 상호 간에 지켜야 하는 약속을 말한다. 인터페이스는 사용자와, 또 그것을 구현하고자 하는 class와 두 번 계약을 하게 된다.사용자와의 계약: 사용자가 인터페이스 내 원하는 매서드를 규칙에 맞게 호출하면, 사용자가 예상하는 결과를 반환 해줘야 한다.구현체와의 계약: 구현체는 추상 매서드의 규칙 (인수, 반환값)을 준수하여 구현하여야 하고, 그것의 용도에 맞는 행동을 해야 한다.(2) 인터페이스 활용의 효과구현 분리와 느슨한 결합A. 구현 분리 = 논리적 결합도 낮춤인터페이스가 없었..

0. 학습 목적인덱스 머지가 무엇인지 이해한다.인덱스 머지의 종류인 교집합, 합집합, 정렬 후 합집합을 이해한다.1. 인덱스 머지란?Index Merge 란 하나의 테이블에서 두 개 이상의 인덱스를 활용하여 데이터를 선별하고 그 결과를 병합하여 쿼리를 처리하는 최적화 전략이다.만약 해당 옵션을 켜두지 않았다면, 옵티마이저는 쿼리를 처리할 때, 하나의 테이블에서는 오로지 하나의 인덱스를 활용한다.2. 사용되는 조건쿼리에 사용된 각각의 조건이 하나의 테이블 내의 서로 다른 인덱스를 활용할 수 있다.하나의 인덱스로만 처리했을 경우 범위 필터링 효과가 미미하다.3. 종류intersection: 각기 다른 인덱스로 필터링한 데이터들 사이의 교집합만 반환union: 각기 다른 인덱스로 필터링한 데이터들 사이에 합집..

0. 학습 목적인덱스 확장이 무엇인지 이해한다.인덱스 확장 전략의 장점을 이해한다.1. 인덱스 확장 이란?Index Extension은 InnoDB를 사용하는 테이블에서 보조 인덱스를 활용할 때, 그 보조 인덱스에 자동 추가된 PK도 함께 활용할 수 있게 할지 말지를 정하는 옵션이다. 해당 옵션을 활성화하면, 보조인덱스를 (보조 인덱스, PK) 로 된 복합 인덱스를 활용하는 것처럼 사용할 수 있다.다음과 같이 테이블이 있다고 해보자.-- 테이블 생성CREATE TABLE dept_emp ( dept_no INT NOT NULL, emp_no CHAR(4) NOT NULL, salary INT, from_date DATE NOT NULL, PRIMARY KEY (dept_no, ..

0. 학습 목적인덱스 컨디션 푸시다운의 정의를 이해한다.인덱스 컨디션 푸시다운이 활성화되었을 때와 비활성화 되었을 떄, 실행 계획이 어떻게 바뀌는지 이해한다.1. 인덱스 컨디션 푸시 다운이란?Index Condition Pushdwon(이하 ICP) 는 보조 인덱스를 활용하여 데이터를 가져오는 쿼리문에서 사용하는 최적화 전략이다.다음과 같이 진행되는 최적화를 ICP라고 한다.옵티마이저가 '범위를 줄일 수 없는 조건 컬럼이더라도' 보조 인덱스의 구성 요소로 존재하는 컬럼이면, 스토리지 엔진에게 전부 전달해준다.스토리지 엔진은 보조 인덱스를 탐색할 때, 옵티마이저에게 받은 조건 컬럼들로 최대한 유효하지 않은 튜플들을 걸러낸다. 이를 통해 스토리지 엔진이 본 테이블을 읽는 횟수를 줄인다. [!info] MyS..

0. 학습 목적iterator.next()를 활용하여 Collections의 자료구조들을 순회하면서, 자료 구조 내의 값들을 수정하려고 하면 ConcurrntModificationException이 나는 이유를 이해한다. Fail-Fast Interator와 Fail-Safe Iterator의 차이를 이해한다.1. Fail-Fast 전략과 Fail-Safe 전략Fail-Fast 전략 은 시스템 작동 중 실패 지점이 생기면 그 즉시 모든 작동을 멈추는 전략이다. 이는 실패 지점에 대한 명확한 판단과 일관성 유지를 목표로 한다.Fail-Safe 전략 은 시스템 작동 중 실패를 맞딱뜨린 상황에도 작동을 중단하지 않는다. 다만 최대한 실패가 커지지 않는 방향으로 나아가는 전략이다.Java는 Iterator 패턴..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/22861(1) 조건 분석 📊폴더 구조 형성 명령어맨 마지막에 1이 오면 폴더 간의 부모-자식 관계를 나타냄맨 마지막에 0이 오면 특정 폴더에 파일 삽입 명령어폴더 이동 명령어폴더 A, 폴더 B 구조로 알려주면 폴더 A를 B로 옮긴다.폴더 하위 파일 수 + 파일 유형 출력 명령어2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, 자료구조 먼저 개념을 나누고자 한다.직속 파일: 해당 폴더에 존재하는 파일이다.하위 파일: 해당 폴더의 하위 폴더 중 어딘가에 존재하는 파일이다.(0) 폴더의 종류를 구분하는 이유폴더 정리 (small)를 풀면서 직속파일과 하위파일을 구분없이 누적하여 풀었던 풀이자들은 해당 풀이..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/22860(1) 조건 분석 📊문제에서 요구하는 폴더의 하위 파일 종류와 개수를 출력하라.main 폴더 아래 같은 이름의 폴더는 2개 이상 존재할 수 없다.한 폴더는 자신의 레벨에서 같은 이름의 파일을 두 개 이상 가지지 못한다.```bash-- 불가능 예시FolderAㄴfile1ㄴfile1 # 2. 코드가 나오기까지 🛠️**`KEY WORD`: `자료구조`, `유니온파인드`** ## (0) 자료 구조 세팅해당 문제는 다음과 같은 이유로 HashMap 3개와 유니온 파인드용 `parents` 배열이 필요하다.1. 폴더 이름만 주어진다. 폴더 이름으로는 index 활용 풀이가 어렵다. - 계층 구조 표현 ..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/22859(1) 조건 분석 📊/* * 1. main 태그 지우기 v* 2. div 별로 구분 v* 3. div에서 title 추출해서 출력 v* 4. div 내부에 P태그 하나당 다음 과정 진행 * (1) P 태그 내부의 모든 태그 지우기 * (2) 문장 시작과 끝의 공백 지우기 * (3) 공백 2개짜리는 하나로 바꾼다. * (4) P 태그 자체를 지우기 * */ 2. 코드가 나오기까지 🛠️KEY WORD: 정규 표현식 정규 표현식으로 div 태그 추출 -> title만 빼서 출력정규 표현식으로 p 태그 추출 -> 위의 4가지 과정 하고 글만 출력(1)..

0. 학습 목적정규 표현식을 활용할 수 있는 Java 클래스들에는 무엇이 있는지 파악한다. 해당 클래스들의 매서드의 뜻과 사용법을 익힌다.1. 정규 표현식을 활용할 수 있는 Java 클래스java.util.regex에 있는 Pattern 클래스와 Matcher 클래스 활용String 클래스의 정규 표현식 사용 가능 매서드 활용2. Pattern과 Matcher 이해하기(1) Pattern 클래스정규 표현식을 컴파일하여 가지고 있는 클래스불변 객체 (한 번 정규 표현식 입력해서 컴파일하면, 이후 동일 Pattern 객체의 정규 표현식은 바꿀 수 없다.)Thread-Safe -> 여러 스레드에서 같은 Pattern 객체 공유 가능Pattern 클래스는 정규 표현식을 담고 있는 역할 밖에 하지 않는다. 문자열..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/22856(1) 조건 분석 📊중위 순회로 나오는 마지막 노드를, 문제에서 주어진 조건인 '유사 중위 순회' 방식으로 노드를 순회 했을 때, 몇 번의 이동만에 중위 순회 상 마지막 노드에 도달할 수 있는지 이동 횟수를 구해라여기서 이동이란 하나아ㅢ 노드에서 다른 노드로 한 번 움직이는 행위이다.2. 코드가 나오기까지 🛠️KEY WORD: DFS 중위 순회 마지막 노드 구하기유사 중위 순회 구현해서 마지막 노드까지의 방문 횟수 구하기(1) 시간복잡도 분석 ⏳최대 노드 개수가 $100,000$ 개 인데, DFS는 $O(V + E)$ 임으로, $200,000$ 개를 안 넘는다.3. 코드 🌐import java.i..

0. 학습 목적String Constant Pool 이라는 개념에 대해서 이해한다.String을 왜 불변 객체로 만들었는지 유추한다.1. String Constant Pool 이란?JVM Heap에 존재하는 메모리 공간으로 불변 객체인 String 리터럴 전용 저장 공간 이다.프로그램 내부에서 선언된 모든 String 리터럴은 String Constant Pool에 저장된다.2. 특징String Literal 만 저장Pool에 존재하는 문자열이 재 선언되면, 새로 할당하지 않고 있는 거 재활용 (1) String Literal 만 저장한다.String 객체 선언 방식은 2개로 나뉜다.// 리터럴 방식 선언String str1 = "Hello World";// 객체 방식 선언String str2 = new..

0. 학습 목적String은 불변 객체임을 이해한다.유용한 String 클래스 함수를 알아둬서 알고리즘 문제를 풀 때 적용한다.1. String의 특징 : 불변성String 객체의 가장 큰 특징은 불변성이 보장 되는 객체 라는 것이다.(1) final 클래스로 선언됨final 클래스로 선언되어 있어서 상속이 불가능하다.(2) 값을 담는 멤버 변수도 private final 임String 문자열의 실질적 값을 담는 byte 배열도 private final로 선언되어 있다. 이 때문에, String 객체가 한 번 선언되면, 이후 새로운 값을 재할당 할 수 없다.(3) 그렇다면 문자열 변경 코드나 함수는 어떻게 작동할까?원래의 String 객체에 값이 추가되는 것이 아니라, 새로운 String 객체가 만들어진..

0. 학습 목적MRR 옵션이 무엇인지, 작동 원리가 어떻게 되는지 이해한다.MRR과 BKA의 관계를 이해한다.BKA의 작동 원리에 대해 이해한다. 1. MRR (Multi-Range-Read) 이란?랜덤 I/O 접근을 순차 I/O 접근으로 변환하여 읽기 속도를 최적화하는 전략이다. 2. MRR 작동 원리-- 테이블 생성CREATE TABLE employees ( emp_no INT PRIMARY KEY, last_name VARCHAR(50), department VARCHAR(50), salary INT, hire_date DATE, INDEX idx_hire_date (hire_date))engine='innodb';-- 실행할 쿼리SELECT * FROM employ..

0. 학습 목적BNL 조인의 동작 과정에 대해 이해한다.BNL 조인이 왜 해시 조인이나 머지 소트 조인에 의해 밀려났는지 이해한다.BNL 조인과 BKA 조인의 차이점에 대해 이해한다.1. BNL 조인이란?조인 버퍼를 활용하여 드리븐 테이블 스캔 횟수를 줄이는 조인 방식.드라이빙 테이블의 유효한 레코드 하나 당, 드리븐 테이블 전체를 스캔해야 하는 NL 조인의 잦은 스캔 횟수를 줄이고자 나온 방식이다.2. BNL 조인의 동작 과정드라이빙 테이블에서 유효한 레코드를 발견하면, '조인에 필요한 컬럼만' 조인 버퍼에 저장조인 버퍼가 가득차거나, 드라이빙 테이블 읽기가 끝나면 다음 과정을 진행드리븐 테이블의 레코드를 순회하며 유효한 레코드를 만났을 경우, 조인 버퍼를 전체 순회한다.현재의 드리븐 레코드와 매칭되는..

0. 학습 목적BKA 조인의 작동 원리를 이해한다. BNL 조인과의 차이점을 이해한다. 1. BKA (Batch-Key-Access) 조인이란?조인 버퍼와 MRR 인터페이스를 활용하여, Nested Loop Join에서 문제가 되던 너무 많은 랜덤 I/O 접근을 한 번의 순차 I/O로 전환하여 최적화하는 조인전략을 말한다.2. BKA 조인의 과정드라이빙 테이블 스캔 후 조인 버퍼 적재Key Build (조인버퍼 각 행의 (조인 컬럼, 조인 버퍼 속 위치 offset) 튜플을 추출해 랜덤 버퍼에 적재) MRR 인터페이스 호출 (드리븐 테이블의 조인 컬럼으로 이루어진 보조 인덱스 활용하여 PK 값 추출 및 정렬) MRR 인터페이스가 드리븐 본 테이블 (클러스터링 테이블)을 3번에서 정렬한 PK 값 순으로 순..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/21922(1) 조건 분석 📊문제에 나온 물건 4가지에 따라 바람의 방향이 바뀌는 것을 나타내는 게 관건이다.2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, BFS 매번 사방 탐색하는 것이 아니고, 초기에 정한 방향을 물건을 만나지 않는 한 유지해야 한다.물건을 만나면, 그것에 맞게 방향을 바꿔줘야 한다.방향 배열을 썼고, 각 물건마다 함수화하여 그것에 맞게 방향을 바꿔주는 것으로 구현했다.(1) 시간복잡도 분석 ⏳최악의 경우 4방 움직임 모두가 전체 연구실을 돌 수도 있다. 그 경우를 계산해보면,$2,000 \times 2,000 \times 4 = 16,000,000$ 번의 연산 횟수가 된다.3..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/20165(1) 조건 분석 📊턴이 존재하고, 매 턴마다 공격자가 공격하고, 수비자가 수비한다.공격자의 행동은 다음과 같다.특정 도미노를 동서남북 중 한 방향으로 넘어트린다.해당 도미노의 길이-1만큼 그 방향의 도미노가 넘어진다.연쇄작용이 일어난다. (즉 넘어진 도미노의 길이만큼 그 이후 도미노가 추가로 더 넘어지고, 이것이 더 이상 넘어질 도미노가 없을 때까지 반복한다.) 수비자는 도미노 하나를 일으켜 세운다.2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, BFS 공격을 구현할 수 있느냐가 문제 풀이의 관건이었다.필자는 재귀가 시간 소모를 높이고 계산을 복잡하게 만들 것이라 판단되어 BFS로 이를 ..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/20164(1) 조건 분석 📊현재 조회 중인 수의 자릿수 중 홀수 인 자릿수의 개수 세기계산은 다음과 같이 진행현재 보는 수의 자릿수가 1이면 계산 종료자릿수가 2이면 두개로 쪼개서 더한 뒤에 1번부터 다시 시작자릿수가 3이상이면 임의로 3덩어리의 숫자로 쪼갠 뒤 전부 더하기. 이후 1번부터 다시 시작2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, 완탐문제에서 제시된 조건을 전부 표현하면 된다. 자릿수가 최대 9개이고, 재귀를 거듭할수록 자릿수의 개수는 줄어들 것이므로, 시간 초과 걱정은 없다.3. 코드 🌐import java.io.*;import java.util.*;public class Mai..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/17837(1) 조건 분석 📊A. 말에 대한 규칙말은 각자 나아가려는 방향이 있다.하나의 칸에 여러 말이 있을 시, 윷놀이처럼 기존에 있던 말이 새로 해당 칸에 온 말을 업는다. (stack)하나의 말이 자신의 방향으로 움직일 때 업힌 말들도 같이 움직인다. (이떄 자신의 나아가려는 방향은 바뀌지 않는다.)말들은 자신이 나아갈 다음 칸의 색깔에 따라 행동이 미세하게 바뀐다.B. 보드 칸 별 규칙흰 칸을 밟을 경우, 업은 말 전부 같이 움직이는 거 외에 특이 사항 없음빨간 칸을 밟을 경우, 자신을 포함한 업은 말들의 위치가 거꾸로 되어야 한다.(exA->B->C (TOP) 순으로 업혀 있었다면, C -> B -..

0. 학습 목적Spring에서 제어의 역전을 어떻게 구현했는지 이해한다.Spring에서 객체의 생성과 관리를 담당하는 컨테이너를 어떻게 생성하는지 이해한다.Spring에서 객체를 어떻게 해당 컨테이너에 등록하는지 이해한다.Spring에서 어떻게 객체를 주입하는지 이해한다.1. Spring에서는 IoC를 어떻게 구현했는가?Spring에서는 Spring IoC Container라는 객체 생성과 관리 전용 컨테이너를 만들어서 IoC를 구현하였다. Spring에서 IoC가 이루어지는 과정을 그려보면 다음과 같다.출처: javaguide.net과정을 말로 풀어보면,프로그램 시작 시, Spring IoC Cotainer가 ApplicationContext 구현체로 생성된다.컨테이너가 생성하고 관리할 객체를 찾는다...