241104 회고 💬
11월이 시작됐다. 낮에 20도까지 올라가는 11월이다. 봄날씨가 느껴지는 11월의 첫 주를 되돌아본다.
Keep 👍
- 알고리즘 문제풀이를 7일 연속으로 해냈다. 241104기준으로 387일, 800문제 해결 중이다. 이번 주에는 MST, 플로이드 알고리즘을 공부했다.
- 도시 분할 계획 간단한 MST 문제다. 프림 알고리즘보다는 크루스칼을 선호해서 MST문제는 거진 모두 크루스칼을 사용해 풀이한다. 인풋 처리만 잘 해결하면 나머지 로직은 전형적인 문제풀이 방법으로 접근하면 된다.
- Line Friends (Small) 플로이드 알고리즘 문제다. 선분이 겹치는지 판단하는 로직만 생각해낼 수 있으면 해당 문제도 전형적인 풀이방식으로 접근해서 해결 가능하다. 선분 겹치는 로직 생각하기가 시간이 많이 걸렸다. - 토이 프로젝트를 제작하고 있다. 이번 주에는 프론트 작업을 많이 했다.
- 동영상 녹화 로직 제작
- 동영상 섬네일 만드는 로직 제작
- Webpack & SCSS
Try 🧚
- 객체지향의 사실과 오해 마무리하기
- 알고리즘 문제 풀이
- 프론트 서버 구축
- node 개념 학습
- cors 해결하기 - 백엔드 서버 개발
- 인증, 인가
- mvp 제작
독서 목록
서평 완료 목록
서평 예정 목록 (읽는 중)
- 함께 자라기 애자일로 가는 길
- 객체지향의 사실과 오해
독서 예정 목록
목록은 우선순위 큐이다. 상단에 있더라도 더 중요한 책이 들어온다면 순위가 뒤로 밀릴 수 있다.
- 오브젝트
- 파이브 라인스 오브 코드
- HTTP 완벽 가이드
- 자바/스프링 개발자를 위한 실용주의 프로그래밍
- 모던 자바 인 액션
- 자바 성능 튜닝 이야기
- 자바 개발자와 시스템 운영자를 위한 트러블 슈팅 이야기 / scouter를 활용한 시스템 장애 진단 및 해결 노하우 자바 트러블슈팅
- 헤드 퍼스트 서블릿
- Hello Coding 그림으로 개념을 이해하는 알고리즘
Extras 😀
도시 분할 계획
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) {
new Main().run();
}
private void run() {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
Input ip = readInput(br);
Solution s = new Solution();
System.out.println(s.solution(ip.numOfHouses, ip.roads));
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private Input readInput(BufferedReader br) throws IOException {
String[] tokens = br.readLine().split(" ");
int numOfHouese = Integer.parseInt(tokens[0]);
int numOfRoads = Integer.parseInt(tokens[1]);
int[][] roads = new int[numOfRoads][3];
for (int i = 0; i < numOfRoads; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
roads[i][0] = from;
roads[i][1] = to;
roads[i][2] = cost;
}
return new Input(numOfHouese, roads);
}
private static class Input {
private final int numOfHouses;
private final int[][] roads;
public Input(int numOfHouses, int[][] roads) {
this.numOfHouses = numOfHouses;
this.roads = roads;
}
}
}
class Solution {
public int solution(int numOfHouses, int[][] roads) {
int[] group = IntStream.range(0, numOfHouses + 1).toArray();
Arrays.sort(roads, Comparator.comparing(a -> a[2]));
int max = 0;
int answer = 0;
for (int[] road : roads) {
int from = road[0];
int to = road[1];
if(isGroup(group, from, to)) continue;
connect(group, from, to);
int cost = road[2];
answer += cost;
if(max < cost) max = cost;
}
return answer - max;
}
private boolean isGroup(int[] group, int target1, int target2) {
return getGroup(group, target1) == getGroup(group, target2);
}
private int getGroup(int[] group, int target) {
if(target != group[target]) group[target] = getGroup(group, group[target]);
return group[target];
}
private void connect(int[] group, int target1, int target2) {
int g1 = getGroup(group, target1);
int g2 = getGroup(group, target2);
if (g1 != g2) {
group[Math.max(g1, g2)] = Math.min(g1, g2);
}
}
}Line Friends (Small)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
new Main().run();
}
private void run() {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
Solution s = new Solution();
System.out.println(s.solution(readInput(br), readQuestions(br)));
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private int[][] readInput(BufferedReader br) throws IOException {
int len = Integer.parseInt(br.readLine());
int[][] result = new int[len + 1][2];
for (int i = 1; i < len + 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
result[i][0] = start;
result[i][1] = end;
}
return result;
}
private int[][] readQuestions(BufferedReader br) throws IOException {
int len = Integer.parseInt(br.readLine());
int[][] result = new int[len][2];
for (int i = 0; i < len; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
result[i][0] = start;
result[i][1] = end;
}
return result;
}
}
class Solution {
public String solution(int[][] people, int[][] questions) {
int len = people.length;
int[][] relations = getRelations(people);
for (int k = 1; k < len; k++) {
for (int i = 1; i < len; i++) {
for (int j = 1; j < len; j++) {
if (relations[i][j] > relations[i][k] + relations[k][j]) {
relations[i][j] = relations[i][k] + relations[k][j];
}
}
}
}
StringBuilder answer = new StringBuilder();
for (int[] question : questions) {
int from = question[0];
int to = question[1];
if(relations[from][to] == 0 || relations[from][to] == 999_999_999) answer.append(-1);
else answer.append(relations[from][to]);
answer.append("\n");
}
return answer.toString();
}
private int[][] getRelations(int[][] people) {
int len = people.length;
int[][] relations = new int[len][len];
for (int i = 1; i < len; i++) {
for (int j = 1; j < len; j++) {
if(i == j) continue;
if(isConnected(people[i], people[j])) relations[i][j] = 1;
}
}
for (int i = 1; i < len; i++) {
for (int j = 1; j < len; j++) {
if(i == j) continue;
if(relations[i][j] == 0) relations[i][j] = 999_999_999;
}
}
return relations;
}
private boolean isConnected(int[] target1, int[] target2) {
return Math.max(target1[0], target2[0]) <= Math.min(target1[1], target2[1]);
}
}
What doesn't kill you, makes you stronger