Algorithm/기타16 섬나라 아일랜드(DFS) N*N 크기의 격자판이 주어진다. 각 격자에는 섬(1) 또는 바다(0)가 표시되어 있다. 섬은 상하좌우 및 대각선으로 연결된 1들로 이루어져 있으며, 각각의 섬은 독립적인 하나의 연결 요소로 간주된다. 주어진 격자판에서 몇 개의 섬이 있는지 구하는 프로그램을 작성해야 한다.입력 설명첫 번째 줄에 자연수 N(3 두 번째 줄부터 N개의 줄에 걸쳐 N개의 숫자가 입력되며, 각 숫자는 0(바다) 또는 1(섬)을 의미한다.출력 설명섬의 개수를 출력한다.입력 예시71 1 0 0 0 1 00 1 1 0 1 1 00 1 0 0 0 0 00 0 0 1 0 1 11 1 0 1 1 0 01 0 0 0 1 0 01 0 1 0 1 0 0 출력 예시5 해결 과정격자판 입력받기먼저 N을 입력받고, N*N 크기의 격자판을 2차원 배.. 2024. 10. 19. 미로의 최단거리 통로(BFS) 7x7 격자판 미로를 탈출하는 최단경로의 길이를 구하는 문제를 해결하기 위해 BFS(너비 우선 탐색) 알고리즘을 사용한다. BFS는 출발점에서 도착점까지 도달할 수 있는 모든 경로를 '너비'로 확장해 나가며 최단 경로를 구하는 알고리즘이다. 문제 설명격자판의 좌표 (1, 1)에서 출발하여 (7, 7)에 도착하는 최단 경로의 길이를 출력한다. 격자판의 각 칸은 벽(1) 또는 도로(0)로 이루어져 있으며, 이동할 수 있는 방향은 상, 하, 좌, 우로 한 칸씩 이동한다. 도착점에 도달할 수 없는 경우 -1을 출력한다.위 미로에서 최단 경로는 총 12칸을 이동한 것이다. 예시 입력0 0 0 0 0 0 00 1 1 1 1 1 00 0 0 1 0 0 01 1 0 1 0 1 11 1 0 1 0 0 01 0 0 0 1.. 2024. 10. 19. 미로탐색(DFS) 이 문제는 7x7 격자판에서 주어진 출발점에서 도착점까지 갈 수 있는 경로의 개수를 구하는 문제다. 격자판에서 1은 벽을 나타내고, 0은 통로를 나타낸다. 상하좌우로만 이동할 수 있으며, 중복되지 않는 경로를 찾아야 한다. 1. 문제 설명출발점: (1, 1) 좌표도착점: (7, 7) 좌표벽은 1로 표시되며, 통로는 0으로 표시됨상하좌우로만 이동 가능경로의 수를 구하는 문제2. 입력 및 출력입력: 7x7 격자판의 정보가 주어진다. 1은 벽, 0은 통로다.출력: 출발점에서 도착점까지 가능한 경로의 개수를 출력한다.3. 예제입력 예제:0 0 0 0 0 0 00 1 1 1 1 1 00 0 0 1 0 0 01 1 0 1 0 1 11 1 0 0 0 0 11 1 0 1 1 0 01 0 0 0 0 0 0 출력 예제:8.. 2024. 10. 19. 수열 추측하기(DFS) 이 문제는 파스칼의 삼각형과 조합을 이용하여, 주어진 N과 마지막 값 F를 기반으로 가장 윗줄에 들어갈 숫자들을 구하는 문제다. 입력으로 주어지는 N과 F는 각각 삼각형의 가장 윗줄에 위치한 숫자의 개수와 마지막 줄에 나오는 값이다. 1. 문제 설명주어진 N개의 숫자를 파스칼의 삼각형처럼 계산하여, 그 밑줄에 있는 숫자가 주어진 F가 되는 가장 윗줄의 숫자들을 구하는 것이 문제다. 만약 답이 여러 가지가 나올 경우, 사전순으로 가장 앞서는 경우를 출력해야 한다. 2. 파스칼의 삼각형과 가중치파스칼의 삼각형은 아래와 같이 계산되며, 각 숫자가 그 아래 숫자에 얼마나 기여하는지를 이항계수로 계산할 수 있다.예를 들어, n = 4, 그리고 주어진 윗줄이 3 1 2 4라면 다음과 같은 삼각형이 만들어진다.이 삼.. 2024. 10. 19. 조합의 경우수(메모이제이션) 1. 문제 설명조합의 경우수는 일반적으로 다음과 같은 공식을 이용해 계산한다.하지만 이 공식 대신 재귀와 메모이제이션을 활용한 방식으로 조합수를 구하는 프로그램을 작성해보자. 2. 공식조합수는 다음과 같은 재귀적 성질을 가진다.즉, n개의 원소에서 r개를 선택하는 경우는 n-1개의 원소에서 r-1개를 선택하는 경우와 n-1개의 원소에서 r개를 선택하는 경우의 합으로 계산된다.이 공식에 따라 재귀를 이용하여 조합수를 구할 수 있다. 3. 입력첫째 줄에 자연수 n(3 ≤ n ≤ 33)과 r(0 ≤ r ≤ n)이 주어진다. 4. 출력첫째 줄에 조합수를 출력한다. 5. 코드 설명package com.example.codingtest;import java.io.BufferedReader;import java.io.. 2024. 10. 18. 순열 구하기(DFS) 설명10 이하의 N개의 자연수가 주어졌을 때, 이 중 M개를 뽑아 일렬로 나열하는 모든 경우의 수(순열)를 출력하는 문제이다. 이때 출력은 사전순으로 오름차순으로 정렬된 결과를 제공해야 한다. 입력 설명첫 번째 줄에 자연수 N(3두 번째 줄에 N개의 자연수가 오름차순으로 주어진다.출력 설명첫 번째 줄에 모든 경우의 순열을 출력한다.출력되는 순서는 사전순으로 오름차순이다.예시 입력3 23 6 9 예시 출력3 63 96 36 99 39 6 풀이 과정입력된 자연수 배열에서 M개를 선택해 순서대로 나열하는 순열을 구한다.DFS(깊이 우선 탐색) 방법을 이용하여 순열을 구하며, 선택된 숫자가 다시 선택되지 않도록 체크 배열을 사용한다.모든 경우의 순열을 탐색하여 조건을 만족하면 출력한다.D(0)├── i = 0.. 2024. 10. 18. 이전 1 2 3 다음
