Jira나 Linear을 이용하다보면, 가끔 내가 해결한 티켓들을 그대로 고이 모셔 두기가 너무 아깝다.
같은 프로젝트를 하더라도, 내가 이 사람보다 월등히 일을 많이 해결했는데 인정받지 못하는 순간이 아쉬워서
어떤 프로젝트(또는 회사) 안의 SubTask를 만들고, 그 Task 안에서 Ticket을 발부할 때마다 티켓의 중요도와 난이도를 가지고 인사평가를 할 수 있는 프로젝트를 만들었다.
그런데 프로젝트 도중 내부 회의를 하다가 이상한 점을 발견했다.
그동안의 점수 로직은 0~5까지의 0.5단위의 점수를 매길 수 있는 중요도와 난이도를 그냥 합산한 수치로 계산했는데,
나는 어쩔때는 예상 밖의 예외에 집착하고 많은 엣지케이스를 실험해 보는 습관이 있어서
내가 짠 로직들에 대해 악감정을 가지고 어떻게 해야 개발자를 골려먹을 수 있을까에 대해 실험해 보았다.
결과적으로는 이 로직을 악용하기에 충분했다. 모든 난이도와 중요도를 5점으로 설정해 놓으면 모든 사원이 만점을 받고, 정상적으로 난이도와 중요도를 매긴 타 업체나 타 프로젝트들에 비해 이 사람이 어떤 능력을 가진 사람인지 예상하기 힘들었고, 편애를 받는 사람은 그 사람이 가진 티켓의 난이도나 중요도만 상위 직급에 있는(Subtask나 Project장) 사람이 올려놓으면 다른 사람의 질타를 받기 충분했다.
토의
그럼 이 문제를 어떻게 해결할까 하다가 대학교 2학년때 배운 선형대수가 떠올랐다.
바로 'Weight Sum(가중합)'을 이용하는 것이다.
가중합이라고 하면 이름만 어렵지 사실은 우리가 옛날에 배운 기초 수학이다.
먼저, 우리가 여태 사용하던 평균을 구하는 공식을 가지고 예를 들어 보자.
국어
수학
음악
평균
영준
70
80
90
80
대현
100
100
40
80
영준이와 대현이는 공부를 열심히 했으나 둘 다 평균 80점을 받았다.
그런데 사실 대현이는 불만이 있었다. 수업 시수는 국어와 수학이 압도적으로 많은데, 비교과 내신인 음악 과목 때문에 결국 똑같은 평균 취급을 받아야 한다니..
대현이는 바로 교장선생님께 달려가서 이 부당함을 일렀고, 교장선생님은 이런 부당함을 없애기 위해 조치를 취했다.
바로 평균을 낼 때, 수업 시수를 고려한 평균을 내는 것이다.
국어
수학
음악
평균
수업
3
5
2
영준
70
80
90
79
대현
100
100
40
88
영준이는 ( 3 * 70 + 5 * 80 + 2 * 90 ) / (3+5+2) 인 평균 79점이,
대현이는 ( 3 * 100 + 5 * 100 + 2 * 40 ) / (3+5+2) 인 평균 88점이 나오게 됐다.
이렇게 영준이는 조금은 억울하지만 물론 쉬운 음악 과목을 날먹했으므로 억울함은 토로할 수 없었고,
대현이는 중요한 내신인 국어와 수학을 열심히 공부해서 좋은 평균을 냈으니 이보다 더 공정할 수는 없었다.
벡터의 내적또한 사실 가중합 방식과 같다.
이렇게 둘은 공평한 점수를 얻게 되었다.
이것이 가중합 방식이고, 수업 시수는 가중치라고 생각하면 된다.
이 방식을 이용해 조금 더 공평한 점수를 구할 수 있다.
적용
이를 적용하여 나름 공평한 시스템을 설계할 수 있었다.
티켓과 그 티켓을 담고 있는 하나의 '일'인 Task에 대해서 얼마나 진행되었는지를 조사한다.
티켓이 완료되지 않았다면 이 티켓에 대해 점수를 줄 수 없어야 하고,
티켓을 처리하여 완료시간이 나왔다면, 전체 진행도에 비해서 이 티켓을 얼마나 빨리 끝냈는가를 체크한다.
진행도는 '분 단위'를 기준으로 계산한다.
그리고는 아까 계산한 평균처럼 점수 * 가중치 / 전체를 계산한다.
DTO로 매핑하기 위한 소스코드를 첨부한다. 매핑 프레임워크는 Mapstruct를 사용하였다.
문제의 설명에 나온 대로 10장, 20장, 40장의 카드 묶음이 있을 때, (10+20)을 묶고, 이 30장짜리 카드묶음을 (30+40)으로 또 묶어버리면 100번의 비교가 필요하지만, (10+40)을 묶고, 50장짜리 카드묶음을 (50+20)으로 묶어버리면 120번의 비교가 필요하다.
결국 첫 번째 방법은 10 + 20 + 30(10+20) + 40 = 100이고
두 번째 방법은 10 + 40 + 50(10 + 40) + 20 = 120으로 해석할 수 있다.
따라서 먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 미치는 것을 알 수 있다.
묶음의 개수는 정해져 있으므로, 카드의 개수가 작은 순서대로 먼저 합쳐야 한다는 것을 알 수 있다.
그래서 작은 묶음의 데이터 2개를 뽑아서 계속 비교해나가므로 삽입, 삭제, 정렬이 자주 일어난다는것을 알 수 있다.
두 번째 문제로, '강의실 배정(11000)' 문제를 보자.
강의실 배정하기의 문제의 핵심은 '수업을 최대한 겹치지 않게' 배정하는 것이다.
수업 시작시간을 기준으로, 가장 빨리 끝나는 시간을 비교해서 같은 강의실 안에 최적으로 배치해서 최소한의 강의실을 이용해야 한다.
따라서 (1,3), (2,4), (3,5)의 수업이 주어졌을 때, 가장 일찍 시작하는 수업을 먼저 배치하고, 그 다음 수업들을 비교해서 다른 수업의 시작시간이 처음 고른 수업의 종료시각보다 느리면 우선순위큐에 넣는다.
위의 예제를 이용해 말로 풀어서 설명하면, 1시부터 3시까지 진행하는 수업을 강의실에 배치하고, 2시부터 4시까지 진행하는 수업은 아직 강의실이 비지 않았으니 새로운 강의실에 배치한다(pQueue.offer). 3시부터 5시까지 진행하는 수업은 우선순위큐의 top을 봤을 때(pQueue.peek) 3시에 끝나는 수업이 있으므로 이 수업을 꺼내고, 3시부터 5시까지 진행하는 수업을 넣는다.
결국 마지막에 남는 우선순위 큐에는 (2,4) (3,5)가 남고, 이 큐가 결국 필요한 강의실의 개수가 되는 것이다.
우선순위 큐를 사용하지 않으려면 강의를 전체 배정하고, 시작시간을 기준으로 정렬한 뒤 강의를 매번 돌면서 겹치지 않는 수업을 지워줘야 한다. ArrayList의 조회 시간복잡도는 O(1)이지만, 삽입과 삭제의 시간복잡도는 O(N)이기 때문에 조회와 삽입/삭제를 같이 해주어야 해서 N*N의 시간복잡도가 걸리기 때문에 최대 (200,000) * (200,000)의 연산을 하게 된다.
이 또한 삽입, 삭제, 정렬이 자주 일어나는 문제임을 알 수 있다.
마지막으로, '보석 도둑(1202)' 문제를 보자.
보석 도둑 문제의 핵심은 '가방의 무게보다 같거나 작은 최소 무게로 최대한의 가격'을 내야 한다.
무게, 가격이 (1,65), (5,23), (2,99)인 보석과 무게가 각각 (10), (2)인 가방이 있을 때
첫번째와 두 번째 보석을 훔친다면 65+23 = 88의 가격을 낼 수도 있지만,
첫번째와 마지막 보석을 훔친다면 65+99 = 164의 가격을 낼 수 있다.
그래서 가방의 무게를 기준으로 들어갈 수 있는 보석의 list를 나열해서 가격이 최대인 보석을 넣어야 한다.
그런데 각 가방의 무게를 기준으로 들어갈 수 있는 보석을 전부 나열해서 고르고, 보석 리스트에서 제거하려면 어마어마한 시간이 소요되게 된다.
그래서 보석과 가방의 무게를 기준으로 정렬한 뒤, 보석의 리스트를 새로 갱신하지 않고 우선순위 큐에 추가해서 가격이 높은것만 빼주는 것이다.
먼저 보석을 무게순으로 정렬하면 (1,65) , (2,99), (5,23)이 될 것이다.
그 다음 가방의 무게가 2라면 첫번째 보석과 두 번째 보석을 우선순위 큐에 넣고, 그 중 가격이 가장 높은 (2,99)보석을 택한다. 그 다음 무게가 10인 가방이 있으므로 나머지 보석 리스트에서 무게가 10 이하인 보석들을 전부 우선순위 큐에 넣는다. 그러면 (1,65), (5,23)중에서 또 밸류가 높은 보석을 뽑으면 된다.
이 3개의 문제를 봤을 때, 공통점은 '삽입, 삭제, 조회가 빈번하느냐'이다.
그런데 '삽입, 삭제, 조회가 빈번하느냐'에 무조건 우선순위 큐를 쓰냐고 하면 그런건 또 아니다.
에초에 삽입/삭제/조회시간을 줄이기 위해서 알고리즘을 풀기 때문에...
그렇다고 문제 유형을 일일히 외워두고 '이런 유형은 무조건 우선순위 큐를 써야지'라고 생각하면 또 안된다.
상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.
가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.
상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.
예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.
상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)
다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)
출력
첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다.
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[] entry;
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());
entry = new int[N];
for (int i=0; i<N; i++){
entry[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(entry);
long start = 0;
long mid = 0;
long end = 1000000000000000001l;
while (start <= end){
mid = (start + end) / 2;
long count = 0;
for (int i=0; i<N; i++){
count += mid/entry[i];
if (count > M) break;
}
//받을수 있는 사람이 승객보다 적다면 총 시간 늘려줘야함
if (count >= M){
end = mid - 1;
} else {
start = mid + 1;
}
}
end = Math.min(end, mid);
//최소 시간 출력
System.out.println(end+1);
}
}
위의 문제처럼 가끔은 하한과 상한 문제 두 가지 전부를 이용해서 풀어야 하는 문제도 존재한다.
각각을 위의 배열을 이용해 슈도 코드로 이용해서 나타내보자.
Arr = | 1 | 2 | 3 | 3 | 4 | 5 | 7 | 8 | 9 |
index = 0 1 2 3 4 5 6 7 8
하한을 이용해 3 이상의 값이 처음으로 나타나는 구간
int start = 0;
int end = 8;
int target = 3;
while (start < end) {
int mid = (start + end) / 2;
if (target <= arr[mid]){
end = mid;
} else {
start = mid + 1;
}
}
return start;
상한을 이용해 3을 초과하는 값이 처음으로 나타나는 구간
int start = 0;
int end = 8;
int target = 3;
while (start < end) {
int mid = (start + end) / 2;
if (target < arr[mid]){
end = mid;
} else {
start = mid + 1;
}
}
return start;
물론, while 뒤에 start <= end를 함으로써 end를 mid - 1해줄 수도 있고, if 안의 조건을 바꿀수도 있다.
문제의 조건을 보고, '이분 탐색'이다 싶으면 이를 변경해주면 된다.
다시 문제로 돌아와서, 이 문제는 '최소한의 시간'으로 '주어진 만큼의 승객'을 받으면 된다.
따라서, count를 만족하는 최소한의 시간이므로 6명의 탑승객이 탑승해야 한다면
- 5명을 초과하는 최소의 시간(상한)
- 6명 이상인 최소의 시간(하한)
중 하나를 이용해 풀이하면 된다.
while (start <= end){
mid = (start + end) / 2;
long count = 0;
for (int i=0; i<N; i++){
count += mid/entry[i];
if (count > M) break;
}
//받을수 있는 사람이 승객보다 적다면 총 시간 늘려줘야함
if (count >= M){
end = mid - 1;
} else {
start = mid + 1;
}
}
end = Math.min(end, mid);
//최소 시간 출력
System.out.println(end+1);
처음에 시간을 최대한으로 많이 잡아놓고,
각각의 카운터를 배열로 설정한다.
카운터 1번이 입국심사를 받는 데 7분이 걸리고, 카운터 2번이 입국심사를 받는데 10분이 걸린다면
28분이 주어질 경우 1번 카운터는 4명, 2번 카운터는 2명을 받을 수 있게 된다.
시간 절약을 위해 count > M을 하면 자동으로 반복문을 빠져나가 다시 이분탐색을 할 수 있게끔 하였다.
국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.
모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.
예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.
여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.
입력
첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.
출력
첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[] budget;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
budget = new int[N];
int max = Integer.MIN_VALUE;
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i=0; i<N; i++){
budget[i] = Integer.parseInt(st.nextToken());
if (budget[i] > max){
max = budget[i];
}
}
int budgetMax = Integer.parseInt(br.readLine());
int start = 0;
int end = max;
while (start <= end){
int mid = (start + end) / 2;
int sum = 0;
for (int i=0; i<N; i++){
sum += Math.min(budget[i], mid);
}
if (sum <= budgetMax){
start = mid + 1;
} else {
end = mid - 1;
}
}
System.out.println(end);
}
}
해설
가장 전형적인 이분탐색 문제이다.
예산의 상한을 이분탐색으로 찾아서, 각 지자체의 예산이 상한을 넘으면 상한값으로, 넘지 않으면 예산만큼을 sum에 추가해주고, 총 예산을 넘는다면 작은 데이터셋으로, 예산을 넘지 않는다면 큰 데이터셋으로 넘어가면 된다.
for (int i=0; i<N; i++){
budget[i] = Integer.parseInt(st.nextToken());
if (budget[i] > max){
max = budget[i];
}
}
이분탐색 문제지만, 정렬이 딱히 필요하진 않다.
다만 처음에 틀렸던 부분은 예산의 최소, 최대를 다 정해줬는데,
최소 상한은 0원으로 고정해놓고, 최대 상한만 max값을 넘기지 않도록 해주는 것이 중요하다.
최소 상한이 반드시 지자체의 최저예산보다 커야하는 법은 없기 때문이다.
이런 언어적인 부분을 코드로 해석하는것이 중요한데, 아직까지는 조금 부족한 것 같다.
int start = 0;
int end = max;
while (start <= end){
int mid = (start + end) / 2;
int sum = 0;
for (int i=0; i<N; i++){
sum += Math.min(budget[i], mid);
}
if (sum <= budgetMax){
start = mid + 1;
} else {
end = mid - 1;
}
}
System.out.println(end);
마지막으로 핵심적인 이분탐색을 시작하는 부분이다.
우리가 구해야 할 것이 Lower bound인지, Upper bound인지, 정확한 값인지를 아는 것이 매우 중요하다.
문제에서는 우리가 구해야 할 것을 다음과 같이 지정했다.
'정해진 총액 이하에서가능한 한 최대의'
이 말은 결국 Upper bound를 구해야 하므로, 예산의 합이 총 합보다 작거나 같을때(sum <= budgetMax)는 계속 더 낮은 값을 찾기 위해 탐색해주어야 하고, 마지막에 예산의 최댓값인 end를 출력해주어야 한다.
우리가 가장 관심있어하는 정보는 테이블 안에 있고, 이 테이블 안의 여러 데이터를 제어하는 것이 우리가 가장 하고 싶어하는 일이다. 이 테이블을 묶어서 그룹핑하고, 이름을 붙인 것이 스키마이고, 이 스키마를 관리하기 위한 것이 데이터베이스이다. 여러개의 데이터베이스를 묶은 것을 클러스터라고도 하고 DBMS라고도 하는데, 이 DBMS를 데이터베이스라고 부르기도 한다.
MySQL에서 데이터를 조회할 때 사용하는 기본 SQL 명령어를 설명해주세요
SELECT
SELECT절은 여러 조건들을 처리한 후 남은 데이터에서 어떤 ROW를 출력할 지 선택하는 역할을 한다.
WHERE
WHERE절은 FROM절에서 읽어온 테이블에서 조건에 맞는 결과만 갖도록 데이터를 필터링한다.
FROM
조회하려는 전체 테이블의 정보를 가져온다.
HAVING
HAVING절은 그룹핑 후 각 그룹에 사용되는 조건절로, HAVING절은 각 그룹에 조건을 걸기 때문에 퍼포먼스가 떨어지는 단점이 있다. 그래서 WHERE에 조건을 쓸 수 있다면 WHERE에 조건을 쓰는게 좋다.
JOIN
JOIN절은 2개나 그 이상의 테이블을 연결하고, 연결한 테이블로부터 필요한 열을 조회할 수 있도록 한다.
ORDER BY
ORDER BY절은 출력할 ROW를 어떤 순서에 맞게 보여줄 지 결정한다.
SQL 명령문의 실행 순서는?
먼저 FROM절에서 조회하려는 전체 테이블의 정보를 가져온다. JOIN이 있다면 다른 테이블과 조인하여 필요한 정보를 가져온다.
WHERE절로 FROM절에서 조회한 테이블에서 필요한 데이터를 필터링한다.
GROUP BY로 선택한 칼럼으로 그룹핑한다.
HAVING으로 그룹핑한 각 그룹에서 조건을 걸어 다시 필터링한다.
SELECT절로 여러 조건들을 처리한 후의 데이터를 가져온다.
ORDER BY를 이용하여 SELECT문에서 가져온 ROW를 어떤 순서에 맞게 보여줄 지 정한다.
LIMIT로 보여줄 ROW의 개수를 정한다.
'Primary Key'와 'Foreign Key'의 차이와 각각의 역할에 대해 설명해주세요.
PK
Primary Key는 데이터베이스 테이블의 각 레코드를 고유하게 식별하는 역할을 합니다.
한 테이블에는 하나의 PK만 존재할 수 있으며, 이 PK는 해당 테이블의 모든 레코드에 대해 고유해야 합니다.
PK는 NULL이 될 수 없습니다.
PK로 지정된 컬럼은 클러스터링의 기준으로 사용되어, 데이터가 저장되는 방식을 결정합니다.
FK
Foreign Key는 다른 테이블의 PK를 참조하여 두 테이블 간의 관계를 설정하는 역할을 합니다.
FK로 지정된 필드 혹은 필드 셋의 값은 참조하는 PK에 있는 값 중 하나여야 합니다. 이 규칙은 참조 무결성의 제약 조건을 만족시키기 위한 것입니다.
FK는 NULL일 수도 있으며, 참조하는 PK에 없는 값을 가질수도 있습니다.
차이점
PK는 한 테이블 내에서 각각의 ROW / RECORD를 고유하게 식별하기 위해 사용되며, FK는 한 테이블과 다른 테이블의 관계를 구축하기 위해 사용됩니다.
PK는 같은 컬럼 안의 모든 레코드가 UNIQUE해야하는 반면 FK는 같은 컬럼 안의 레코드가 중복될수도 있고, NULL이나 참조하는 PK의 ROW에 해당하지 않는 값을 가질수도 있습니다.
MySQL에서 'JOIN'이란 무엇이며, 'INNER JOIN'과 'LEFT JOIN'의 차이점은 무엇인가요?
JOIN은 두 개 이상의 TABLE에서 ROW를 결합하는 데 사용되는 연산이며, 주로 테이블 간에 관계를 맺고 있을 때 사용됩니다. JOIN의 형태는 여러개지만, 가장 기본적인 형태는 INNER JOIN과 LEFT JOIN입니다.
INNER JOIN
INNER JOIN은 두 테이블 간의 교집합을 반환합니다.
즉, 조인 조건에 일치하는 레코드만 결과로 반환합니다.
예를 들어 A라는 테이블과 B라는 테이블이 있어서 INNER JOIN을 하면, A와 B 모두에 들어있는 데이터만 반환합니다.
LEFT JOIN(LEFT OUTER JOIN)
LEFT JOIN은 첫 번째 테이블의 모든 레코드와 일치하는 두 번째 테이블의 레코드를 반환합니다.
오른쪽(두 번째) 테이블에서 일치하는 값이 없을 경우 NULL을 반환합니다.
정규화(Normalization)란 무엇이며, 왜 중요한가요?
NORMALIZATION은 테이블의 각 레코드의 중복을 최소화하고, 데이터 구조를 효율적으로 만드는 과정입니다. NORMALIZATION을 통해 데이터의 무결성(INTEGRITY)와 일관성(CONSISTENCY)을 유지할 수 있습니다.
정규화의 단계는 1NF, 2NF, 3NF 등이 있지만 너무 많은 정규화를 사용할 경우 성능하락이 동반될 수도 있으므로 성능과 무결성 사이에서 적절한 균형을 찾아야 합니다.
송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.
상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.
편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)
각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).
다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)
송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)
출력
각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다.
풀이
public class Main {
static int N;
static final int distance = 1000;
static Queue<Integer> queue;
static int[][] field;
static boolean[] visited;
static StringTokenizer st;
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());
while (T-- > 0){
queue = new LinkedList<>();
N = Integer.parseInt(br.readLine());
visited = new boolean[N+2];
field = new int[N+2][2];
//초기 설정
for (int i=0; i<N+2; i++){
st = new StringTokenizer(br.readLine());
field[i][0] = Integer.parseInt(st.nextToken());
field[i][1] = Integer.parseInt(st.nextToken());
if (getDistance(field[i][0], field[i][1], field[0][0], field[0][1]) <= distance){
queue.offer(i);
visited[i] = true;
}
}
BFS();
if (visited[N+1]) {
sb.append("happy").append("\n");
} else {
sb.append("sad").append("\n");
}
}
System.out.println(sb.toString());
}
static int getDistance(int x1, int y1, int x2, int y2){
return Math.abs(x2-x1) + Math.abs(y2-y1);
}
static void BFS(){
while (!queue.isEmpty()){
int now = queue.poll();
for (int i=1; i<N+2; i++){
if (!visited[i] && getDistance(field[i][0], field[i][1], field[now][0], field[now][1]) <=distance){
queue.offer(i);
visited[i] = true;
}
}
}
}
}
해설
기존 BFS문제를 풀 때 늘 좌표에 Queue를 이용해서 풀다보니 이 문제도 자연스레 그렇게 문제를 들어가다가
OOME에 막혀서 다른 풀이를 찾아보다가 그래프를 이용한 풀이를 보고 깜짝 놀란 문제였다.
물론 배열로 풀어도 상관없다.
다른 블로그에서 list를 이용한 풀이를 많이 설명했으므로, 배열을 이용한 풀이로 설명한다.
리스트를 이용한 풀이든, 배열을 이용한 풀이든 핵심은 다음과 같다.
맥주를 마시기 전에 집에서 갈 수 있는 편의점은 큐에 넣는다.
편의점을 저장할 수 있는 배열을 만든다.
상세한 코드 설명은 다음과 같다.
먼저 메인 함수를 보자.
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());
while (T-- > 0){
queue = new LinkedList<>();
N = Integer.parseInt(br.readLine());
visited = new boolean[N+2];
field = new int[N+2][2];
//초기 설정
for (int i=0; i<N+2; i++){
st = new StringTokenizer(br.readLine());
field[i][0] = Integer.parseInt(st.nextToken());
field[i][1] = Integer.parseInt(st.nextToken());
if (getDistance(field[i][0], field[i][1], field[0][0], field[0][1]) <= distance){
queue.offer(i);
visited[i] = true;
}
}
BFS();
if (visited[N+1]) {
sb.append("happy").append("\n");
} else {
sb.append("sad").append("\n");
}
}
System.out.println(sb.toString());
}
테스트 케이스 T를 받아서 T가 줄어들때까지 케이스를 돌린다.
가장 중요한건 [N+2][2]의 정수형 이차 배열 구조를 가진 field와, [N+2]의 불린형 일차원 배열인 visited를 선언해주는 것이다.
물론 x,y좌표를 담는 point class와 ArrayList<Point>를 만들어서 나중에 get으로 뽑아도 상관없다.
그리고 시작점과 비교해서 맨해튼 거리가 1000 이하인 편의점에 대해 큐에 넣고, visited로 처리해준다.
마지막에 BFS 함수를 돌리고, visited[N+1]로 펜타포트에 갈 수 있는지 / 없는지를 조사하고 append한다.
static int getDistance(int x1, int y1, int x2, int y2){
return Math.abs(x2-x1) + Math.abs(y2-y1);
}
static void BFS(){
while (!queue.isEmpty()){
int now = queue.poll();
for (int i=1; i<N+2; i++){
if (!visited[i] && getDistance(field[i][0], field[i][1], field[now][0], field[now][1]) <=distance){
queue.offer(i);
visited[i] = true;
}
}
}
}
getDistance는 맨해튼 거리를 구하는 함수, 그리고 BFS는 단순하게 큐에 있는 편의점을 뽑아서 다음 편의점과 거리가 1000 미만이면 새로 큐에다가 추가해주면 된다.
2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.
출력
P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.
풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int x3 = Integer.parseInt(st.nextToken());
int y3 = Integer.parseInt(st.nextToken());
System.out.println(ccw(x1, y1, x2, y2, x3, y3));
}
static int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
int temp = x1*y2+x2*y3+x3*y1 - y1*x2-y2*x3-y3*x1;
if (temp > 0) {
return 1;
} else if (temp < 0) {
return -1;
} else {
return 0;
}
}
}
해설
CCW = Counter,Counter-ClockWise의 줄임말로, 시계방향과 시계 반대방향을 찾아내는 문제이다.
한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.
예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.
첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.
출력
첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int n = Integer.parseInt(br.readLine());
int[] A = new int[n];
st = new StringTokenizer(br.readLine());
for (int i=0; i<n; i++){
A[i] = Integer.parseInt(st.nextToken());
}
int m = Integer.parseInt(br.readLine());
int[] B = new int[m];
st = new StringTokenizer(br.readLine());
for (int i=0; i<m; i++){
B[i] = Integer.parseInt(st.nextToken());
}
Map<Long, Long> mapA = new HashMap<>();
Map<Long, Long> mapB = new HashMap<>();
for (int i=0; i<n; i++){
long sum = 0;
for (int j=i; j<n; j++){
sum += A[j];
long count = mapA.getOrDefault(sum, 0L);
mapA.put(sum, count+1);
}
}
for (int i=0; i<m; i++){
long sum = 0;
for (int j=i; j<m; j++){
sum += B[j];
long count = mapB.getOrDefault(sum, 0L);
mapB.put(sum, count+1);
}
}
long answer = 0;
for (Map.Entry<Long, Long> entryA :mapA.entrySet()){
Long aSum = entryA.getKey();
Long aCount = entryA.getValue();
long diff = T - aSum;
Long bCount = mapB.getOrDefault(diff, 0L);
answer += (aCount * bCount);
}
System.out.println(answer);
}
}
해설
누적합 + 부배열을 다룰 수 있는지를 물어보는 문제였다.
슬라이딩 윈도우로도 풀 수 있는 문제지만, 어짜피 개수 * 개수를 리턴해야 하는 문제라고 생각해서
Map에 누적합이 몇개 있는지 count를 넣어주었다.
예를 들어 A = {1,3,1,2}, B = {1,3,2}라면
mapA에는 7가지 경우의 수(1,2,3,4,5,6,7)
mapB에는 6가지 경우의 수(1,2,3,4,5,6)가 들어갈 것이다.
그중에서 연속되어 있는 수열을 찾기 위해 중첩포문을 두번 돌려줄 것이다.
그리고 map의 entryset을 뒤져서
mapA = 1이라면, mapB = T-mapA = 4가 되어야 하므로
mapB의 4에 해당하는 entryset을 찾아서
mapA의 count (값이 1이 되는 부분수열의 개수) * mapB의 count(값이 2가 되는 부분수열의 개수)를 해주고 print한다.
물론 sliding window나 이분 탐색으로 풀 수도 있다.
그러나 규칙 / 분류에 의거해서 기계적으로 문제를 푸는 일을 굉장히 지양하려고 해서 어떻게 할까 생각하다 보니
