BOJ75 [BOJ]2473번: 세 용액 문제: https://www.acmicpc.net/problem/2473 세 용액의 합이 0에 가까운 값을 구하는 문제입니다. N^3으로 해결하면 시간초과가 나므로 이중 포문 + 이분 탐색을 활용해서 N^2(logN)으로 시간복잡도를 줄일 수 있습니다. 이분 탐색 조건은 현재 mid 인덱스를 사용해서 구한 세 용액의 합이 양수라면 mid 인덱스를 하한값(end)을 내림으로써 0에 가깝게 가도록 합니다. 현재 mid 인덱스를 사용해서 구한 세 용액의 합이 음수라면 mid 인덱스를 상한값(start)을 올림으로써 0에 가깝게 가도록 합니다. 추가로 주의할 점은 정수 3개를 더한 값이 정수 범위를 넘어갈 수 있으므로 long값으로 파싱해서 사용해야 합니다. 코드: https://github.com/cotcha.. 2022. 4. 28. [BOJ]2467번: 용액 문제: https://www.acmicpc.net/problem/2467 투 포인터로 해결할 수 있는 문제입니다. 주어진 용액을 오름차순 정렬한 후 start = 0, end = arr.size() - 1로 둔 뒤 절대값을 구하면서 탐색 범위를 좁혀갑니다. arr[start] + arr[end] 값이 양수라면 end-- 을 해서 값을 줄이는 방향으로 이동 arr[start] + arr[end] 값이 음수라면 start++을 해서 값을 늘리는 방향으로 이동 위와 같이 start와 end를 조절하여 O(N)에 탐색을 완료할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ2467.java 2022. 4. 28. [BOJ]2342번: Dance Dance Revolution 문제: https://www.acmicpc.net/problem/2342 YJYOON님 풀이를 참고하여 해결하였습니다. DP를 사용하여 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ2342.java 2022. 4. 27. [BOJ]1647번: 도시 분할 계획 문제: https://www.acmicpc.net/problem/1647 Union-find 문제입니다. 모든 도시가 연결되어 있다는 가정이 있으므로 그래프 => 트리로 만들 수 있습니다. 그리고 모든 도시를 연결하는 트리의 최소 비용은 MST로 만들 수 있습니다. MST를 구성한 상태에서 하나의 간선만 제외하면 도시(컴포넌트)를 2개로 나눌 수 있습니다. 제외하는 한 개의 간선은 MST 간선 중 최대 비용 간선입니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1647.java 2022. 4. 26. 이전 1 2 3 4 5 6 ··· 19 다음
