패스트캠퍼스 챌린지 10일차

728x90

시청 날짜 : 11/10/2021
시청 강의 : 어떻게든 푼다. 완전 탐색 (Brute Force) 응용편

오늘은 완전탐색 강의 2를 듣기 위해 문제를 푸는것을 중심으로 학습했다.

연산자 끼워넣기	https://www.acmicpc.net/problem/14888
부분수열의 합	https://www.acmicpc.net/problem/1182
암호 만들기	https://www.acmicpc.net/problem/1759

위의 연습문제를 모두 dfs를 사용하여 풀었다.

연산자 끼워넣기

~~무려 삼성 기출문제로 분류되어있다. 이렇게만 나오면 얼마나 행복할까..~~

DFS

private static void dfs(int depth , int calculated){ ... }
//main 함수:
dfs(1,nums[0]);

dfs 함수에 depth 와 현재 계산중인 int variable을 파라미터에 넘겨 재귀로 호출하였다.

depth==N에서 멈추기 때문에 처음 depth를 0 이아니라 1로 주었고, 입력받은 배열의 맨 처음 숫자를 넘겨주었다. (만약, 4 라면 4 "+" "3" 이 되어야함 -> 맨 처음 숫자는 필요!)

Return 조건

if(depth == N) {
	min = Math.min(calculated, min );
	max = Math.max(calculated, max);
	return;
}

for loop

처음에는 연산자가 아니라, N 만큼 돌려서 엄청난 디버깅을 했다.

for(int i = 0 ; i <4 ; i++) {//연산자에 대해 +,-,*,/ 확인
	if(operator[i]>0) { //연산자가 남아 있을 경우에만
		operator[i]--;//사용된 연산자 pop off
		//dfs 호출
		operator[i]++;
	}
}

하지만, operator가 사이즈가 4로 잡혀있고,

operator [0] = +의 개수 , [1] = -의 개수 , [2] = *의 개수, [3] = /의 개수

로 지정해놨다.

따라서, 루프를 4만큼 돌려야 하고, 해당 연산이 남아있는 경우에만 dfs를 호출해주었다. 이때, operator[i]--를 처리해주어야 dfs로 함수를 호출했을 때 방금 사용한 연산자를 중복 사용하는 경우가 없어지고 재귀에서 돌아오면 다시 operator[i] ++ 를 해줘서 초기화를 시켜야한다.

dfs 조건

if(i==0) dfs(depth+1 , nums[depth]+calculated);
else if(i==1) dfs(depth+1 , calculated - nums[depth]);
else if(i==2) dfs(depth+1 , calculated * nums[depth]);
else if(i==3) dfs(depth+1 , calculated / nums[depth]);

i = 0일때는 + 연산, 1일때는 - 연산 , 2 일때는 * 연산, 3 일때는 / 연산처리를 한다. (operator[i] 의 i 임*)

dfs를 재귀호출할 때, depth는 1 더하고, calculated에 방금 연산한 결과를 파라미터에 같이 보내서 다음번 계산때에도 쓸 수 있게 했다.

전체 소스 코드

package Backtracking;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @author June Park
 * @date 11/10/2021
 * dfs 를 이용하여 연산자 +-* /에 대해 남은 연산자가 있는 경우 해당연산처리 후 dfs로 보낸다
 * */
public class BOJ_14888_연산자끼워넣기 {
static int N , nums[],operator[];
static int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		nums = new int[N];
		
		operator = new int[4];//+ - * /
		for(int i = 0 ; i < N ; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < 4 ; i++) {
			operator[i]=Integer.parseInt(st.nextToken());
		}//end of input
		
		dfs(1, nums[0]);
		System.out.println(max);
		System.out.println(min);
		
	}
	private static void dfs(int depth , int calculated) {
		if(depth == N) {
			//System.out.println(calculated);
			min = Math.min(calculated, min );
			max = Math.max(calculated, max);
			return;
		}
		for(int i = 0 ; i <4 ; i++) {//연산자에 대해 +,-,*,/ 확인
			if(operator[i]>0) {		 //연산자가 남아 있을 경우에만
			operator[i]--;			 //사용된 연산자 pop off
			if(i==0) dfs(depth+1 , nums[depth]+calculated);
			else if(i==1) dfs(depth+1 , calculated - nums[depth]);
			else if(i==2) dfs(depth+1 , calculated * nums[depth]);
			else if(i==3) dfs(depth+1 , calculated / nums[depth]);
			operator[i]++;
			}
		}
		
		
	}

	
	

}

부분 수열의 합

DFS 생성

private static void dfs(int depth, int sum){...}
//main 함수:
dfs(0,0); //depth 와 sum

depth 와 현재 dfs연산의 합을 저장할 변수를 파라미터에 주었다.

Return 조건

if(depth == N) { //끝까지 찾았다면,
	if(tempSum==S) {count++;}
	tempSum = 0;//초기화
	return;
}

만약, depth 가 N 와 같다면 -> 모든 원소를 둘러보았단 소리다.

따라서, 여태까지의 합이 입력으로 받은 target Sum (S)와 같은지 확인하고 같다면, count 를 더해준다.

DFS 조건

//부분수열. 지금 위치의 원소를 선택하거나 하지 않는다
dfs(depth+1 , nums[depth]+tempSum);//선택함	
dfs(depth+1 , tempSum);	//선택안함

부분집합은 선택하거나 선택하지 않는 경우로 트리를 이룬다.

이미지 출처 : 춤추는 개발자 - JavaScript로 멱집합(PoswerSet) 리턴하는 함수 구하기

위 그림을 보면, 좀 더 이해하기 쉬울 것 같아서 가져왔다.

현재 문제에서, 선택할 경우에는 해당 숫자를 더하고 선택하지 않으면 기존 숫자를 파라미터에 넘긴다.

Count 처리

count = S==0? -1 : 0;

위 dfs 함수를 실행하기전, 위 코드를 처리해주어야 한다. 내 디버깅 시간을 잡아먹은 코드이다...

만약, 주어진 S가 0 인 경우는 공집합인 경우의 합도 0 이기 때문에 count가 하나 더 늘게 된다. ~~이게 바로 허위매물..~~

따라서, 만약 S가 0이라면 -1부터 시작, 아니라면 0부터 시작해 주면 정상적으로 공집합을 제외하고 카운트하게 된다.

전체 소스 코드

package Backtracking;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @author June Park
 * @date 11/10/2021
 * 부분 수열의 합 :dfs 를 사용하여 먼저 부분 집합을 구한 후, 
 * return statement 에서 합이 같은지 확인하는 처리를 해주었다.
*/
public class BOJ_1182_부분수열의합 {
	static int N, S , nums[], count;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		nums= new int[N];

		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N ; i++) {nums[i]=Integer.parseInt(st.nextToken());}
		
		count = S==0? -1 : 0; //합이 sum 이면 count ++해주고, 만약 S =-0 이면 공집합의 합도 0이기 때문에 1빼준다
		dfs(0,0); //depth 와 sum
		System.out.println(count);

	}
	
	/**
	 * 부분 집합 : 선택하거나, 선택하지 않거나 
	 * 위 형태의 트리를 이룬다.
	 * 즉, dfs 를 사용할 때, 현재 원소를 선택한(더한) 재귀호출과 선택하지 않은(더하지 않은) 재귀 호출을 한다.
	 * */
	private static void dfs(int depth, int tempSum) {
		if(depth == N) { //끝까지 찾았다면,
			if(tempSum==S) {
				count++;
			}
			tempSum = 0;
			return;
		}
		//부분수열. 지금 위치의 원소를 선택하거나 하지 않는다
		dfs(depth+1 , nums[depth]+tempSum);//선택함
		dfs(depth+1 , tempSum);	//선택안함

	}

}

암호만들기

놀랍게도 몇달 전에 풀어본적이 있는 문제다. 그때는 dfs 가 뭔지도 모르고 풀었는데 다시 코드를 보니 지금보다 훨씬 잘했던것같다...

이번에는 전형적인 dfs로 풀어보았다.

Arrays.sort

Arrays.sort(input); //sort 하면, 현재가 이전보다 작은거 고민할 필요 x

이부분 때문에 한참 해맸다.. 과거의 나는 놀랍게도 이 문제를 보자마자 이 생각을 했나보다.

비밀번호는 오름차순만 가능하다고 문제에서 주어젔기 때문에 ex : ABCD 가능, XASD 불가능

Arrays.sort를 사용하여 미리 알파벳 순으로 탐색할 문자 배열을 정렬해두면 별도의 조건 없이도 탐색할 수 있다.

(ex : if(depth>0 && 이전고른문자<입력받은문자배열[현재인덱스]))

DFS 생성

private static void dfs(int depth, int index, char[] passwords){...}

Return 조건

if(depth == L ) {
	int vowels=0 , consonants=0;
	for(char c : passwords) {
		if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u') {vowels++;}
		else {consonants++;}
	}
	if(vowels>=1 & consonants>=2) {
		for(char c:passwords) {
			bw.write(c);
		}
		bw.write("\n");					
	}
	return;
}

깊이 == length of password 면,

1. 조건에서 제시한 모음 1개이상과 자음 2개이상 을 만족하는지 확인하고

2. 만족하면 정답 문자열에 추가한다 (속도개선을 위해 bw를 썼지만, System.out.print를 써도 시간 초과는 나지 않는다)

DFS 조건

//중복 선택 허용 x - visited 배열 사용
for(int i = index ; i < C ; i++) { //index활용 책갈피
	if(visited[i])continue;
	visited[i] = true;
	passwords[depth] = input[i];
	dfs(depth+1 , i+1 , passwords);
	visited[i] = false;
}

패스워드 생성 시, 중복된 문자는 허용되지 않기 때문에 visited 배열을 사용하였다.

만약, 이미 사용된 문자라면 continue, 그렇지 않다면 일단 생성중인 패스워드에 문자를 담고 재귀를 돌려서 validation 체크를 하도록 한다. 재귀를 탄 후에 return statement를 만나면 다시 dfs(depth+1,i+1,passwords);지점에 돌아오게 되는데, 따라서 방문처리를 해제시켜줘야 다음번 패스워드를 정상적으로 담을 수 있다.

전체 소스 코드

package Backtracking;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 *@ author June Park
 *@ date 11/10/2021
 *1. 오름 차순 : Arrays.sort()를 사용하면, dfs에서 추가 연산 안해도 된다. (greedy)
 *2. return 조건에서 aeiou 개수 판단 
 * */
public class BOJ_1759_암호만들기 {
	static int L,C;
	static char[] input;
	static boolean[]visited;
	static BufferedWriter bw;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		L = Integer.parseInt(st.nextToken()); //length of passwords
		C = Integer.parseInt(st.nextToken()); //number of given characters
		visited = new boolean[C];
		//password : 최소 한개의 모음과 두개의 자음으로 구성 . alphabetically ordered 증가순으로 구성
		input = br.readLine().replace(" ", "").toCharArray();
		Arrays.sort(input); //sort 하면, 현재가 이전보다 작은거 고민할 필요 x

		char[] passwords = new char[L];
		dfs(0,0 , passwords);//depth, index
		bw.flush();
	}
	//count 로 길이 센다
	private static void dfs(int depth, int index, char[] passwords) throws IOException {
		if(depth == L ) {
			int vowels=0 , consonants=0;
			for(char c : passwords) {
				if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u') {vowels++;}
				else {consonants++;}
			}
			if(vowels>=1 & consonants>=2) {
				for(char c:passwords) {
					bw.write(c);
				}
				bw.write("\n");					
			}
			return;

		}
		//중복 선택 허용 x - visited 배열 사용
		for(int i = index ; i < C ; i++) { //index활용 책갈피
			if(visited[i])continue;
			visited[i] = true;
			passwords[depth] = input[i];
			dfs(depth+1 , i+1 , passwords);
			visited[i] = false;
		}
	}
}

패스트캠퍼스 환급 챌린지 바로가기👉 https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

딱 5일간 진행되는 환급챌린지로 수강료 100% 환급받으세요! 더 늦기전에 자기계발 막차 탑승!

fastcampus.co.kr

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

728x90

'📓 STUDY > FASTCAMPUS' 카테고리의 다른 글

패스트캠퍼스 챌린지 12일차 (0)	2021.11.12
패스트캠퍼스 챌린지 11일차 (0)	2021.11.11
패스트캠퍼스 챌린지 9일차 (2)	2021.11.09
패스트캠퍼스 챌린지 8일차 (0)	2021.11.08
패스트캠퍼스 챌린지 7일차 (0)	2021.11.07

연산자 끼워넣기

DFS

for loop

dfs 조건

전체 소스 코드

부분 수열의 합

DFS 생성

Return 조건

DFS 조건

Count 처리

전체 소스 코드

암호만들기

Arrays.sort

DFS 생성

Return 조건

DFS 조건

전체 소스 코드

'📓 STUDY > FASTCAMPUS' 카테고리의 다른 글

티스토리툴바