Algorithm/BOJ172 [BOJ]13549번: 숨바꼭질 3 문제: https://www.acmicpc.net/problem/13549 다익스트라로 해결하였습니다. 특정 좌표 X에서 수빈이가 움직일 수 있는 위치는 세 가지 입니다. 1. X-1 2. X+1 3. 2X 다익스트라로 해결한 이유는 두 배씩 뛰는 좌표의 경우 시간의 영향을 받지 않습니다. 그러므로 그냥 단순히 방문했다고 visited[] 배열을 true / false로만 표시한다면 더 빠른 시간에 특정 좌표 X에 도착해도 이미 visited[] 이 true라면 다시 탐색할 수 없습니다. 그러므로 큐에서 늦게 나온 값이라도 이미 저장되어있는 visited[] 시간보다 빠르면 갱신해줍니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ13549.. 2020. 6. 20. [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]1654번: 랜선 자르기 문제: https://www.acmicpc.net/problem/1654 parametric search 문제입니다. 랜선의 하한: 1 랜선의 상한: 2^31 - 1 랜선의 상한 ~ 하한에 대한 임의의 길이 값을 기준으로 "N개의 랜선을만들 수 있다면 TRUE, 만들 수 없다면 FALSE" 입니다. 임의로 정한 랜선의 길이가 길어질 수록 만들 수 있는 랜선의 갯수는 작아지고, 랜선의 길이가 짧아질수록 만들 수 있는 랜선의 개수는 늘어납니다. 이런 구간의 연속성이 성립하기 때문에 랜선의 하한 ~ 상한의 범위를 선형 탐색이 아닌 이분 탐색으로 훑을 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1654.cc 2020. 6. 9. [BOJ]9466번: 텀 프로젝트 문제: https://www.acmicpc.net/problem/9466 싸이클 찾기 문제입니다. 위상 정렬을 통해 해결할 수 있습니다. 싸이클의 대상이 아닌 노드의 특징은 자신에게 들어오는 간선이 하나도 없다는 점입니다. 그러므로 처음에 데이터를 입력받을 때 finished[] 배열을 통해서 자신에게 들어오는 간선을 카운트 해줍니다. 1. finished[Node] == 0인 애들을 제외 (싸이클이 아님) 2. 1번에서 제외된 노드들과 연결되어있던 Node들의 finisehd[] 값을 1 감소시켜줍니다. (싸이클이 아닌 후보들로부터 들어온 간선은 싸이클에 아무런 영향을 끼치지 못하므로) 3. 2번 과정을 통해 finished[] == 0인 애들이 있다면 이 노드들도 제외해줍니다. 4. finished[.. 2020. 6. 9. 이전 1 ··· 33 34 35 36 37 38 39 ··· 43 다음
