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++를 해준 후 정답 갯수를 리턴하면 됩니다. 코드: .. Algorithm/BOJ 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 Algorithm/BOJ 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 Algorithm/BOJ 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 Algorithm/BOJ 2022. 5. 2.

• 

  [BOJ]2098번: 외판원 순회 문제: https://www.acmicpc.net/problem/2098 비트마스킹 + DP로 해결할 수 있습니다. dp 상태정의를 dp[현재까지 방문한 상태][현재 노드]로 하고 점화식은 아래와 같이 세울 수 있습니다. dp[nxtState][nxtNode] = min(dp[nowState][nowNode] + cost[nowNode][nxtNode]) 방문 상태를 저장함으로써 중복 방문을 없앨 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ2098.java Algorithm/BOJ 2022. 5. 1.

• 

  [BOJ]16946번: 벽 부수고 이동하기 4 문제: https://www.acmicpc.net/problem/16946 BFS + 아이디어가 필요한 문제입니다. NM 값이 100만이므로 벽 갯수만큼 BFS를 돌려보면 시간초과가 납니다. 그러므로 BFS를 도는 횟수를 줄여야합니다. 해결한 아이디어는 다음과 같습니다. ex. 빈 칸끼리 붙어있는 값을 '컴포넌트'라고 하겠습니다. 1. 전체 BFS를 1번 돌면서 빈 칸으로 이뤄져있는 모든 컴포넌트 정보를 (컴포넌트번호, 컴포넌트 내 빈 칸 갯수) 저장합니다. 2. 1번 연산을 마친 다음에 모든 벽에 대해 벽이 있는 해당 칸과 인접한 4칸에 존재하는 컴포넌트 갯수를 더해줍니다. 1번에서 빈 칸 갯수 외에 '컴포넌트 번호'를 굳이 저장한 이유는 인접한 4칸을 탐색할 때 동일한 컴포넌트에 포함되는 빈 칸을 중.. Algorithm/BOJ 2022. 5. 1.