본문 바로가기

dfs6

줄 서는 방법(Lv.2) 문제 설명 입출력 예시 요약 n명의 사람을 n!(factorial)만큼 가지수로 나열했을 경우 k번째 나열 순서 리턴 풀이 접근 방식 1. 각 인덱스의 숫자가 얼마의 반복 주기를 갖는지 확인 → n = 4의 경우 {1, 2, 3, 4} / {1, 2, 4, 3} / {1, 3, 2, 4} / {1, 3, 4, 2} / {1, 4, 2, 3} / {1, 4, 3, 2} / {2, 1, 3, 4} / ... → 첫 번째 숫자의 경우 6개, 두 번째 숫자의 경우 2개, 세 번째와 네 번째는 각각 1개의 반복 사이클을 갖는다. → n = 4의 경우 반복되는 사이클을을 배열로 나타내면 {(n-1)!, (n-2)!, (n-3)!, (n-4)!} 임을 확인 할 수 있다. 2. k를 통해 각 인덱스에 해당하는 숫자 구.. 2024. 4. 15.
모음사전(Lv.2) 문제 설명 입출력 예시 요약 A, E, I, O, U 모음을 가지고 만들 수 있는 1~5 자리의 모든 조합(경우의 수) 구하기 풀이 접근 방식 1. 순서 파악 → A, AA, AAA, AAAA, AAAAA, AAAAE, AAAAI, AAAAO, AAAAU, AAAE, AAAEA, AAAEE, AAAEI, AAAEO, ... → dfs로 length가 5가 되면 return 2. dfs 메소드 구현 → 재귀 방식을 통한 모든 조합을 구하는 dfs 메소드 구현 코드리뷰 import java.util.*; public class Solution { String[] arr = {"A", "E", "I", "O", "U"}; List list = new ArrayList(); public void dfs(Stri.. 2024. 3. 25.
단지번호붙이기 문제 설명 입출력 예시 요약 아파트 단지의 개수와 각 단지에 속한 아파트 개수 구하기 풀이 접근 방식 1. 전체 단지의 모습을 담은 이차원 배열 graph 작성 → 전체 사이즈는 N+2로 설정(상하좌우 탐색을 위해 1~N 까지의 전체 단지를 둘러싸는 크기로 설정) → 1 : true, 0 : false로 아파트가 있는 곳 표시 2. 단지 개수 구하기 → graph의 첫 번째 row부터 순차적으로 방문하면서 true인 곳을 false로 변경 → 상하좌우 탐색 전 첫 방문시 단지 count ++ 3. 단지 내 아파트 개수 구하기 → 상하좌우 탐색해가며 true인 곳을 방문(dfs) → 방문 시 마다 아파트 count++ → 방문한 곳은 graph에서 false로 변경 코드리뷰 import java.util... 2024. 3. 24.
바이러스 문제 설명 입출력 예시 요약 1번 컴퓨터와 직.간접적으로 연결되어 있는 컴퓨터의 개수 구하기 풀이 접근 방식 1. 연결되어 있는 컴퓨터들을 이차원 배열로 표시 → graph[row][col], graph[col][row] 모두 true로 연결됨을 표시 2. 방문하지 않은 컴퓨터(노드) 확인 후 방문 → 재귀함수로 dfs 실행 코드리뷰 import java.util.*; public class Main { static int N, M; static int count = 0; static boolean[][] graph; static boolean[] visited; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N.. 2024. 3. 24.
타겟 넘버(Lv.2) 문제 설명 입출력 예시 요약 끝까지 더하거나 빼서 target을 완성할 수 있는 경우의 수 구하기 풀이 접근 방식 1. dfs를 통한 모든 경우의 수 구하기 → 재귀함수로 구현, length의 끝까지 도달했다면 return(exit) → 더하는 동작 실행 후 빼는 동작 실행 코드 리뷰 import java.util.*; class Solution { int[] nums; int targetNum; int count = 0; public void dfs(int i, int sum) { if(i == nums.length) {// 탈출조건은 length까지 도달했을 때가 된다. if(sum == targetNum) {// 마지막까지 더하거나 뺏을 때 target과 같은지 비교 count++; } return.. 2024. 3. 22.
소수 찾기(Lv.2) 문제 설명 입출력 예시 요약 주어진 숫자로 조합해서 만든 숫자가 소수인지 판별 풀이 문제 해석 각 숫자로 만들 수 있는 모든 숫자 만들어서 소수인지 판별 접근 방식 1. 모든 숫자 조합 구하기 → 순열에 가까운 조합방식으로 재귀함수를 통해 숫자 조합을 구한다. 2. 소수 판별 → 0과 1을 제외한 숫자 중, 2 ~ (해당 숫자-1)과 나눴을 때 나머지가 0이면 소수가 아님 → '에라토스테네스의 체'를 통해 해당 숫자의 제곱근까지만 반복문 실행 코드리뷰 import java.util.*; class Solution { HashSet set = new HashSet(); public boolean isPrime(int num) {// 소수인지 판별하는 메소드 boolean result = true; int .. 2024. 3. 21.

티스토리툴바