본문 바로가기

Algorithm283

[BOJ]17836번: 공주님을 구해라! https://www.acmicpc.net/problem/17836 BFS 문제입니다. 그램을 얻은 상태, 안 얻은 상태에 탐색할 수 있는 영역이 달라지기 때문에 방문표시에서 구분을 해줘야 합니다. 그래서 방문표시 배열을 visited[2][N][M]으로 선언하고 BFS 탐색을 해주면 해결이 가능합니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ17836.cc 2020. 9. 1.
[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.

티스토리툴바