백준 38

[백준] 3055번 - 탈출

3055번 - 탈출 [문제] https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net [문제 풀이] D . * . . . . S . D * * . S * S S S D * * S S * S S S 위 표는 고슴도치가 비버의 굴을 찾아가는 과정이다. 1분에 빈칸(.)으로 한 칸씩 이동이 가능하며, 물(*)도 1분에 한 칸씩 채워진다. 물이 채워진 곳과 고슴도치의 위치를 나타내기 위해 2개의 Queue(water - 물, queue - 고슴도치)를 사용하였다. (경로를..

Baekjoon 2023.06.21

[백준] 1182번 - 부분수열의 합

1182번 - 부분수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net DFS를 통해 모든 경우의 수를 탐색한 뒤 depth가 N이고, 부분 수열의 합이 S일 경우 count를 1씩 증가하여 출력 값을 구한다. 이때 주의해야 할 점은 S가 0일 때, 부분 수열의 어떠한 수도 선택되지 않는 경우이다. S가 0이 아닐 경우 앞의 경우는 고려사항이 아니다. 즉, S가 0일 때만 count에서 1을 빼주면 된다..

Baekjoon 2023.04.07

[백준] 1107번 - 리모컨

1107번 - 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 처음 문제를 이해하고 접근할 때 완전 탐색 방법은 배제하고 접근을 했다. 길이가 10인 배열에 고장 난 버튼은 1, 정상작동 버튼은 0으로 초기화했다. 위의 예제에서 답을 구하는 방법은 5455++, 5459-- 2가지 방법이 있다. 7에서 1씩 증가, 1씩 감소 2가지 방향으로 리모컨 클릭수를 누적하였다. 하지만 이 예제는 마지막 자릿수의 버튼만 고장인 상태..

Baekjoon 2023.04.06

[백준] 2178번, 2667번

격자, 좌표, 경로 탐색 문제 -> BFS(너비우선탐색), DFS(깊이우선검색) 사용 2178번 - 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 최근 최단거리 문제를 풀 때, 역추적 방법을 사용하여 문제를 해결했던 적이 있어 역추적 방법으로 문제 접근을 했습니다. 하지만 생각해 보니 역추적으로 풀었던 문제는 오른쪽 방향을 우선순위로 이동한다는 조건이 있었습니다. 2178번 문제는 방향 우선순위 없이 칸의 숫자가 1인 칸은 모두 이동이 가능한 문제이기 때문에 역추..

Baekjoon 2023.02.12

[백준] 1644번 - 소수의 연속합

1644번 - 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 먼저 N을 입력받는다. 1부터 입력받은 N까지의 범위에서 소수를 찾아 primeArr에 추가한다. 이 문제는 소수의 합으로 N을 구하는 경우의 수 이기도 하지만, 연속된 소수의 합으로 이뤄져야 한다. 어떤 방법을 사용해야 할지 잘 생각이 나지 않아 구글링을 해봤다. 이 과정에서 '슬라이딩 윈도우 알고리즘'을 알게 되었고, 해당 글을 참고해서 문제를 풀었다. 연속된 소수의 합을 위해 누적된 값이 N이 넘지 않는다면 다음 인덱스의 요소를 더하고 단약 누적된 값이 N보다 크거나 같으면 시작하는..

Baekjoon 2023.02.05

[백준] 1456번 - 거의 소수

1456번 - 거의 소수 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 먼저 정해진 범위 내에서 소수만 저장된 List를 구한다. public static void makePrimeArr(long end) { // 소수로만 이루어진 List 생성 arr = new long[(int) (end + 1)]; for (int i = 2; i B) break; list.add((long) Math.pow(prime.get(i), j)); } } //A의 범위도..

Baekjoon 2023.02.04

소수 찾기, 구하기

이 글에서는 백준에 있는 소수 문제들을 풀면서 배웠던 부분을 정리하려고 한다. 소수 문제는 '에라토스테네스의 체'라는 개념만 확실히 알고 있어도 반 이상은 먹고 들어간다고 생각한다. 소수? 모두가 알고 있듯이 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 이런 소수를 찾는데 유명한 방법은 에라토스테네스의 체이다. 에라토스테네스를 자바로 구현한 코드이다. i = 2 ~ 100 i는 2부터 시작해서 2를 제외한 2의 배수 자리에 모두 0을 대입하여 소수가 아님을 확인한다. i가 3이 되면 앞의 방식과 동일하게 3을 제외한 3의 배수 자리에 모두 0을 대입한다. 이 과정을 거치고 나서 arr배열의 0이 아닌 수만 출력하면 소수만 출력된다. public class Main { static in..

JAVA 2023.02.01

[백준 DP] 2293번 - 동전 1

2293번 - 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net Ex) n = 3, k = 10 arr 배열 i 1 2 3 arr[i] 1 2 5 dp 배열 (dp[0] = 1, j) 1. 초기상태 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 2. i = 1일 때 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 arr[1] = 1이므로 index 1~10까지는 1로 만들 수 있는 숫자에..

Baekjoon 2023.01.04

[백준 DP] 11048번 - 이동하기

11048번 - 이동하기 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 문제를 이해하고 가장 먼저 떠오른 방법은 역추적이다. 알고리즘 학부 수업시간에서 최단경로 문제를 풀 때 역추적으로 해결한 기억이 있어 추적의 시작점을 dp [N][M]으로 설정하였다. 실행 결과는 동일하지만 제출하니 틀렸다고 한다.... 역추적으로 문제 풀이를 시작한 만큼 해결하고 싶었는데 얼떨결에 dp [1][1]부터 시작한 추적도 답과 동일한 결과가 나왔..

Baekjoon 2022.12.28

[백준 DP] 11660번 - 구간 합 구하기 5

11660번 - 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 접근은 쉽다. 값을 입력 받아 배열에 저장하고 시작점부터 끝점까지의 누적 합을 구하면 된다. 시간초과될 것을 알면서도 일단은 이중 for문을 사용하여 코드를 작성하고 제출해봤다. 좌표값을 입력 받을 때 사용하는 이중 for문은 필요한 과정이라고 생각을 했고, 누적 합을 구하는 과정에서 사용되는 이중 for문을 없애..

Baekjoon 2022.12.28