결국 저번주에 커피를 걸고했던 챌린지는 제대로 패배...
게임에 하나 꽂혔더니 주말동안 70렙까지 키웠고, 현실에선 으음
월요일도 대체공휴일임을 몰랐다가 늦은 줄 알고 20분정도 빠른걸음으로 갔는데, 가는 길에 학생도 없고 학교도 닫아있어서 혹시나 하는 마음으로 달력을 열었지.
아니나 다를까 공휴일이네 😇
덕분에 돌아와서 잠을 꽤 깊이자고 밥먹고 조미료때문에 잠드니 하루가 또 끝나있었다
오늘은 그래도 4개 이상은 달성해야지..
비록 병원가는 날이라 조퇴지만 😅
일정 정리부터..
플래너를 쓰지만 달력형식인 페이지는 기록을 안했더니 어떤 일정들이 있었는지 자꾸 까먹는다.
그래서 이번기회에 정리를 했는데...
와 정처기가 이번주야? 생각하고 있는데
PT 날짜가 정처기 응시날짜랑 겹치네 🤣
당장 트레이너님께 연락했음... 다행히 시간 조정에 성공!
그리고 내일 어버이날이니까 거금 좀 써주고...
이제서야 오늘을 보낼 준비가 된 것 같다.
할일 끄적이기
- PS
- CS를 곁들인 정처기 필기 대비
- 이것이 자바다
- 스프링 자바편
이 4개 위주로 달려야지
PS 문제풀기
한달 뒤 시험이라 생각하고 대비하는 느낌으로 해보려 한다.
실제로 PCCP가 6월 16일에 있길래 바로 예약해뒀음
문제 1) 정수 삼각형
보통 문제를 풀 때 유형을 보지않고 풀려는 편인데 문제집에서 Lv3중 정답률 높은 순으로 고르다보니 동적계획법이라는 유형을 보고 말았다...
그래도 dp라면 워낙 솔루션이 정형화 되어있지 않으니 상관없겠다 싶어서 그대로 풀어보려 했는데 문제를 보자마자 이게 왜 dp인건지에 대해 고민에 빠졌음.
위의 값 그대로 받아서 Math.max(값1,값2) 연산으로 전체에 대해 계산하면 불가능한가?? 왜?? 라는 생각만 맴돌았다.
우선 문제를 보고 높이가 500이하, 숫자가 최대 9999인것을 보고 자료형을 long으로 잡아야 할지 계산하기 위해 구해봤는데
500 * 9999 = 4,999,500
이므로 int로도 충분하다고 생각했다.
그러곤 앞서 말했던 왜 dp여야하는 가를 생각했는데,
위의 값을 모두 받아서 계산에 포함시키면 중복이 많은 것처럼 느껴질 수도 있겠다 라는 생각을 해봤다.
시간복잡도를 계산하기 위해 특징을 찾아보면 아래와 같다.
양 끝은 바로 내려오고 중간은 위의 2개 중 큰값을 선택해서 내려온다.
위의 개수가 n개, 아래 개수가 n+1개라 하면,
2 + 2 * (n-2) = 2n-2번의 연산을 하게 된다.
여기서 n은 1부터 최대 N = 500까지 가능하므로
2 * (1+2+3...+N) - 2 * N = N(N+1) - 2N = 500 * 501 - 1000 = 249,500이다.
결국 그대로 완탐해도 풀리는데 이게 왜 DP냐구우...
그래서 에라모르겠다를 외치며 좀더 효율적인 Math.max() 메서드를 이용해서 구현했다.
처음엔 이전값 배열 dp와 함께 현재값을 배열 cur로 받아 dp배열에 누적시키는 방법을 이용했는데, 불필요한 값이 누적되는 듯 했다.
알고보니 이미 합산된 값이 dp에 들어가버리면 다음 값 계산할 때 합산된 값과 비교를 하고 더하게 되니.. 안되던 것.
그래서 dp를 2차원 배열로 잡아서 돌렸고 맞았습니다를 얻었다.
문제 2) 네트워크
음 네트워크가 몇개냐.. 문제는 이젠 Union-Find밖에 떠오르지 않아서, 오늘도 크루스칼 알고리즘으로 유니온 파인드를 구현했다.
UF를 구현할 때는 현재 구해둔 부모들의 모음인 parents 배열을 너무 믿으면 안된다는 것을 간과해선 안된다.
parents에 들어가 있으니 부모임은 확실하지만, 오류가 있을 수 있기 때문.
이해를 돕기위해 예시를 들어보면,
A 노드의 부모는 B,C,D,E 처럼 여러개 일 수 있다. 하지만, 단 하나의 값을 저장해야 한다.
즉, A의 부모는 B이다 라고 했을 때 B,C,D,E를 다 포함할 수 있어야한다.
그래서 union-find의 대표 함수인 union과 find는 아래처럼 구현될 수 있다.
find 함수 정의
public static int find(int node){
if(parents[node] == node)
return node;
return parents[node] = find(parents[node]);
}union 함수 정의
public static void union(int a, int b){
int na = find(a);
int nb = find(b);
if(na <= nb){
parents[na] = nb;
}else{
parents[nb] = na;
}
}이 스니펫을 그대로 가져가는 것보다 이해가 먼저임을, 그리고 나만의 방식대로 구현해보는 것이 중요함을 잊지말자.
CS를 곁들인 정처기 필기 대비
정처기를 이번엔 좀 대비하고자 책을 샀었는데 이번주라니...
다행히 실기책을 샀기 때문에 개념 요약집으로 빠르게 대비는 가능할 듯 하다.
그렇지만 CS 공부 겸 병행 목적으로 보는거니까 허투루 보진 말아야지
우선 핵심요약 부분 전체 1회독 후 양을 가늠해보고 목표를 잡아야겠다.
1회독 중
우선 병원가기 전에 58까지 읽었다.
이것이 자바다;
스프링 자바편;
