알고리즘20 백준 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. 백준 12869번 : 뮤탈리스크 | JAVA 📌 알고리즘 선택 이 문제는 빼지는 수도 3개, 빼는 숫자도 3개라 동전 문제보다 더 복잡하게 느껴졌던 문제였다. BFS를 이용하여 사용한 공격 패턴에 따라 SCV 값들을 감소시켜며 공격 최소 횟수를 구하고, DP를 이용하여 감소된 SCV 값들을 기억하여 중복 연산 횟수를 줄였다. `📌 풀이 1️⃣ scv의 수가 3개가 되도록 한다. 그래서 N이 1이나 2일 경우에는 scv의 수가 총 3개가 되도록 0을 채워준다. 2️⃣ visited[][][]의 3차원 배열을 통해 scv의 변화를 기록한다. 만약, visited[i][j][k] = 1일 경우, 0번 이상의 공격을 통해 (i, j, k)에 도달했다는 것을 의미한다. 이미 도달한 배열에 대해서는 다시 연산할 필요가 없으므로 연산을 멈춘다. 3️⃣ (i, .. 2023. 5. 31. 백준 1562번 : 계단 수 | JAVA 📌 알고리즘 선택 인접한 자리의 수를 기억하면서 풀이를 진행해야 하므로 DP를 이용해야 한다. 📌 풀이 이 문제에서 지켜야 할 규칙은 다음과 같다. 1. i번째 자리에 j라는 수가 오기 위해서는 i-1번째 자리에 j+1 혹은 j-1가 있어야 한다. 2. 0부터 9까지의 모든 수를 한 번씩 사용해야 한다. 2번 규칙을 해결하기 위해 비트마스크를 이용하여 특정 숫자를 이용했는지 아닌지를 기록하고자 한다. 비트마스크의 각 자리는 특정 숫자를 이용했는지를 나타낼 수 있고, 0부터 9까지 10개의 숫자를 확인해야 하므로 비트마스크의 자릿수는 총 10이다. 1번 규칙을 해결하기 위해 2차원 dp 배열을 이용하여 i번째 자리에 j라는 수가 있는지를 나타내고자 한다. 이를 점화식으로 나타내면 다음과 같다. dp[i][.. 2023. 5. 24. 프로그래머스 두 큐 합 같게 만들기 | 자바 📌 알고리즘 선택 별다른 알고리즘은 없고, 구현 문제라고 생각한다. 📌 풀이 정직하게 큐의 사이즈만큼 반복해서 풀이하면 시간초과가 난다. 그렇기에 조금 다르게 접근할 필요가 있다. 한쪽 큐의 합을 (두 큐의 합 / 2)로 만들어주면 어떨까? 한쪽 큐의 합이 (초기의 두 큐의 합 / 2)보다 크면 poll하여 다른 큐에 add 해주고, 작으면 다른 큐에서 poll 하여 한쪽 큐에 add 해주면 된다. 반복문은 한쪽 큐의 합과 (초기의 두 큐의 합 / 2)이 같아질 때까지 반복하면 되는데, 어떤 방식으로도 두 큐의 합을 같게 만들 수 없는 경우가 있을 수 있기에, 초기의 한쪽 큐의 길이의 3배 만큼 반복문을 반복해주고, 그래도 두 큐의 합이 같지 않다면 -1을 리턴해주자. 여기서, 왜 3배일까? 대강 최악의.. 2023. 5. 3. 이전 1 2 3 4 다음
