본문 바로가기

알고리즘19

자바 - 백준 12015 / 가장 긴 증가하는 부분 수열2 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 골드2 구현 방법 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이므로 DP로 풀 경우 O(n^2)의 시간복잡도를 가지므로 런타임 에러가 발생한다. 따라서 이 문제의 경우, 이분 탐색으로 구현해야 한다. 하지만 여기서 이해가 안되는 부분이 생겼다. 예를 들어서 5 6 2 7이라는 수열이 있다고 하자. 이 경우 이분 탐색으로 구현 하면 순서는 다음과 같다. 1. 5 2. 5 6 3. 2 6 .. 2023. 7. 21.
자바 - 백준 14889 / 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 실버 2 구현 방법 처음에 보고 재귀로 풀어야 겠다는 생각이 들어서 바로 풀었지만 시간 초과가 났다. 생각해보니 문제는 조합을 의도한거였는데 순열로 풀어서 시간 초과가 난거였다. 구현 자체는 간단하다. 1. n명의 사람들 중 반을 조합으로 선택한다. 2. 조합으로 선택된 사람들의 능력치를 구한다 3. 차이값을 계산하여 최소값인 경우 저장한다. 코드 import java.io.BufferedReader; import j.. 2023. 7. 17.
자바 - 백준 17144 / 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 골드 4 구현 방법 구현 문제라서 문제부터 간단하게 요약했다. plate -> r * c 공기청정기 = 1번열(c) 설치, 두행(r) 차지한다 미세먼지 양 = A(r, c) a. 미세먼지 모든칸 동시에 확산, 네방향으로 인접한 방향에 공기청정기 있거나 칸없으면 확산 x 확산 양 : a(r,c) / 5 소수점 버리기 (r,c)에 남은 양 : a(r, c) - a(r,c)/5 * (확산 방향 개수).. 2023. 7. 4.
자바 - 백준 16235 / 나무 재테크 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 골드3 구현 방법 구현 문제라서 일단 문제의 조건을 간단하게 정리 했다. 1. n * n = 땅 크기 2. 처음 모든 칸 양분 5 3. m = 나무 개수 4. 봄 -> 자신의 나이만큼 양분 먹음 -> 나이 +1 5. 한칸에 여러개 나무 가능 6. 나이 어린 나무부터 양분 먹음, 양분 부족하면 바로 죽음 7. 여름 -> 죽은 나무 양분으로 변함, 나무 나이 // 2 8. 가을 -> .. 2023. 6. 30.

티스토리툴바