전체 글361 [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]2252번: 줄 세우기 문제: https://www.acmicpc.net/problem/2252 노드 간에 우선 순위가 있으므로 위상 정렬을 사용하여 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ2252.java 2022. 4. 27. [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. 이전 1 2 3 4 5 6 ··· 91 다음
