백준알고리즘15 [BOJ]12837번: 가계부 (Hard) 문제: https://www.acmicpc.net/problem/12837 쿼리랑 N 제한이 큽니다. O(NQ)에 처리하면 터집니다. 구간합, 갱신 쿼리를 O(logN)에 처리하기 위해 세그먼트 트리로 해결합니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ12837.cc 2020. 6. 17. [BOJ]1018번: 체스판 다시 칠하기 문제: https://www.acmicpc.net/problem/1018 시뮬레이션 문제입니다. N,M 제한이 작으므로 체스판의 시작점이 될 수 있는 모든 점에서 01010101 10101010 ... 체스판과 10101010 01010101 ... 체스판을 비교하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1018.cc 2020. 6. 3. [BOJ]1484번: 다이어트 문제: https://www.acmicpc.net/problem/1484 투 포인터로 해결가능한 문제입니다. G = Y^2 - X^2을 만족하는 모든 Y를 구하는 문제입니다. G는 자연수이므로 X 2020. 5. 26. [BOJ]2211번: 네트워크 복구 문제: https://www.acmicpc.net/problem/2211 다익스트라 문제입니다. 주어진 간선중에 1번 컴퓨터에서 모든 컴퓨터를 연결하되 최소비용 조건을 맞추려면 다익스트라의 최종 경로가 된 간선들만 뽑아내면 됩니다. 제가 해결한 방법은 다익스트라에서dist[] 배열을 pair로 선언하여 first에는 길이 값을 담고, 길이가 더 짧을 만나 갱신될 때 마다 second값에 현재 나와 연결된 NODE 값을 저장해놓습니다. 그렇게 하면 최종적으로 dist[] 배열에 저장된 다익스트라의 (dist[i], dist[i].second) 모든 쌍이 정답입니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2211.cc 2020. 5. 21. 이전 1 2 3 4 다음
