백준 | 14248번. 점프 점프 | DFS, BFS
⬛ 백준 14248번. 점프 점프 | DFS, BFS https://www.acmicpc.net/problem/14248 14248번: 점프 점프 첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000) 다음 줄에는 출 www.acmicpc.net 문제 영우는 개구리다 개굴개굴개굴 영우는 지금 n개의 돌이 일렬로 놓여있는 돌다리에 있다. 그리고 돌다리의 돌에는 숫자가 하나씩 적혀있다. 영우는 이 숫자가 적혀있는 만큼 왼쪽이나 오른쪽으로 점프할 수 있는데, 이때 돌다리 밖으로 나갈 수는 없다. 영우는 이 돌다리에서 자기가 방문 가능한 돌들의 개수를 알고 싶어한다..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 11.
(소프티어) Softeer | 장애물 인식 프로그램 - BFS 문제
⬛ Softeer | 장애물 인식 프로그램 https://softeer.ai/practice/info.do?idx=1&eid=409 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💚나의 풀이 전형적인 BFS 문제인데, map[][] 에 입력받을 때 고생을 했다. import java.util.*; import java.io.*; public class Main { static int N; static int[] dx = {0, 0, 1, -1}; static int[] dy = {1, -1, 0, 0}; static boolean[][] visited; static int[][] map; static ArrayList arr= new ArrayList();//각 블록..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 3.
백준 | 1699번. 제곱수의 합 - DP 문제
⬛ 백준 1699번. 제곱수의 합 - DP 문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 2.
백준 | 11055번. 가장 큰 증가하는 부분수열 - DP 문제
⬛ 백준 11055번. 가장 큰 증가하는 부분수열 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 문제 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 1.
백준 | 13398번. 연속된 정수의 합 구하기 - DP 문제
🟦 백준 13398번. 연속된 정수의 합 구하기 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다) 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 14.
백준 | 1915번. 가장 큰 정사각형 찾기 - DP 문제
🟦 백준 1915번. 가장 큰 정사각형 찾기 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 입력 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. 출력 첫째 줄에 가장 큰 정사각형의 넓이를 출력한다. 풀이 가장 큰 정사각형 넓이 구하기 == 가장 큰 한 변의 길..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 14.
백준 | 9252번. LCS - 최장 공통 부분 수열 찾기 - DP 문제
🟦 백준 9252번. 최장 공통 부분 수열 찾기 (LCS) https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS | longest common subseuence : 최장 공통 부분 수열 두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 문자열과 관련된 DP는 이 문제와 비슷한 방식으로 풀이 가능한 것이 많다. 이 문제를 꼼꼼히 숙지하여 연습할 것 문제 LC..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 14.
백준 | 10844번. 계단 수 구하기 - DP 문제
🟦 백준 10844번. 계단 수 구하기 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이 D[i][j] 의 정의 : i자릿수에서 j로 끝나는 계단 수 구하기 경우의 수 나누..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 12.
백준 | 11726번. 타일 채우기 - DP 문제
🟦 백준 11726번. 타일 채우기 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 문제 분석 : 2 X N 크기의 직사각형을 1 X2 or 2 X 1 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 1) D[N] = 2 X N크기의 직사각형을 타일로 채울 수 있는 경우의 수 2) D[1] = 1. D[2] = 2. D[3] = 3. D[4] = 5 … 이런 식으로 확장된다. 규칙성이 보인다. 즉. D[i] = D[..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 12.
백준 | 9095번. 1, 2, 3 더하기 - DP 문제
⬛ 백준 9095번. 1, 2, 3 더하기 - DP 문풀 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 11.
백준 | 1922번. 네트워크 연결 - 최소비용 신장트리
🟦 백준 1922번. 네트워크 연결 | 최소비용 신장트리 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.) 그런데 이왕이면 컴퓨..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 7.
백준 | 2660번. 회장 뽑기 - 플로이드-워샬
🟦 백준 2660번. 회장 뽑기 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제 월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다. 예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 6.
백준 | 1504번. 특정한 최단 경로 - 다익스트라
🟦 백준 1504번. 특정한 최단 경로 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 3.
백준 | 11779번. 최소비용 구하기 2 - 다익스트라
🟦 백준 11779번. 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 7. 3.