본문 바로가기

알고리즘 문제/백준81

[백준] 15721번: 번데기 (Java) 1. 문제설명n-1 회차일 때 ‘뻔 – 데기 – 뻔 – 데기 – 뻔(x n번) – 데기(x n번)’ 문장으로 진행되는 번데기 게임이 있다.플레이어는 원을 반시계 방향으로 돌아 계속 진행할 수 있다.T번째로 ‘뻔’ 또는 ‘데기’를 외치는 사람이 원에서 몇 번째 사람인지 구하는 문제이다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식무한 루프(while)를 사용해 게임을 진행한다.각 라운드마다 "뻔 – 데기 – 뻔 – 데기" 패턴을 먼저 처리한다.다음으로 “뻔”을 `round+1` 번, “데기”를 `round+1` 번 반복한다.매번 “뻔” 또는 “데기”의 `count`를 증가시키고, T번째 발생을 체크한다.원형으로 앉은 것을 고려해 사람 번호를 `person % A` 로 계산한다. 3. 틀린 이유 .. 2024. 8. 6.
[백준] 4779번: 칸토어 집합 (Java) 1. 문제설명주어진 n에 대해 “-”가 3^n이 있는 문자열을 생성하고, 모든 선의 길이가 1일 될 때까지 문자열을 3등분하여 가운데 문자열을 공백으로 만든다.마지막 문자열의 결과를 출력하는 문제이다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식문자열을 3등분하고 모든 선이 1이 될 때까지 재귀 호출하는 함수를 사용한다.cantor 함수검사하려는 시작 인덱스(`s`)와 문자열 길이(`len`)를 매개변수로 받는다.`len`이 1이면 종료한다.`len`을 3으로 나눈 `div`를 구해, `s+div ~ s+div*2`에 해당하는 부분(2번째 부분)을 공백으로 변경한다.1번째, 3번째 부분을 재귀 호출한다. 3. 최종 코드import java.io.BufferedReader;import java... 2024. 8. 6.
[백준] 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.
[백준] 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.
반응형