BOJ (2) 썸네일형 리스트형 [백준 | BOJ] 10986번: 나머지 합 (Python) 문제https://www.acmicpc.net/problem/10986 난이도 알고리즘 분류더보기수학누적합 요약수학적 지식이 필요한 문제난이도에 비해 코드는 쉽게 짤 수 있음(=풀이 과정 자체는 별거 없음)하지만 아이디어를 떠올리는 것이 어려웠던 문제문제 접근 방식어떤 알고리즘을 사용해야 하는지 살펴보기 위해 문제의 조건들을 살펴보자. 3번에 대한 내용은 쉽게 떠올리기 힘들어서 체감 난이도가 높은 것 같다.연속된 부분 구간의 합을 구해야 한다.누적 합 알고리즘을 사용해서 구할 수 있다. 시간 복잡도는 대략 O(N)N의 범위가 최대 1,000,000 이다.허용 가능한 최대 시간 복잡도는 대략 O(N log N) 임을 알 수 있음누적 합 알고리즘은 O(N) 이므로 사용 가능!구간 합이 M으로 나누어 떨어지는.. [백준 | BOJ] 2098번: 외판원 순회 (Python) 문제https://www.acmicpc.net/problem/2098 난이도 알고리즘 분류더보기DFS/BFSDP비트마스킹 요약BFS를 사용하면 다익스트라(Dijkstra) 알고리즘과 매우 흡사한 방식으로 풀 수 있다.BFS보다 DFS가 메모리, 속도 측면에서 결과가 더 좋았다. (BFS 방식 코드를 잘못 짰을수도...)문제 접근 방식우선 어떤 알고리즘을 사용해야 하는지 확인하기 위해 문제의 조건들을 살펴보자.외판원의 순회 여행 경로를 구해야 한다.출발지에서 시작해서 다시 출발지로 돌아와야 한다는 뜻이죠. 즉, 순환경로(Cycle)라는 의미입니다.모든 노드를 방문해야 하므로 DFS/BFS를 사용해야 하는 것을 알 수 있습니다.가장 적은 비용으로 순회해야 한다."가장 적은 비용" 어디서 많이 보던 단어죠?.. 이전 1 다음
