Algorithm/BOJ172 [BOJ]1253번: 좋다 문제: https://www.acmicpc.net/problem/1253 투 포인터로 해결할 수 있는 문제입니다. 모든 수를 훑으면서 해당 수를 임의의 두 수로 만들 수 있는지 투포인터로 확인하면 O(N^2)에 해결할 수 있습니다. 투 포인터를 사용하는 방식은 1. start = 0번째 인덱스, end = N-1번째 인덱스로 둡니다. (단, 찾으려는 숫자의 인덱스는 넘어갑니다.) 2. targetNumber = number[start] + number[end] 3. targetNumber가 만들려는 수보다 크다면 end--, 작다면 start++를 해줘서 원하는 방향으로 이동시킵니다. 4. targetNumber가 만들려는 수와 일치한다면 answer++를 해준 후 정답 갯수를 리턴하면 됩니다. 코드: .. 2022. 5. 2. [BOJ]11404번: 플로이드 문제: https://www.acmicpc.net/problem/11404 기본 플로이드문제입니다. N 제한이 작으므로 O(N^3) 알고리즘인 플로이드를 사용할 수 있습니다. 유의해야할 점은 두 가지로 1. 시작 도시 a, 도착 도시 b로 가는 간선이 여러 개 주어질 수 있으니 최솟값만 저장 2. 시작 도시 a, 도착 도시 a인 경우는 0으로 처리해줘야합니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ11404.java 2022. 5. 2. [BOJ]1806번: 부분합 문제: https://www.acmicpc.net/problem/1806 전형적인 투포인터 문제입니다. start, end 포인터 두 개를 만든 후 numbers[start] + ... + numbers[end] 까지의 합을 SUM으로 저장합니다. 1. SUM >= S인 경우, start를 전진시켜서 SUM 값을 감소시킨 후 다시 비교합니다. 2. SUM < S인 경우, end를 전진시켜서 SUM 값을 증가시킨 후 다시 비교합니다. 그렇게 모든 배열을 훑은 뒤 start-end+1의 최솟값이 정답이 됩니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1806.java 2022. 5. 2. [BOJ]10775번: 공항 문제: https://www.acmicpc.net/problem/10775 Union-find를 사용한 그리디 알고리즘을 통해 해결할 수 있습니다. 어떤 비행기가 1~k번째 게이트에 도킹을 시도할 때 k번째 게이트에 도킹을 시도하는 것이 최적해입니다. 다만 k번째 게이트에 도킹을 시도할 때 이미 도킹이 되어있는 경우, 다음 게이트를 찾는 과정을 O(G)에서 시간복잡도를 줄이기 위해 Union-find를 사용합니다. 그러면 해당 해를 O(P*log(G))에 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ10775.java 2022. 5. 2. 이전 1 2 3 4 ··· 43 다음
