전체 글

[백준] 1182번 - 부분수열의 합 (JAVA) [접근 방법] DFS를 이용하는 풀이 이다. 기존 DFS 문제와 달리 반복문 for 문을 사용하지 않는다. // sum : 현재 부분 수열의 합 public static void dfs(int depth, int sum){ if (depth == N){ if (sum == S){정답 추가} return; } dfs(depth + 1, sum); // 다음 원소를 더하지 않는 경우 dfs(depth + 1, sum + arr[depth]); // 다음 원소를 더하는 경우 return; } 4 0 -7 -3 -2 5 위와 같은 트리 구조로 시각화 할 수 있다. 부모노드의 왼쪽 자식 노드는 dfs(depth + 1, sum +arr[depth]) 를 실행 시킨..

0. 이진수 선언 및 출력 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { int a = 0B1110; // 1110 (2) , 14 (10) System.out.println(a); // 십진수 출력 System.out.println(Integer.toBinaryString(a)); // 이진수 출력 } } 1. 비트 연산자 / 비트 이동 연산자 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOExcep..

[백준] 15661번 - 링크와 스타트 (JAVA) [접근 방법] DFS를 사용하여 해결한 문제였다. 가장 핵심적인 부분은 "방문 여부에 따라서 팀을 나눈다." 이다. visit 배열을 사용하여 0~N-1까지 수 중에서 방문 한 값은 Team : Start에 포함되고, 방문하지 않은 값은 Team : Link에 포함된다. 여기까지는 14889번 - 문제와 동일하다. 다른 점은 "두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다." 즉, 두팀의 인원수가 서로 다를 수 있다는 것이다. 기존 문제는 dfs에서 depth == N/2인 경우 calGap()을 실행 시켜 두 팀간의 능력치 차이를 탐색하였지만, 이 문제는 "팀원 수와 관계없이 능력치 차이를 조사" 한다. 14889번 - https://..

[백준] 14889번 - 스타트와 링크 (JAVA) [접근 방법] DFS를 사용하여 해결한 문제였다. 가장 핵심적인 부분은 "방문 여부에 따라서 팀을 나눈다." 이다. visit 배열을 사용하여 0~N-1까지 수 중에서 방문 한 값은 Team : Start에 포함되고, 방문하지 않은 값은 Team : Link에 포함된다. [JAVA 코드] // 14889번 - 스타트와 링크 import java.util.*; import java.io.*; public class Main { static int N; static int[][] stats; // 능력치 static boolean[] visit; static int Min = Integer.MAX_VALUE; // 최솟값 public static void ..

[백준] 1759번 - 암호 만들기 (JAVA) [접근 방법] DFS를 사용하여 해결하였다. 와 유사한 방법으로 해결하였다. '가능성 있는 암호'는 문자가 '오름차순'으로 나열된 문자열이다. 따라서, dfs함수는 이전 문자의 정보를 가지고 있어야 하기 때문에, 매개변수로 int at을 갖는다. 예외로 처리해야 할 사항이 존재한다. "암호는 최소 한 개의 모음과 최소 두 개의 자음으로 구성된다." boolean 자료형을 반환하는 "check" 함수를 생성하여, 위 사항을 예외로 처리 해준다. 코드는 아래와 같다. [JAVA 코드] // 1759번 - 암호 만들기 import java.util.*; import java.io.*; public class Main { static int L, C; static..

[백준] 10971번 - 외판원 순회 2 (!) (JAVA) [ 접근 방법 ] DFS를 이용하여 해결하였다. * 첫번째 방법 (시간초과) 첫번째로 생각한 방법은 N X N 비용 2차원 배열에, 각 행과 열에 중복하지 않고, N개의 원소를 선택하는 방법이다. * 문제에 예제 1을 그래도 사용하였다. 경로 : 2 -> 1 row : 2 와 col : 1 을 제외한다. 경로 : 2 -> 1 -> 3 row : 1 와 col : 3 을 제외한다. 경로 : 2 -> 1 -> 3 -> 4 row : 3 와 col : 4 을 제외한다. 경로 : 2 -> 1 -> 3 -> 4 -> 2 row : 4 와 col : 2 을 제외한다. * 두번째 방법 (성공) DFS 함수에 매개변수로, 경로의 출발위치는 나타내는 "star..