류호석님의 알고리즘 github 강의커리큘럼과 최백준님의 코딩테스트 준비 기초 커리큘럼을 따라 작성한 문서입니다!
또한 유튜브 ezsw님의 강의를 듣고 작성한 문서입니다.
중간중간 참고한 블로그/강의는 해당 자료 아래에 출처를 남기도록 하겠습니다!
완전탐색 (Exhaustive search, Brute force)
모든 경우의 수를 시도해 보는 방법
해를 항상 찾게되지만 실행시간이 오래걸릴 수 있다.
-순차탐색 : 나올때까지 계속 찾기(중복조합)
-중복 순열 (중복해서 순서상관o)
-경우의 수 : 순열(p)(순서o 중복x)과 조합(c)(순서x 중복x)를 구분
출처: 순수이성비판님 네이버 블로그
순열 예제 !!!!!!!!!!다시보기!!!!!!!!!!!
문제 : 가장 큰 두자리 수 구하기
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int n=4; //배열의 크기
static int[] nums= {1,2,3,4}; //미리 주어진 input
//cnt : 선택된 숫자의 개수, used : 비트형태로 사용된 숫자 마킹해둘 변수 , val :중간 계산 결과
public static int solve(int cnt,int used,int val) {
if(cnt==2) {return val;} //선택된 숫자의 수가 두개이면 재귀호출 종료 **return은 해당 함수 자체를 종료시킴
//재귀 부분
int ret=0;
for(int i=0;i<n;i++) { //모든걸 다 시도
if((used&1<<i)!=0) { //사용한 숫자라면 스킵
continue;
}
ret=Math.max(ret, solve(cnt+1,used|1<<i,val*10+nums[i])); //cnt 올려주고 해당 숫자를 사용했다고 마킹해주고 계산해주고
}
return ret;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.print(solve(0,0,0));
}
}조합 예제
가장 큰 두수의 합 구하기
출처: ezsw님 유튜브 - java 완전탐색
package codeup100;
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int n=4; //배열의 크기
static int[] nums= {1,2,3,4}; //미리 주어진 input
//pos : 현재위치, cnt : 선택된 개수 , val :중간 계산 결과
public static int solve(int pos,int cnt,int val) {
if(cnt==2) {return val;} //선택된 숫자의 수가 두개이면 재귀호출 종료 **return은 해당 함수 자체를 종료시킴
if(pos==n) {return -1;} //선택 안한것만 있을 때
//재귀 부분
int ret=0;
ret=Math.max(ret, solve(pos+1,cnt+1,val+nums[pos])); //선택하고
ret=Math.max(ret, solve(pos+1,cnt,val)); //안하고
return ret;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.print(solve(0,0,0));
}
}재귀 진짜 너무 어렵게 느껴져서 여러 코드를 디버깅해보면서 전체의 값의 흐름을 전부 체크하려고 했는데 좋은 글을 만나게 되었다.
재귀적으로 호출된 함수는 각각 독립적으로 자신이 맡은 ‘상태’에 대한 처리만을 한다는 것을 인지하고 자신의 역할에만 충실할 수 있도록 코드를 잘 작성해주면, 그 다음은 그냥 믿어주면 됩니다. 재귀 함수는 처음 보면 동작 방식을 이해하기 어렵지만, 재귀 함수를 어떤 곳에 사용할 수 있고 고려해야 할 점들이 무엇인지를 알고 나면 매우 강력한 도구가 될 수 있을 것입니다.
출처:삼성 소프트웨어 멤버십
복습하며 (3/26)
1. 순열
n개 중 r 개를 줄세우기 (1,2,3이랑 3,2,1다름)
visited를 이용해서 dfs 구현 한다.
void solve(int depth)
{
if(depth==m){//depth가 마지막 일때
//출력
return
}
for(int i=0;i<n;i++){ //1부터 n까지 돌면서
if(visited[i]!=true){ //방문하지 않은 노드이면
visited[i]=true; //방문했다고 체크
arr[depth]=i+1; //해당하는 숫자를 depth번째 배열에 넣기
solve(depth+1); //다음 depth 재귀
//재귀가 끝나고 돌아오면(basecase만족) visited 초기화
visited[i]=false;
}
}
}조합
n 개중 r개 순서 고려하지 않고 선택 (123 과 321 같음)
현재 인덱스 선택하는 경우, 선택 하지않는 경우 ->두가지 경우를 완탐
r이 0이 될때까지
- 백트래킹이용
void solve(boolean[] visited,int start,int r)
{
if(r==0){ //r==0이되면 다 뽑은거
//출력
//for문 visited가 true인것만 출력
return
}
for(int i=start;i<n;i++){ //순열과 다른것은 start부터 시작하기때문에 순열은 (2.1)가능하지만 조합은 안됨 (1,2)때 이미 함 2턴때부터 다름
visited[i]=true;
solve(visited,i+1,r-1); //r을 -1씩 해준다.
visited[i]=false;
}
}- dfs 이용
void solve(boolean[] visited,int depth,int r)
{
if(r==0){
//visited true인것 출력
return;
}
if(depth==n){
return;
}
//선택하고
visited[depth]=true;
solve(visited,depth+1,r-1)
//선택안하고
visited[depth]=false;
solve(visited,depth+1,r);
}백준 15651 : n과 m(3)
처음에는 nCm의 경우의 수를 모두 구하는 거라고 생각했는데 중복 포함이였다.
위에 재귀에 대한 내용에도 적혀있듯이
1. 함수가 어떤 기능을 하는지
2. 그것을 반복하는것은 어떤 기준을 가지고 하는지
3. 어떤 값을 반환할지
4. base case 설정 (재귀가 끝날때)
를 잘고려해서 짠게 많이 도움이 되었다.
헤맨 Point
pos=m+1일때 재귀를 끝내고 return을 해줬어야되는데 return을 안넣어줘서 꽉찬 data에 데이터를 넣으려고 했기때문에 array boundary error가 발생했다.
import java.util.*;
public class Main {
public static StringBuilder sb=new StringBuilder();
public static Scanner scanner=new Scanner(System.in);
static int n=0,m=0;
static int[] data;
public static void main(String[] args) {
n=scanner.nextInt();
m=scanner.nextInt();
data=new int[m+1];
solve(1);
System.out.println(sb.toString());
}
public static void solve(int pos) { //1~n중에서 총 m 번째 자리중 pos번째 자리를 고른 함수
if(pos==m+1) {
for(int i=1;i<m+1;i++) { // 저장된 값을 string builder에 넣어주기
sb.append(data[i]).append(' ');
}
sb.append('\n');
return;
}//m개를 다 골랐을 때 재귀 끝
for(int i=1;i<n+1;i++) { //1~n까지 자연수 중에서 m번째 자리를 고른다.
data[pos]=i; //pos번째 자리를 기록한다.
solve(pos+1); //pos+1 번째 자리를 고른다.
}
}
}복습
import java.io.*;
import java.util.*;
public class Main {
static int n,m,cnt=0;
static String str;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
static int[] arr,ans;
static boolean[] visited;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
arr=new int[m];
visited=new boolean[n];
solve(0);
System.out.print(sb);
}
public static void solve(int depth) {
if(depth==m) {
for(int a=0;a<m;a++) {
sb.append(arr[a]+" ");
}
sb.append("\n");
return;
}
for(int i=0;i<n;i++) {
arr[depth]=i+1;
solve(depth+1);
}
}
}순열에서 살짝만 손보면 되는 코드인데 sb쓰지않으면 시간초과가 난다!
백준 15649 n과 m(1)
앞에서 공부한 '순열예제'에서 사용한 비트로 사용 값 체크하는 부분을 활용해서 쉽게 풀 수 있었다!
실패 point
첫번째 제출 때 실수한 부분은 used를 1<<i로 체크하여 재귀하는 부분에서 used or로 해줘야 체크가 되는데 and로 해서 초과가 떴다 ! 실수하지 말기
import java.util.*;
public class Main {
public static StringBuilder sb=new StringBuilder();
public static Scanner scanner=new Scanner(System.in);
static int n=0,m=0;
static int[] data;
public static void main(String[] args) {
n=scanner.nextInt();
m=scanner.nextInt();
data=new int[m+1];
solve(1,1);
System.out.println(sb);
}
//pos 현재 위치 used 앞의 pos에서 사용된 숫자 체크
public static void solve(int pos,int used) { // 1~n의 자연수 중 앞에서 사용된 숫자를 제외하고 pos 위치의 값을 저장하고 하는 함수
//끝날 조건 pos가 m 일때
//리턴 해야하는 값 : m개의 데이터를 가진 수열
if(pos==m+1) {
for(int i=1;i<m+1;i++) {
sb.append(data[i]).append(" ");
}
sb.append("\n");
return;
}
for(int i=1;i<n+1;i++) {
if((used&1<<i)!=0) {//사용한 숫자라면 넘기기
continue;
}
data[pos]=i;
solve(pos+1,used|1<<i);
}
}
}복습
import java.io.*;
import java.util.*;
public class Main {
static int n,m,cnt=0;
static String str;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
static int[] arr,ans;
static boolean[] visited;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
arr=new int[m];
visited=new boolean[n];
solve(0);
}
public static void solve(int depth) {
if(depth==m) {
for(int a=0;a<m;a++) {
System.out.print(arr[a]+" ");
}
System.out.println();
return;
}
for(int i=0;i<n;i++) {
if(visited[i]==false) {
visited[i]=true;
arr[depth]=i+1;
solve(depth+1);
visited[i]=false;
}
}
}
}순열을 구하라는 문제! 순열과 조합 구현방법을 제대로 이해하자
백준 15652 :n과 m (4)
실패 point
이문제와 n과 m (3) 차이를 이해하지 못했다. 비내림차순의 의미를 파악하고는 쉽게 고칠 수 있었다.
package codeup100;
import java.util.*;
public class Main {
public static StringBuilder sb=new StringBuilder();
public static Scanner scanner=new Scanner(System.in);
static int n=0,m=0;
static int[] data;
public static void main(String[] args) {
n=scanner.nextInt();
m=scanner.nextInt();
data=new int[m+1];
solve(1);
System.out.println(sb);
}
//pos 현재 위치 used 앞의 pos에서 사용된 숫자 체크
public static void solve(int pos) { // 1~n의 자연수 중 pos 위치의 값을 저장하고 하는 함수
//끝날 조건 pos가 m 일때
//리턴 해야하는 값 : m개의 데이터를 가진 수열
if(pos==m+1) {
for(int i=1;i<m+1;i++) {
sb.append(data[i]).append(" ");
}
sb.append("\n");
return;
}
for(int i=1;i<n+1;i++) {
if(pos!=1&&i<data[pos-1]) {//i값이 data[pos]보다 작으면 continue;
continue;
}
data[pos]=i;
solve(pos+1);
}
}
}백준 15650 : n과 m(2) (다시풀기)
실패 point
if 문에서 조건을 줄때 이전 값보다 i값이 작고 1이아닌 조건 1 or 사용한적있음 이라고 줬어야하는데 and로 줌 그리고 제출할때 c++로 냄 ㅎㅎ;;
단계적으로 풀다보니까 풀리는데 뭔가 길가다 만나면 못풀각이다
import java.util.*;
public class Main {
public static StringBuilder sb=new StringBuilder();
public static Scanner scanner=new Scanner(System.in);
static int n=0,m=0;
static int[] data;
public static void main(String[] args) {
n=scanner.nextInt();
m=scanner.nextInt();
data=new int[m+1];
solve(1,1);
System.out.println(sb);
}
//pos 현재 위치 used 앞의 pos에서 사용된 숫자 체크
public static void solve(int pos, int used) { // 1~n의 자연수 중 pos 위치의 값을 저장하고 하는 함수
//끝날 조건 pos가 m 일때
//리턴 해야하는 값 : m개의 데이터를 가진 수열
if(pos==m+1) {
for(int i=1;i<m+1;i++) {
sb.append(data[i]).append(" ");
}
sb.append("\n");
return;
}
for(int i=1;i<n+1;i++) {
if((pos!=1 && i<data[pos-1] )||(used&1<<i)!=0) {//i값이 data[pos]보다 작고 사용한적 있으면 continue;
continue;
}
data[pos]=i;
solve(pos+1,used|1<<i);
}
}
}복습
import java.io.*;
import java.util.*;
public class Main {
static int n,m,cnt=0;
static String str;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
static int[] arr,ans;
static boolean[] visited;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
arr=new int[m];
visited=new boolean[n];
solve(0,m);
}
public static void solve(int depth, int m) {
if(m==0) {
for(int i=0;i<n;i++) {
if(visited[i])
{
System.out.print(i+1+" ");
}
}
System.out.println();
return;
}
if(depth ==n) {
return;
}
visited[depth]=true;
solve(depth+1,m-1);
visited[depth]=false;
solve(depth+1,m);
}
}조합을 구하라는 문제!
백준 14888번 : 연산자 끼워넣기 (다시풀기)
실패 point
처음 쓴 코드가 오래걸리기는 했으나 답과 비슷했다 실패 포인트는 for문을 4까지 돌려야하는데 부호가 총 n-1 개 있으니 n-1번 돌린게 가장 큰 미스 였고
두번째로 쓴 부호의 인덱스를 1씩 지워주는 cal[i]--를 재귀하기전에 해줬어야 됐다. 그리고 재귀가 끝나고 돌아왔을 때 cal 배열을 원상복구 하기 위해서 ++ 해줘야 됐다.
세번째로 sum이라는 변수에 값을 구하여 base case에서 비교하는 식으로 답을 구했으나 재귀가 끝나고 돌아가도 초기화가 되지 않았다. cal 함수로 return하는시그올 구현을 해줘야했다.
넘어렵다 그래도 스켈레톤은 꽤 짠것같다 좀만더해보장 ㅠㅠ
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int n;
static int[] data,cal;
static int max;
static int min;
public static void main(String[] args) {
n=scanner.nextInt(); //수의 개수
data=new int[n];
cal=new int[4];
max=Integer.MIN_VALUE;
min=Integer.MAX_VALUE;
for(int i=0;i<n;i++) {
data[i]=scanner.nextInt(); //수 배열
}
for(int j=0;j<4;j++) {
cal[j]=scanner.nextInt(); // 덧 뺄 곱 나눗셈의 순서로
}
solve(data[0],0);
System.out.println(max+" "+min);
}
public static int calculate(int a,int b, int c) {
if(c==0) {//덧
return b+a;
}
else if(c==1) //뺄
{
return b-a;
}
else if (c==2) {//곱
return b*a;
}
else if(c==3) {//나눗
return b/a;
}
return 0;
}
//sum : 계산 한 값을 넣을 변수 j: data배열에서 현재위치
public static void solve(int sum, int j) {
//i번째 까지 계산한 값과 i+1번째 숫자를 i번째 부호로 계산을 하는 함수
if(j==n-1) {//base case
max= Math.max(max,sum);
min=Math.min(min,sum);
}
for(int i=0;i<4;i++) { //부호를 다 쓸 때까지 반복
if(cal[i]==0) { //해당 인덱스에 해당하는 부호가 없을 때
continue;
}
cal[i]--; //사용했다고 표시해주기
solve(calculate(data[j+1],sum,i),j+1);
cal[i]++;
}
}
}
남기고 싶은 개발자입니다 :>