본문 바로가기

분류 전체보기167

[백준] 1495번: 기타리스트 (Java) 💡문제 분석 요약N개의 각 곡을 연주하기 전에 볼륨을 V[i] 만큼 올리거나 내릴 수 있고, 볼륨은 0에서 M 사이여야 한다.시작 볼륨 S에서 시작해서, 마지막 곡을 연주할 수 있는 최대 볼륨을 구하는 문제이다.시간 제한: 2초메모리 제한: 128MB 💡알고리즘 설계M+1 크기의 dp 배열을 생성한다. → dp[볼륨] = 연주 순서볼륨 리스트가 {5, 3, 7}일 때:0번째 연주에서 가능한 볼륨은 S = 5 → dp[5] = 01번째 연주에서 가능한 볼륨은 0, 10 → dp[0] = 1, dp[10] = 12번째 연주에서 가능한 볼륨은 7, 3 → dp[7] = 2, dp[3] = 23번째 연주에서 가능한 볼륨은 10, 0 → dp[10] = 3, dp[0] = 3N번째 곡의 볼륨 중 최댓값 → 값.. 2024. 8. 2.
[백준] 12026번: BOJ 거리 (Java) 💡문제 분석 요약1부터 N까지 보도블럭이 있고 B, O, J 순서로 이동할 수 있다. i번에서 I+1 ~ N번까지 이동할 수 있으며 k칸 이동하는데 k*k 에너지가 필요하다. 1부터 N까지 이동하는데 필요한 최소한의 에너지를 구하는 문제이다.시간 제한: 2초메모리 제한: 512MB 💡알고리즘 설계모든 경로를 탐색하며 최소 경로 찾는 문제 ⇒ DP(동적계획법)의 Bottom-Up 방식`dp` 배열을 큰 값으로 초기화한다. (MAX로 초기화) `dp[0]`은 0으로 설정한다.현재 위치 i에 대해, 이전의 모든 위치 j(0~i-1)를 검사한다. (현재: B→ 이전: J, O→B, J→ O)ex) `street[i] == 'B' && street[j] == 'J'` : 현재 위치(i)가 'B'이고 이전 위치.. 2024. 8. 1.
[백준] 1654번: 랜선 자르기 (Java) 💡문제 분석 요약길이가 제각각인 K개의 랜선을 모두 같은 길이로 잘라 N개 이상의 랜선으로 만들 때, 만들 수 있는 최대 랜선의 길이를 구하는 문제이다. (나무 자르기 문제와 유사)시간 제한: 2초메모리 제한: 128MB 💡알고리즘 설계만들 수 있는 최대 랜선의 길이를 구하기 ⇒ 이진 탐색탐색 설정left: 0right: 랜선 길이 중 최대값탐색 수행mid: `left + (right - left) / 2`mid 길이로 만들 수 있는 랜선 개수를 구한다. (`count`)범위 조정count가 N보다 크거가 같으면 → `left = mid + 1`count가 N보다 작으면 → `right = mid - 1` (더 잘게 잘라야 함)left가 right보다 작거나 같은 동안 위 과정을 반복한다.결과값으로 .. 2024. 7. 31.
[백준] 2805번: 나무 자르기 (Java) 💡문제 분석 요약나무의 수 N과 상근이가 집에 가져가려고 하는 나무의 길이 M, 나무들의 높이가 주어졌을 때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최대값을 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 💡알고리즘 설계특정 조건을 만족하는 최댓값 구하기 ⇒ 이진탐색탐색 범위left: 가장 작은 나무 길이right: 가장 높은 나무 길이탐색 수행mid: `left + (right - left) / 2`절단기에 mid를 설정했을 때 얻을 수 있는 나무 길이 구하기범위 조정구한 나무 길이가 M보다 크거나 같으면 → 값을 더 높여야 함 → `left = mid + 1`구한 나무 길이가 M보다 작으면 → 값를 더 낮춰야 함 → `right = mid - 1`l.. 2024. 7. 30.
[프로그래머스] 입국심사 (Java) 💡문제 분석 요약입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 주어질 때, 모든 사람이 심사는 받는데 걸리는 시간의 최솟값을 구하는 문제이다.$1 ≤ n ≤ 1,000,000,000$각 심사관이 한 명을 심사하는데 걸리는 시간(분): $1 ≤ time ≤ 1,000,000,000$심사관: $1≤ t ≤ 100,000$ 💡알고리즘 설계이진탐색을 사용.탐색 범위left(최소시간): 1right(최대시간): `n * max(times)` :가장 오래 걸리는 심사관이 모든 사람을 심사하는 경우탐색 수행mid(중간시간): `left + (right - left) / 2`이 시간동안 모든 심사관들이 심사할 수 있는 인원을 계산한다.범위 조정계산된 인원이 .. 2024. 7. 29.
[백준] 2661번: 좋은 수열 (Java) 💡문제 분석 요약1,2,3 으로만 이루어져 있는 길이가 N인 좋은 수열 중 가장 작은 수를 구하는 문제이다.좋은 수열은 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 없는 수열이다.시간 제한: 1초메모리 제한: 128MB 💡알고리즘 설계백트래킹 메서드 (`backTrack`)1, 2, 3 을 순차적으로 현재 수열(`seq`)에 추가한다.`seq` 에 숫자를 추가했을 때 좋은 수열인지 검사한다. (`isGoodSeq`)좋은 수열이면 숫자를 추가하여 메서드를 재귀 호출한다.`seq`의 길이가 N이 되면 출력하고 프로그램을 종료한다.좋은 수열인지 검사 (`isGoodSeq`)길이가 1인 부분 수열부터 시작해서 수열의 길이 절반까지 늘려가며 검사한다. (1부터 seq.length() / 2 까지)각.. 2024. 7. 27.
[백준] 1759번: 암호 만들기 (Java) 💡문제 분석 요약암호의 알파벳 개수 L과 사용한 문자의 종류 C를 입력받아서, 가능성 있는 암호들을 모두 구하는 문제이다.시간 제한: 2초메모리 제한; 128MB 💡알고리즘 설계C개의 문자열을 오름차순으로 `alpha` 배열에 저장하고, 자음&모음의 여부를 `check` 배열에 저장한다.start를 0부터 백트래킹을 시도한다.백트래킹 메서드매개 변수로 `start` (시작위치), `length` (암호 길이)를 받는다.`length` 가 L이면암호의 모음, 자음 최소 개수 조건을 확인하고, `result` 에 추가한다. (중복 방지를 위해 `LinkedHastSet` 타입으로 `result` 를 정의함)start부터 C-1까지 작업을 수행한다.`password[length]` 에 현재 위치의 알파벳을.. 2024. 7. 26.
반응형