Algorithm/BOJ172 [BOJ]5719번: 거의 최단 경로 문제: https://www.acmicpc.net/problem/5719 jaimemin님 블로그의 솔루션을 참고해서 해결했습니다. (https://jaimemin.tistory.com/617) 다익스트라를 진행하게 되면 src => dst 방향으로 최종 노드까지 최소 간선비용으로 갱신이 됩니다. 이 점을 이용해서 다익스트라 진행 중, 최소 간선 비용이거나, 최소 간선 비용과 비용이 같은 경우 before라는 벡터를 선언해 저장해줍니다. //before[NODE]: 최소 간선 비용으로 정점 NODE로 들어오는 정점들을 저장한 벡터 //ex. before[NODE] = {1,2,3,4} 이면 // 1번 정점 => NODE, 2번 정점 => NODE, 3번 정점 => NODE, 4번 정점 => NODE ve.. 2020. 7. 28. [BOJ]2096번: 내려가기 문제: https://www.acmicpc.net/problem/2096 슬라이딩 윈도우 문제입니다. 메모리 제한이 심상치 않습니다. 발판은 board[N][3]의 형태를 가지고 있지만, i번째 칸을 계산함에 있어서 필요한 발판정보는 i-1번째 칸의 정보만 필요합니다. 그러므로 메모이제이션을 위한 dp[][] 배열이나 input값을 저장하는 board[][] 배열 모두 [2][3] 크기면 됩니다. dp배열을 다음과 같이 정의내리겠습니다. max_dp[N][M]: 맨 윗칸에서부터 board[N][M] 칸까지 내려왔을 때 얻을 수 있는 최댓값 min_dp[N][M]: 맨 윗칸에서부터 board[N][M] 칸까지 내려왔을 때 얻을 수 있는 최솟값 끝으로 dp[i][], dp[i+1][] 이렇게 두 칸만 사용하.. 2020. 7. 22. [BOJ]17135번: 캐슬 디펜스 문제: https://www.acmicpc.net/problem/17135 시뮬레이션 문제입니다. 아래와 같은 조건들을 문제 요구사항대로 구현해야 합니다. 1. 궁수 배치 2. 궁수가 쏠 타겟 정하기 3. 적들 한 칸씩 내리기 궁수가 쏠 타겟을 정하는 건 우선순위 큐를 사용해서 tuple(거리, X좌표(가로), Y좌표(세로))로 담은 다음 PQ.top()값을 사용하는 것으로 해결하였습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ17135.cc 2020. 7. 22. [BOJ]1916번: 최소비용 구하기 문제: https://www.acmicpc.net/problem/1916 기본 다익스트라 문제입니다. 도시의 개수가 1000개이므로 인접행렬을 사용하든, 인접리스트를 사용하든 상관없습니다. O(ElogV)에 해결할 수 있도록 우선순위큐를 사용해서 문제를 해결하였습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1916.java 2020. 7. 20. 이전 1 ··· 29 30 31 32 33 34 35 ··· 43 다음
