https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS로 이 문제를 풀 때 가장 중요한 한가지를 기억하자. 노드간의 거리를 구할 때, 자식 노드는 반드시 부모 노드의 길이 + 1 이다. public class Dev2178 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Buffere..
https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 이번 문제는 BFS의 가장 기본적인 문제다. 아래의 코드를 간략히 설명하자면, dx, dy배열을 사용하는 이유는 (curX, curY) 좌표 기준으로 동서남북에 있는 원소를 현명하게 처리할 수 있기 때문이다. 시작점이 (0,0)이 아닐 수 있으니, 시작점이 될 수 있는 요소를 모두 찾아야 한다. 따라서 vis 배열에서 아직 방문하지 않았고, matrix 배열에서 요소가 1인 숫자를 시작점으로 간주한다...
https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net https://github.com/SeongeunJi/BOJ_Algo/tree/main/%EB%B0%B1%EC%A4%80/Gold/6198.%E2%80%85%EC%98%A5%EC%83%81%E2%80%85%EC%A0%95%EC%9B%90%E2%80%85%EA%BE%B8%EB%AF%B8%EA%B8%B0 GitHub - SeongeunJi/BOJ_Algo: This is a auto push ..
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net https://github.com/SeongeunJi/BOJ_Algo/blob/main/%EB%B0%B1%EC%A4%80/Gold/2493.%E2%80%85%ED%83%91/%ED%83%91.java GitHub - SeongeunJi/BOJ_Algo: This is a auto push repository for Baekjoon Online Judge created with [BaekjoonH..
https://github.com/SeongeunJi/BOJ_Algo/tree/main/%EB%B0%B1%EC%A4%80 GitHub - SeongeunJi/BOJ_Algo: This is a auto push repository for Baekjoon Online Judge created with [BaekjoonHub](https://github This is a auto push repository for Baekjoon Online Judge created with [BaekjoonHub](https://github.com/BaekjoonHub/BaekjoonHub). - GitHub - SeongeunJi/BOJ_Algo: This is a auto push repository for B... ..
https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이번 문제는 수열과 수열 사이의 차이는 1인 점을 이용하여 간단하게 해결했다. StringTokenizer st = new StringTokenizer(br.readLine(), " "); for(int i = 1; st.hasMoreTokens(); i++) numArr[i] = Integer.parseInt(st..
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 가장 긴 증가하는 부분 수열은 아래와 같이 구할 수 있다. for(int i = 1; i numArr[j] && D[i] numArr[j] && D[i]
https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이번 문제는 확실히 매우 간단했다. 가장 마지막에 오는 숫자를 작은 문제로, 그 앞에 오는 숫자를 큰 문제로 하면 된다. 작은 문제가 1인 경우 큰 문제가 될 수 있는 건, 길이가 i-1이면서 0으로 끝나는 수이다. dp[i][1] = dp[i-1][0]; 작은 문제가 0인 경우 큰 문제가 될 수 있는 건, 길이가 i-1이면서 0 또는 1로 끝나는 수이다. dp[i][0] = dp[i-..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이번 문제는 수와 수가 차이가 1이 나는 계단수의 개수를 구하는 문제이다. 해결법은 다음과 같이 했다. 1. 조건에 맞는 dp 배열 생성. 각 행은 자릿수를, 해당 행의 각 열엔 마지막 숫자가 0~9일때 계단 수가 될 수 있는 숫자의 개수를 저장. long[][] dp = new long[101][11]; 2. 1자리 숫자일 때의 배열 초기화와 2~100 자리의 계단수의 개수 구하기 for(int i = 1; i < dp.length; i++) { for(int j = 0; j < 10; j++) { if(i ..
https://www.acmicpc.net/problem/15991 15991번: 1, 2, 3 더하기 6 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 우선 나는 이 문제를 처음부터 풀이하기엔 너무 번거로워서 아예 접근법을 모르시겠다면 이전에 작성한 1, 2, 3 더하기 포스팅을 확인하여주시면 좋을것 같다. 지난 1, 2, 3 더하기 5 문제에선 작은 문제와 큰 문제의 작은 문제가 동일하지 않은 경우를 이용하여 연속되지 않은 수들로 구성된 식의 수를 구할 수 있었다. 이번 문제는 이전 문제를 풀고 나서, 문제를 힐끔보고 자기전에 영화를 보다가 순간 생각이 번뜩여서 풀었던 문제이다 ㅋㅋㅋㅋㅋ 이번 ..
