본문 바로가기

분류 전체보기156

[백준] 25501번: 재귀의 귀재 (Java) 1. 문제설명문제에서 주어진 팰린드롬(앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열)을 판별하는 isPalindrome 함수와 recursion 함수를 이용하여, 주어진 문자열에 대해 팰린드롬의 여부와 recursion 함수의 호출 횟수를 출력하는 문제이다.시간 제한: 2초메모리 제한: 1024MB 2. 접근 방식문제에서 주어진 isPalindrome, recursion 함수를 자바 코드로 수정한다.isPalindrome 함수recursion 함수를 호출하여 팰린드롬 여부를 검사하는 함수이다.문자열과 시작인덱스, 끝 인덱스를 인자로 recursion 함수를 호출한다.recursion 함수문자열이 팰린드롬인지 재귀적으로 확인하는 함수이다.왼쪽 인덱스가 오른쪽 인덱스보다 크거나 같으면 1을 반환.. 2024. 8. 5.
[백준] 10870번: 피보나치 수 5 (Java) 1. 문제설명n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식재귀 방법을 사용한다.피보나치 메서드합을 구한 두 개의 값을 매개변수로 받는다.두 개의 합을 구하고 저장한 뒤, 구한 합과 두 번째 매개 변수로 재귀 호출한다.n번째 피보나치 수를 구한 경우 종료한다.단, n이 0이면 0을 출력, 1이면 1을 출력한다. 그 외의 숫자는 피보나치 메서드를 호출한다. 3. 올바른 접근 방식 및 해결 방식재귀 방법을 사용해 피보나치 수를 구한다.n이 0과 1일 경우는 fibonacci 메서드를 호출하면 에러가 발생하기 때문에 따로 체크해주어야 한다. 4. 최종 코드import java.io.BufferedReader;import java.io.IOExc.. 2024. 8. 5.
[백준] 1890번: 점프 (Java) 💡문제 분석 요약각 칸에 현재 갈 수 있는 거리가 적혀있는 NxN 게임판이 주어지고, 반드시 오른쪽이나 아래쪽으로 이동할 수 있다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 문제이다.시간 제한: 1초메모리 제한: 128MB 💡알고리즘 설계이동 경로를 저장할 `dp`배열을 생성한다.시작 위치인 `dp[0][0]`을 1로 설정하고, 이중 for문으로 게임판 배열을 탐색한다.탐색 위치가 게임판의 가장 오른쪽 아래 칸이면 반복문을 종료한다.게임판에 적혀있는 숫자만큼 오른쪽 또는 아래쪽으로 이동할 수 있으면 `dp`배열에 경로를 저장한다. 💡코드import java.io.*;import java.util.*;public class Main { pu.. 2024. 8. 3.
[백준] 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.
반응형