🧐오늘 한 일
- 프로그래머스(Lv3) 카카오블라인드2021 합승 택시 (다익스트라 또는 플로이드 와샬)
- 백준(실버 2) 1931번 회의실 배정 (Greedy, Sort)
- 백준(골드 4) 2234번 성곽 (BitMask, BFS, HashMap)
😁 알게 된 점
프로그래머스(Lv3) 카카오블라인드2021 합승택시는 플로이드 와샬과 다익스트라중 하나를 골라서 사용할 수 있다. (
물론 다른 최단 거리 알고리즘도 가능)
플로이드 와샬은 모든 정점에서 최단 거리를 dp를 이용해 저장 하는 방법으로 시간 복잡도가 O(n^3)이 된다.
다익스트라는 특정 지점에서 부터 최단 거리를 구하는 것으로 그리디 알고리즘을 이용하는 것이다.
⇒인자의 개수가 몇개 안되기 때문에 플로이드 와샬도 충분히 가능하다고 생각해서 플로이드 와샬로 풀었다. (효율성 체크하게 되면 다익스트라가 훨씬 빠르다 ⇒ 공부하기!) 둘의 풀이 과정은 굉장히 비슷한 데 다른부분의 코드는 아래의 코드이다.
// 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다.
// 1이상 n이하
for(int i = 1; i < n+1; i++) {
for(int j = 1; j < n+1; j++) {
for(int k = 1; k < n+1; k++) {
dp[j][k] = Math.min(dp[j][k], dp[j][i] + dp[i][k]);
}
}
}<전체 코드>kangum99/AlGORITHM
백준(실버 2) 1931번 회의실 배정 (Greedy, Sort)는 가장 대표적인 그리디 문제이다. 특정 시간 이 끝나고 다른 동작을 시작했을 때 가장 많은 수의 작업을 할수 있는 경우!
⇒ 대표적인 풀이 방법 : 종료시간을 오름차순으로 정렬(만약 같다면 시작시간을 오름 차순으로)→ 그 후 반복문을 돌면서 시작시간이 이전 것의 종료시간보다 같거나 크면 cnt++을 해준다.
⇒ time 클래스를 만들어서 사용했는 데 time클래스를 저 기준으로 오름 차순을 할 때 어려웠다.. compareTo(Comparable<>)-(나와 이전변수 비교)와 compare(Comparator<>)-(변수 두개 비교) 잘 찾아보자!
<전체 코드>kangum99/AlGORITHM
백준(골드 4) 2234번 성곽 (BitMask, BFS, HashMap)
1. 방의 개수와 최대 넓이를 BFS로 먼저 구한다. (BitMask를 이용해 그 방의 어느 방향에 벽이 있는 지 확인하기)
2. 방의 개수를 구할 때 마다 HashMap에 {roomNum : size}이런식으로 저장을 한다. 또한 주어지는 arr[][] 그 방에 해당하는 값들을 전부 roomNum으로 바꿔준다 → 하나의 방에 해당하는 값들은 전부 같은 숫자로 초기화됨.
3. 그 후 벽을 뚫은 경우를 구할 때는 또 BFS를 하지 X ⇒ 모든 방들을 돌면서 현재 방과 이동할 방의 값이 다르면(roomNum이 다르면) 벽이 있다는 의미 이므로 그 벽을 뚫었을 때 방의 넓이는 (현재방 넓이+이동할 방의 넓이)이므로 HashMap에 저장해둔 넓이들을 이용해 값을 구하면된다.
4. 그 후 그 넓이를 max와 비교해서 최댓값을 구한다.
<전체 코드>kangum99/AlGORITHM
😎 다짐
- 이제 최단 거리 알고리즘 같은 어려운 알고리즘을 제대로 공부해보자
- 라이브러리나 정해진 메서드를 가져와 사용할 때는 그것으로 인해 나오는 실행값만 아는 것이 아니고 어떻게 그 값이 나오는지 먼저 알아보자
