백준 | 1303번. 전쟁- 전투 | DFS 풀이
⬛ 백준 1303번. 전쟁- 전투 | DFS, BFS문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 이 문제는 가로 크기 N, 세로 크기 M으로 준다. M먼저 입력받고, N을 나중에 입력받아서 map[N][M] 해줘야 한다. 문제 전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 16.
백준 | 10026번. 적록색약 - BFS & DFS 풀이
⬛ 백준 10026번. 적록색약 - BFS & DFS 풀이 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또,..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 14.
백준 15649번. N과 M (1) - 백트래킹 문제
⬛ 백준 15649번. N과 M (1) | 백트래킹 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 11.
![백준 | 21938번. 영상처리 - DFS & BFS 풀이](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/Uq75W/btstG6duwvW/0jdHnLnEW0IkHE0klrc71k/img.png)
백준 | 21938번. 영상처리 - DFS & BFS 풀이
⬛ 백준 21938번. 영상처리 - DFS & BFS 풀이 https://www.acmicpc.net/problem/21938 21938번: 영상처리 화면의 세로 $N$, 가로 $M$ 값이 공백으로 구분되어 주어진다. 두 번째 줄부터 $N + 1$줄까지 $i$번째 가로를 구성하고 있는 픽셀의 $R_{i,j}$, $G_{i,j}$, $B_{i,j}$의 값이 공백으로 구분되어 총 $M$개 주어진 www.acmicpc.net 💚나의 풀이 입력만 주의하면 되는 문제이다. N행 M열의 map에 똑같이 이중 for문을 돌면서 하나의 map[i][j]에 3개의 값을 모두 담아 그 평균치를 담으면 된다. 이후 경계값 T보다 크거나 같으면 255 로, 작다면 0으로 세팅을 한 번 더 해주고, DFS 나 BFS로 탐색을 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2023. 8. 11.
백준 | 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 문제](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/ovxty/btspPbC8fh2/7DPnUqeGrTMCbRCl9wd4H0/img.png)
(소프티어) 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 문제](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/cDaiqb/btspxbD3nyD/Wffk0lnwKJQInkpsl9nGs1/img.png)
백준 | 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 문제](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/wb41m/btsppHCzTDY/XCauy5CyV4mSRQ0ugL7bZ0/img.png)
백준 | 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.