자바9 백준 4811번 : 알약 📌 알고리즘 선택 알약 n개의 경우는 알약이 n개 보다 작은 경우를 활용할 수 있므로 DP로 풀 수 있다. 📌 풀이 1️⃣ 알약이 1개인 경우 >> W H >> 1가지, dp[1] =1 2️⃣ 알약이 2개인 경우 >> W H W H >> W W H H >> 2가지, dp[2] = 2 3️⃣ 알약이 3개인 경우 큰 알약을 먹음과 동시에 3가지 케이스로 나뉘게 된다. >> 작은 알약 + 큰 알약 + 큰 알약: 남은 큰 알약 2개는 dp[2]인 경우와 같으므로 dp[0] * dp[2]로 표현할 수 있다. >> 큰 알약 + 작은 알약 + 큰 알약: 앞에 큰 알약 1개와 뒤에 큰 알약 1개는 각각 dp[1]인 경우와 같으므로 dp[1] * dp[1]로 표현할 수 있다. >> 큰 알약 + 큰 알약 + 작은 알약들:.. 2023. 6. 4. 백준 7490번 : 0 만들기 | JAVA 📌 알고리즘 선택 주어진 연산자와 숫자들로 만들 수 있는 모든 식에 도달하기 위해서 DFS를 이용했다. 📌 풀이 dfs(int idx, int num, int sum, int op, String express) >> dfs 함수의 파라미터를 먼저 살펴보자. idx : idx을 통해 1부터 N까지의 수를 모두 사용하였는지 체크한다. idx는 1부터 시작한다. num: 해당 연산에서 만든 숫자이다. 공백 연산일 경우 이전의 숫자와 합쳐서 새로운 숫자를 만들어줘야 하므로 0부터 시작한다. sum: 총합이다. dfs 함수 내의 if 절에서 sum이 0이면 재귀 연산을 종료한다. op: 덧셈일 경우 1, 뺄셈일 경우 -1이다. express: 만든 식이다. dfs 함수 내의 if 절에서 sum이 0이면 해당 식을.. 2023. 6. 2. 백준 16234번 : 인구 이동 | JAVA 📌 알고리즘 선택 국경선을 연 나라들 중 인접한 나라들의 평균 인구 수를 구해야 하므로 BFS를 사용했다. 어느 정도 구현에 복잡함도 있긴 하다 ..ㅎㅎ 📌 풀이 1️⃣ migrate() 함수 >> 더 이상 인구 이동이 없을 때까지 반복문을 실행한다. >> 방문하지 않은 나라에 대해서 bfs를 실행한다. 2️⃣ bfs(int x, int y) 함수 >> 매개변수(x, y)의 나라와 인접한 나라들 중 인구 수 차이가 범위 내에 있는 나라들을 구하여 list에 저장하고, 인구 수의 총합을 리턴한다. 3️⃣ change(int sum) 함수 >> list에 저장된 나라들의 평균 인구 수를 구하여, 각 나라의 인구 수를 평균 인구 수로 갱신한다. 📌 코드 import java.io.BufferedReader; .. 2023. 6. 2. 프로그래머스 두 큐 합 같게 만들기 | 자바 📌 알고리즘 선택 별다른 알고리즘은 없고, 구현 문제라고 생각한다. 📌 풀이 정직하게 큐의 사이즈만큼 반복해서 풀이하면 시간초과가 난다. 그렇기에 조금 다르게 접근할 필요가 있다. 한쪽 큐의 합을 (두 큐의 합 / 2)로 만들어주면 어떨까? 한쪽 큐의 합이 (초기의 두 큐의 합 / 2)보다 크면 poll하여 다른 큐에 add 해주고, 작으면 다른 큐에서 poll 하여 한쪽 큐에 add 해주면 된다. 반복문은 한쪽 큐의 합과 (초기의 두 큐의 합 / 2)이 같아질 때까지 반복하면 되는데, 어떤 방식으로도 두 큐의 합을 같게 만들 수 없는 경우가 있을 수 있기에, 초기의 한쪽 큐의 길이의 3배 만큼 반복문을 반복해주고, 그래도 두 큐의 합이 같지 않다면 -1을 리턴해주자. 여기서, 왜 3배일까? 대강 최악의.. 2023. 5. 3. 프로그래머스 단어변환 | JAVA 📌 알고리즘 선택 미로찾기랑 비슷한 원리로, 경로를 기억했다가 되돌아올 필요가 있기에 DFS로 시도했다. 📌 풀이 전반적인 풀이의 흐름은 다음과 같다. 1. 한글자만 다른 단어를 찾는다. 2. 해당 단어를 visited=true 처리한다. 3. cnt를 1 증가시키고, 해당 단어를 begin으로 설정하여 dfs 탐색을 해준다. 4. 모든 경우에 대해 탐색하기 위해 visited=false 처리한다. 5. begin과 target이 같은 경우에 answer=cnt를 리턴한다. 📌 코드 import java.util.*; class Solution { static boolean[] visited; static int answer = 0; public int solution(String begin, Strin.. 2023. 4. 27. 백준 1806번 : 부분합 | JAVA 📌 알고리즘 선택 부분합 문제는 특별한 알고리즘을 활용하기보단, left 변수와 right 변수를 통해 범위를 설정하는 것이 핵심이라고 생각한다! 📌 풀이 이 문제를 풀 때 가장 유의해야 할 점은 바로,, "문제를 정확히 읽는 것" 이다. 부분합 S에 해당하는 것이 아닌 S 이상인 것의 최소 길이를 구하는 것이 문제인데,, 해당하는 것으로 읽어버려서 시간 낭비를 한 점이 굉장히 아쉬웠다. 다음부터는 문제를 꼼꼼하고 정확하게 읽도록 하자! 전반적인 풀이의 흐름은 다음과 같다. 1. int 형 배열에 주어진 수열을 입력받는다. 2. right 값을 증가시키면서 arr[right]에 접근하여 sum 값에 더해준다. 3. 만약 sum 값이 S값 보다 커진다면, 범위의 길이를 계산하여 최소길이에 해당한다면 기록해.. 2023. 4. 25. 이전 1 2 다음
