본문 바로가기

분류 전체보기361

[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.
[코딩테스트 연습] 가장 긴 팰린드롬 https://programmers.co.kr/learn/courses/30/lessons/12904 hyozkim님의 풀이를 보고 해결하였습니다. (https://velog.io/@sa833591/%EA%B0%80%EC%9E%A5-%EA%B8%B4-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv.3) 팰린드롬을 위한 dp 점화식은 간단합니다. D[i][j] == 1 : i번째 문자부터 ~ j번째 문자가 팰린드롬이면 1 D[i][j] == 0 : i번째 문자부터 ~ j번째 문자가 팰린드롬이 아니면 0 기저 사례는 아래와 같습니다. DP[i][i] = 1 DP[i][i+1] = (str.. 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.

티스토리툴바