6주차 스터디 #23
Description
1번 문제 - 세연 (양궁 대회)
- 백트래킹으로 풀이 -> 문제가 조건에 맞춰 그대로 구현
- 각 기능별로 함수로 구현해내어 풀이
- 대체로 시간 복잡도가 넉넉하다.
Q1. static 아닌 main 함수인데 왜 입력받는 매개변수를 다시 static 변수로 만들어 사용하셨나요 ?
A1. 전역변수로 사용하려고 썼습니다. 습관적으로 썼습니다.
Q2. 프로그래머스는 시간 복잡도가 넉넉한가?
A2. 원하는 풀이 방향이 있다면, 완탐이나 부적절한 풀이를 할 경우 시간 복잡도가 터지게 만들어놨을 확률이 높다.
main이 static이 아니기 때문에, static 변수로 만들지 않아도 어느 함수에서든 매개변수를 사용할 수 있다.
카카오 문제 풀이를 해설해주는 사이트: https://tech.kakao.com/posts/488
2번 문제 - 주혜 (택배 배달과 수거하기)
- 끝에서부터 다녀오면 문제를 풀이할 수 있을 것 같아서 그렇게 풀었다.
- while문을 활용한 핵심 로직 구현
- 배달해야하거나, 수거해야할 마지막 집을 구하는 풀이
long trips = Math.max((deliverPending + cap - 1) / cap, (pickupPending + cap - 1) / cap);- 위 코드에 대한 의문 / 빨라지는데 왜 빨라지는지, 어떤 의미인지 이해를 못했다.
- 끝집 갔는데, 덜 배달해서 남는 경우를 대비하기 위한... (서기는 이해를 하지 못했다. -> 이해한 정연이에게 질문을 하기 바람)
3번 문제 - 은성 (도넛과 막대 그래프)
- 처음에 그래프 탐색(인접 리스트 구현)을 하려고 했다.
- 각 그래프의 특성을 파악해서 구현 -> 나가는 정점과 들어오는 정점을 기준으로 케이스를 분류
Q1. 숫자에 언더바를 해도 되나요? (ex. 100_000_000)
A1. 네! 됩니다.
Q2. 그럼 다르게 어떻게 풀이할까요?
A2. DFS, BFS로 풀 수 있을 것 같은데, 검증을 안해봤습니다.
알게 된 사실: 숫자를 구분하기 위해서 언더바를 활용해보자.
4번 문제 - 예림 (코딩 테스트 공부)
- DP와 다익스트라 풀이가 있다. 다익스트라로 풀이하려다가 도저히 안 풀려서 DP로 풀이했습니다.
- dp[i][j]: 알고력 i, 코딩력 j 도달할 때, 최단 시간
- Runtime 에러가 많이 났었다. 그 이유는 목표보다 초기값이 더 클 수가 있었기 때문이다.
- 적당히 큰 값을 정해야 하는데, 그걸 모르겠어서 Integer.MAX_VALUE 를 사용했고, 이 값과 일치하면 continue 하는 방식을 채택했다.
5번 문제 - 정연 (등산코스 정하기)
- 어떻게 하면 덜 힘들게 봉우리를 찍고 올 수 있을까? 에 대한 고민을 했다.
- 간선들의 가중치가 다양해서 다익스트라 알고리즘을 사용하면 좋겠다는 생각을 했다.
- 그 경로에서 가장 힘들었던 때가 언제인지를 저장하면서 알고리즘을 전개하는 것이 이 문제의 핵심이었다.
- .contains() O(1) 메서드를 사용하기 위해서 HashSet<> 자료구조를 선택했다.
- 2중 for문을 돌면서 완탐을 진행했었지만, 시간 초과가 발생했다. 시간 복잡도를 줄이기 위해서 출발점을 Queue를 모두 담아 시작했다.
- 다익스트라 1번을 통해서 모든 봉우리의 문제가 요구하는 값을 도출할 수 있다.
Q1. PriorityQueue 말고, Queue를 쓴 이유가 뭔가요?
A1. 출발점이 1개인 경우 뿐 아니라, 출발점이 여러 개인 경우에도 최적해가 보장이 된다. / 같은 거리면 더 적은 숫자의 봉우리를 선택하는 것이기 때문에 노드 숫자까지 우선순위 큐에 넣어서 최적해를 구하면 된다.
다익스트라 알고리즘은 출발점이 1개인 경우 뿐 아니라, 출발점이 여러 개인 경우에도 최적해가 보장이 된다.
용모 왈: 안전 지대 문제와 같이 가중치를 1씩 높여가며 BFS를 돌면서 최초로 도착할 수 있는 가중치를 선택하는 풀이도 가능하다.
가중치가 너무 다양하면 파라메트릭 서치(이분 탐색) 풀이도 도전해볼 수 있을 것 같다.