본문 바로가기

전체 글

 (162)
섹션 8 DFS, BFS - 13. 섬나라 아일랜드(BFS) 문제 설명N×N 크기의 격자판으로 이루어진 섬나라 아일랜드의 지도가 주어진다.각 칸은 1(섬) 또는 0(바다)로 구성되어 있고, 섬은 상하좌우 + 대각선 방향으로 연결된 1들의 묶음이다.이때 섬의 개수를 구하는 프로그램을 작성하라.입력 & 출력입력첫 줄에 정수 N (3 ≤ N ≤ 20)다음 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해결 방법 (BFS)이 문제는 BFS(너비 우선 탐색)을 활용해서 해결할 수 있다.격자판 전체를 순회하며 아직 방문하지 않은 섬(1)을 발견하면 그 지점을 시작점으로 BFS ..
섹션 8 DFS, BFS - 13. 섬나라 아일랜드 문제 설명N×N 크기의 격자판으로 이루어진 섬나라 아일랜드의 지도가 주어진다.각 칸은 1(섬) 또는 0(바다)로 구성되어 있고, 섬은 상하좌우 + 대각선 방향으로 연결된 1들의 묶음이다.이때 섬의 개수를 구하는 프로그램을 작성하라.입력 & 출력입력첫 줄에 정수 N (3 ≤ N ≤ 20)다음 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해결 방법이 문제는 DFS(깊이 우선 탐색)를 활용하여 해결할 수 있다.지도 전체를 순회하면서 아직 방문하지 않은 섬(1)을 발견하면 섬의 개수를 1 증가시킴그 좌표부터 8방..
포트원(아임포트), 부트페이, 토스페이먼츠(PG사) 특징 및 수수료 비교 작년에 회사에서 구독 서비스 구현을 담당했던 경험을 정리하려고 한다. 결제 서비스를 구현하려면 PG사 연동을 해야 하는데 방법이 두 가지가 있었다. PG사를 직접 연결하는 방법과 포트원, 부트페이와 같은 PG사 연동을 도와주는 통합결제 솔루션을 선택하여 사용하는 방법이었다. 통합결제 솔루션인 포트원, 부트페이와 PG사 토스페이먼츠에 대해 조사하여 회사에서 발표했던 내용을 간략하게 남기고자 한다. 이 세 가지 중 하나를 선택하려고 하는 사람들에게 도움이 되었으면 한다.(2024년 7월 조사 내용으로 현재 정보와 조금 차이가 있을 수 있으므로 참고용으로 봐주시길 바랍니다.)우선 PG사와 통합결제 솔루션의 차이에 대해 알아보자. 아래는 간략한 정의와 결제 flow에 대해 정리한 내용이다.PG사(결제 대행사..
섹션 8 DFS, BFS - 12. 토마토(BFS 활용) 문제 설명현수는 토마토를 보관하는 창고에서 익은 토마토가 익지 않은 토마토에 영향을 줘서 며칠 뒤 모든 토마토가 익는지를 알고 싶어한다.격자 형태의 창고에서 하루마다 익은 토마토가 인접한 칸의 익지 않은 토마토를 익게 한다.창고는 N행 M열로 구성되어 있으며 각 칸은 다음 중 하나이다:1: 익은 토마토0: 익지 않은 토마토-1: 토마토가 없는 칸모든 토마토가 익기까지의 최소 일수를 구하라.모든 토마토가 처음부터 익어 있으면 0,절대 익지 못하는 토마토가 존재하면 -1을 출력한다.입력 & 출력입력첫 줄에 M(가로), N(세로) (2 ≤ M, N ≤ 1,000)다음 N줄에 M개의 정수 (토마토 상태)출력최소 일수 (불가능한 경우는 -1)예시입력:6 40 0 -1 0 0 00 0 1 0 -1 00 0 -1 0..
섹션 8 DFS, BFS - 11. 미로의 최단거리 통로(BFS) 제 설명7×7 크기의 격자 미로에서 (1,1)에서 시작해 (7,7)에 도착하는 최단 경로의 길이를 구하는 문제입니다.여기서 경로의 길이는 출발점에서 도착점까지 지나간 칸의 수를 의미합니다.이동 가능한 칸: 0 (도로)이동 불가능한 칸: 1 (벽)상하좌우 4방향으로만 이동 가능입력 & 출력입력7×7 격자판의 각 칸의 값 (0 또는 1)출력최단 경로의 길이 출력도착할 수 없으면 -1 출력예시입력: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 0 01 0 1 0 0 0 0출력:12해결 방법이 문제는 최단 거리를 구하는 것이기 때문에, DFS보다 BFS가 적합합니다.BFS는 현재 위치에서 갈 수 있는 모든 방향을 먼저 탐색하..
섹션 8 DFS, BFS - 10. 미로탐색(DFS) 문제 설명7×7 격자판 미로에서 출발점 (1,1)에서 도착점 (7,7)까지 이동할 수 있는 모든 경로의 수를 구하는 문제입니다.격자 내 0은 이동 가능한 통로, 1은 이동 불가능한 벽입니다.이동은 상하좌우 네 방향으로만 가능합니다.입력 & 출력입력7×7 정사각형 격자판이 주어집니다. 각 값은 0 또는 1입니다.시작점은 항상 (1,1), 도착점은 (7,7)입니다.출력첫 줄에 이동 가능한 경로의 수를 출력합니다.예시입력: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해결 방법DFS(깊이 우선 탐색)을 사용해 출발점부터 도착점까지 경로를 따라가며 가능한 모든 경우의 수를 탐색합니다.이미 ..
섹션 8. DFS, BFS 활용 - 9. 조합 구하기 문제 설명1부터 N까지의 자연수 중에서 M개를 중복 없이 골라 오름차순 조합을 모두 출력하는 문제입니다.입력 & 출력입력첫 번째 줄에 자연수 N(3 ≤ N ≤ 10), M(2 ≤ M ≤ N) 이 주어집니다.출력한 줄에 하나씩, 오름차순으로 조합을 출력합니다.예시입력:4 2출력:1 21 31 42 32 43 4해결 방법DFS와 백트래킹을 이용해서 조합을 탐색합니다.오름차순으로 중복되지 않게 선택하기 위해 DFS(L, S)에서 S를 다음 단계로 넘겨줍니다.종료 조건은 뽑은 숫자의 개수(L)가 M이 되었을 때입니다.코드 구현package partDfsBfs;import java.util.Scanner;public class Problem9 { static int n, m; static int[] c..
섹션 8 DFS, BFS - 8. 수열 추측하기 문제 설명가장 윗줄에 1부터 N까지의 숫자 중 서로 다른 N개의 숫자가 한 개씩 적혀 있고, 그 아래줄부터 위 두 수를 더한 값이 저장되는 방식으로 삼각형을 만든다. 예를 들어 N=4이고 윗줄이 3 1 2 4이면 다음과 같다.3 1 2 4 4 3 6 7 9 16 가장 아랫줄의 값 F가 주어질 때 윗줄에 어떤 숫자를 배치해야 이 삼각형의 최하단 값이 F가 되는지 구하는 문제이다.답이 여러 개인 경우 사전순으로 가장 앞서는 배열을 출력한다.입력 & 출력입력첫 줄: 두 개의 정수 N, F (1 ≤ N ≤ 10, F ≤ 1,000,000)출력조건을 만족하는 수열을 사전순으로 출력 (공백 구분)예제 입력 & 출력예제 입력 4 16예제 출력 3 1 2 4해결 방법파스칼의 삼각형 구조 활용맨 마..

티스토리툴바