본문 바로가기

알고리즘 문제87

[백준] 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.
[백준] 1182번: 부분수열의 합 (Java) 💡문제 분석 요약N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열에서 그 수열의 원소를 모두 더한 값이 S가 되는 경우의 수를 구하는 문제이다.시간 제한: 2초메모리 제한: 256MB 💡알고리즘 설계`numbers` 배열에 N개의 정수를 입력받는다.부분 수열의 길이(`depth`)는 1~N까지 가능하다. 각 길이에 대해 백트래킹을 수행한다.백트래킹 메서드현재 깊이가 목표 깊이와 같으면, (`curDepth == depth`)부분수열의 합(`sum`)이 S인지 확인하고 `result`를 갱신한다.그렇지 않으면, 현재 위치(`start`)부터 N까지의 숫자에 대해해당 숫자를 `sum`에 더한다.다음 위치로 이동하여 메서드를 재귀 호출한다.백트래킹 후 `sum` 에서 해당 숫자를 뺀다. (원.. 2024. 7. 25.
[백준] 6987번: 월드컵 (Java) 💡문제 분석 요약월드컵 조별 리그의 결과를 입력받아, 입력받은 결과가 가능한지 아닌지 판별하는 문제이다.시간 제한: 1초메모리 제한: 128MB 💡알고리즘 설계문제 조건한 팀의 경기 수는 5회각 팀은 다른 모든 팀과 한 번씩 경기 ⇒ 총 15경기각 경기 결과는 승-패, 무-무, 패-승 중 하나 ⇒ 총 3가지자료구조int[] team1, int[] team2: 각 라운드별 경기를 진행하는 팀int[][] gameInputResult: 입력받은 각 팀의 경기 결과(승,무,패) 횟수int[][] gameResult: 백트래킹 과정에서 계산하는 각 팀의 경기 결과 횟수int[] result: 각 테스트 케이스의 결과를 저장하는 배열백트래킹라운드 0부터 시작해서 각 경기 결과를 가정하며 탐색각 라운드에서 3가.. 2024. 7. 24.
반응형