본문 바로가기

Algorithm/BOJ172

[BOJ]1940번: 주몽 https://www.acmicpc.net/problem/1940 N 제한이 15,000 이므로 단순 O(N^2) 탐색을 하면 시간초과가 납니다. N개의 숫자를 오름차순 정렬을 한 뒤 앞에서 부터 하나씩 숫자를 탐색하면서 특정 숫자가 조합할 수 있는 대상이 되는 숫자를 선형 탐색이 아닌 이분 탐색을 하면 됩니다. 그러면 시간복잡도는 O(NlogN)으로 통과할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1940.cc 2020. 9. 1.
[BOJ]9328번: 열쇠 https://www.acmicpc.net/problem/9328 jaimemin님 풀이를 참고하여 해결하였습니다. (https://jaimemin.tistory.com/692) 문제 풀이에 필요한 아이디어는 아래와 같습니다. 1. 모든 칸에서 입장이 가능하다는 조건을 위해 주어진 그래프 테두리에 빈 칸을 추가해서 모든 칸 방문하게 하기 2. 열쇠를 새로 얻으면 그 지점부터 bfs를 다시 시작합니다. 3. 열쇠나 문서를 얻었으면 재방문을 막기 위해 빈 칸으로 바꿔버립니다. 위와 같은 기법을 통해 bfs를 돌리면 문제를 해결할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ9328.cc 2020. 9. 1.
[BOJ]1102번: 발전소 https://www.acmicpc.net/problem/1102 bitmasking + dp 문제입니다. sungwoo님의 블로그 내용을 참고하여 해결하였습니다. (https://sungwoo91.tistory.com/12) dp테이블은 다음과 같습니다. dp[N][state]: N: 현재 N개의 발전소가 켜져있고, state: N개 중에 어떤 발전소가 켜져있는 상태를 나타냅니다. 그리고 dp table에 위와 같은 상태를 만드는데 드는 최소 비용만을 저장해놓습니다. dp[N][state] = minCost 그래서 P개를 모두 켰을 때 최소의 비용을 구하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1102.cc 2020. 8. 28.
[BOJ]13308번: 주유소 https://www.acmicpc.net/problem/13308 jason님 풀이를 바탕으로 해결하였습니다. (https://jason9319.tistory.com/249) 거리와 비용 최소화라는 2가지 정보로 판단해야 합니다. 그렇기 때문에 단순히 dist[N] 1차원 배열로는 모든 정보를 담을 수 없습니다. 그래서 dist[N]과 같은 역할을 하는 2차원 dp테이블을 사용합니다. dp[node][minOilCost] 정의 : 1번 노드부터 순회하여 node까지 왔고, 지금까지 방문한 주유소의 기름 가격 중 최소 기름 가격 그리고 이 dp table에 node를 방문하며 쌓인 totalCost 값을 집어넣는 것입니다. dp[node][minOilCost] = totalCost 이런식으로 다익스트라를.. 2020. 8. 28.

티스토리툴바