School algo02 전수조사

재귀를 이용한 전수조사문제는 거시적 관점에서는 대부분 재귀트리를 내리락 오르락 하면서 답을 찾아나간다. 다만 세부적으로보면 올라가면서 답을 찾는 경우가 있고 완전히 내려와서 찾는 경우가 있다(물론 내려가면서 찾을수도 있지만 이 경우는 내가 경험해 본 바에 의하면 올라가면서 찾는 경우로 바꿀수 있고 그렇게 바꾸는게 더 코드가 좋다). 이는 어디까지나 세부적으로 보았을때 그렇다는 말이지 거시적으로는 대부분 내리락 오르락 하면서 답을 낸다.  

 

import java.util.Scanner;

public class Main {
	// int[블록을 놓는 모양][모양에 따른 블록들의 상대좌표][상대 좌표]
	// 가장 왼쪽 위 블록을 기준으로 상대좌표를 산정한다.
	// (y좌표,x좌표)
	private static int[][][] coverType = { { { 0, 0 }, { 1, 0 }, { 0, 1 } }, // ┌
			{ { 0, 0 }, { 0, 1 }, { 1, 1 } }, // ┐
//			{ { 0, 0 }, { 1, 0 }, { 0, -1 } },
			{ { 0, 0 }, { 1, 0 }, { 1, 1 } }, // └
			{ { 0, 0 }, { 1, 0 }, { 1, -1 } } // ┘
//			{{0,0}, {0,1}, {-1,1}}
	};
	//coverType[4개중어느것?][3개중어느것?][2개중어느것?]
    
	// 블록을 쌓을 수 있는지 확인하고 쌓고 빼는 메서드
	// Stack이 1이면 쌓고, Stack이 -1이면 뺀다.
	private static boolean stackAndAbs(int[][] board, int y, int x, int type, int stack) {
		boolean ok = true;

		for (int i = 0; i < 3; i++) {
			int ny = y + coverType[type][i][0];
			int nx = x + coverType[type][i][1];

			// 보드 밖으로 나갔을 때, false 반환
			if (ny < 0 || ny >= board.length || nx < 0 || nx >= board[0].length) {
				ok = false;
				// 검은 칸에 쌓았을 때(Stack = 2) false 반환
			} else if ((board[ny][nx] += stack) > 1) {
				ok = false;
			}
		}
		return ok;
	}
	// 보드에 블록을 쌓는 메소드
	private static int solution(int[][] board) {
		int y = -1, x = -1;
		//블럭을 채워나가는 중이더라도 아래와 같이 board의 첫번째 칸부터 매번 시작해야하는건 비효율적으로 보일수 있지만 어쩔수 없는거.
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if (board[i][j] == 0) {
					y = i;
					x = j;
					break;
				}
			}
			// 빈칸(board[i][j]==0)을 찾고 세로줄(j) for문을 빠져 나왔을 때, 다음 가로줄(i)로 넘어가면 안되므로 다시 break
			if (y != -1) 
				break;
		}
		// 모든 빈칸이 메꿔지면 y,x의 값은 -1이므로 이 때, 하나의 경우를 만족하므로 1 반환.
		if (y == -1) //x==-1도 괜찮음
			return 1;
		int result = 0;// 모든 레벨의 solution함수마다 result=0으로 시작한다.
		for (int type = 0; type < 4; type++) {
			// board[y][x]를 type형태로 덮을 수 있으면 재귀 호출로 다음 블록을 놓는다.
			if (stackAndAbs(board, y, x, type, 1)) {
				result += solution(board);// 하나의 판을 모두 덮는데에는 같은 개수의 블럭이 필요할 것이므로 바로위의 if문을 통과한 횟수는 어떤 경로에서든지 같을것이다.
			}
			// 보드에 쌓았던 블록을 치운다.set이 boolean을 반환해도 반드시 반환되는 것을 받을 필요는 없다. 이런 유연성도 꼭 익숙히 하자!
			stackAndAbs(board, y, x, type, -1);
		}
		return result;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int loop = sc.nextInt();
		int[] result = new int[loop];
		int num=0;
		while (num<loop) {
			int height = sc.nextInt();
			int width = sc.nextInt();
			int[][] board = new int[height][width]; // board[i][j]의 값이 1 이상이면 블록이 존재 0이면 없는것.

			String tmp;
			sc.nextLine(); // Scanner 에서 \n을 제거하기 위함.

			for (int i = 0; i < height; i++) {
				tmp = sc.nextLine().replace("#", "1").replace(".", "0");
				for (int j = 0; j < width; j++) {
					board[i][j] = Integer.parseInt(tmp.substring(j, j + 1));
				}
			}
			result[num] = solution(board);
			System.out.println(result[num]);
			num+=1;
		}
	}
}

왜 하필 블럭의 좌표를 설정해 줄때 ㅢ 모양의 블럭의 좌표를 -1을 포함하여 넣어준다고 의문을 품을 수 있다. 이 의문에 대한 답은 이렇다. “이미 점유 되었는지, 경계를 넘어가는지를 판별하는 기능은 코드 속에 담겨 있지만 빈곳이 남아있는지를 검사하는 기능은 없다는 것이다.” 따라서 빈곳은 어떻게든 만들어서는 안된다. 만약 -1이 없게 ㅢ 모양의 블럭을 좌표안에 넣는 다면 (아래그림처럼)

좌표(0,0)은 그대로 빈곳으로 남겨지게 되고 그 상태로 알고리즘이 흘러가고 잘못된 답이 나오는 것이다. 반면

와 같이 일부러 범위를 벗어나게 처음부터 설정해 주면 애초에 알고리즘에서 걸러지도록 블럭이 배치되어 그 오답이 걸러지게 된다는 것이다!  

위와 같은 이유로 ㅢ 모양의 블럭에 예외를 허용한다고 하면 왜

이와 같은 모형은 안되는가에 답하기 힘들다. 이에 대한 이유는 이와 같은 것을 허용해 버리면 초반부에 기역자 모양의 블럭으로 (0,0)을 차지하며 시작하게 되는 경우는 영영 카운팅할수 없게 된다는 것이다. ('ㄱ'모양의 한군데 빈 곳은 나중에 'ㄴ' 모양의 블럭이 매꿀수 있지만 (0,0)을 비워둔 거꾸로된 'ㄴ'은 사방에서 막고 있어 (0,0)을 채울수 없음)

 

즉, 정리하면 보편타당하게 블럭을 놓기는 놓되 알고리즘에서 걸러지더라도 영영채워질수 없는 빈칸은 만들면 안된다는 것이다(빈칸을 만들면 오답이 나오지만 애초에 알고리즘에서 걸러지도록 블럭을 배치하면 그 오답이 걸러지게 된다는 것이다!!!). 

 

게임판 덮기. 파이썬

from sys import stdin
bricks=[[[0,0],[1,0],[0,1]],
    [[0,0],[0,1],[1,1]],
    [[0,0],[1,0],[1,1]],
    [[0,0],[1,0],[1,-1]]
    ]

def stackAndAbs(board, y, x, type, stack):
    ok=True
    for i in range(3):
        ny=y+bricks[type][i][0]
        nx=x+bricks[type][i][1]
        if(nx<0 or nx>=len(board[0])or ny<0 or ny>=len(board)):
            ok=False
        else:
            board[ny][nx]+=stack
            if(board[ny][nx]>1):
                ok=False
            #파이썬에서는 조건식안에 +=연산자를 쓸수 없다. 따라서 elif((board[ny][nx]+=stack)>1):ok=False
            #와 같은 식을 사용할 수 없어. 위와같이 코드의 양이 늘어난다.
    return ok

def solution(board):
    y,x=-1,-1
    for i in range(len(board)):
        for j in range(len(board[0])):
            if(board[i][j]==0):
                y=i
                x=j
                break
        if( y!=-1):
            break
    if(y==-1):
        return 1
    result=0
    for i in range(4):
        if(stackAndAbs(board, y, x, i, 1)):
            result+=solution(board)
        stackAndAbs(board, y, x, i, -1)
    return result

def main():
    num=int(stdin.readline())
    for _ in range(num):
        r, c=map(int, stdin.readline().split())
        # board[r][c]
        board=[[0]*c for _ in range(r)]
        for i in range(r):
            string=stdin.readline().replace("#", "1").replace(".", "0")
            for j in range(c):
                board[i][j]=int(string[j:j+1])
        
        print(solution(board))

main()

게임판 덥기 최종

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Testing3 {
    /*
    불변객체의 멤버변수는 기본적으로 private, final임. 그런데 내부클래스로 쓰이므로 접근제어자는 무시됨(복습. 내부클래스의 접근
     제어자는 별도의 클래스에서 접근할 때나 의미가 있음. 하지만 내부 클래스를 별도의 다른 클래스가 사용한다는 것은 적절치 못함).
    (복습. 불변클래스를 static으로 수식함. static 내부 클래스는 외부 클래스에 대한 포인터주소를 유지하지 않는다)

     그렇다면 왜 내부클래스로 불변데이터 클래스인 record를 사용했을까? 이 내용 질문해서 답변은 내부클래스로 record를 사용하면
     생성자생략, Object메서드생략, 불변객체를 만들수 있어서 그렇다는 답변을 들었다. 하지만 내가 record를 실제로 일반 클래스로
     바꾸어도 문제가 없었고 record를 사용했을때보다 불편했던점은 생성자를 따로 코딩해 주어야 했었던 점이다. 즉, 내 생각에는
     static 중첩 (일반)클래스를 사용해도 된다!
     */
    static record Location(int r, int c) {
        static int height = 0;
        static int width = 0;

        static boolean isValid(int r, int c) {
            return (r >= 0 && r < height && c >= 0 && c < width);
        }
    }


    public static int[][][] cover = {
            {{0, 0}, {0, 1}, {1, 1}}, // ㄱ
            {{0, 0}, {0, 1}, {1, 0}}, // ㄱ의 반대
            {{0, 0}, {1, 0}, {1, -1}}, // ㄴ의 반대
            {{0, 0}, {1, 0}, {1, 1}} // ㄴ
    };

    public static boolean put(boolean[][] board, int r, int c, int[][] cover) {
        for (int i = 0; i < 3; ++i) {
            int locR = r + cover[i][0];
            int locC = c + cover[i][1];
            if (!Location.isValid(locR, locC) || board[locR][locC])
                return false;
        }
        for (int i = 0; i < 3; ++i)
            board[r + cover[i][0]][c + cover[i][1]] = true;
        return true;
    }

    public static void remove(boolean[][] board, int r, int c, int[][] cover) {
        for (int i = 0; i < 3; ++i)
            board[r + cover[i][0]][c + cover[i][1]] = false;
    }

    public static Location getStartLoc(boolean[][] board, int r, int c) {
        while (r < Location.height) {
            while (c < Location.width) {
                if (!board[r][c]) return new Location(r, c);
                ++c;
            }
            c = 0;
            ++r;
        }
        return null;
    }

    //내가 파이썬으로 짠 코드는 매번 블록이 점유되어있는지를 1행 1열의 블럭부터 검사했다. 이것은 solve함수에 행, 열 정보를 알려주는
    //아래의 R,C를 매개변수로 데리고 다니면 해결되는 문제이다. 그리고 다음 블럭의 위치를 찾기위해 getStartLoc이라는 함수를 정의해주었다.
    public static int solve(boolean[][] board, int R, int C) {
        Location nextLoc = getStartLoc(board, R, C);
        if (nextLoc == null) return 1;
        int ret = 0;
        for (int t = 0; t < 4; ++t) {
            if (put(board, nextLoc.r, nextLoc.c, cover[t])) {
                ret += solve(board, nextLoc.r, nextLoc.c);
                remove(board, nextLoc.r, nextLoc.c, cover[t]);
            }
        }
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine().strip());
        for (int t = 0; t < T; ++t) {
            StringTokenizer st = new StringTokenizer(in.readLine().strip());
            Location.height = Integer.parseInt(st.nextToken());
            Location.width = Integer.parseInt(st.nextToken());
            boolean[][] board = new boolean[Location.height][Location.width];
            int count = 0;
            for (int r = 0; r < Location.height; ++r) {
                char[] line = in.readLine().strip().toCharArray();
                for (int c = 0; c < Location.width; ++c) {
                    if (line[c] == '#') board[r][c] = true;
                    else ++count;
                }
            }
            if (count % 3 != 0) System.out.println(0);
            else System.out.println(solve(board, 0, 0));
        }
    }
}

 

 

import java.util.*;
public class Main{
    public static boolean answer;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        for(int i=0;i<num;i++) {
            int target=sc.nextInt();
            int n=sc.nextInt();
            int[]arr=new int[n];
            for(int j=0;j<n;j++)
                arr[j]=sc.nextInt();
            answer = canSum(target, arr);
            System.out.println(answer);
            answer = false;
        }
 
    }
 
    public static boolean canSum(int target, int[] arr) {
        if (target < 0)
            return false;
        if (target == 0)
            return true;
 
        for (int i = 0; i < arr.length; i++) {
            if (canSum(target - arr[i], arr)) {
                answer = true;
                break;
            }
        }
        return answer;
         
    }
}

2023.02.15

#23.2.15 파이썬으로 다시해본 Cansum
def cansum(target, arr,n):
    if(target<0):
        return False
    if(target==0):
        return True
    else:
        for i in range(n):
            if(cansum(target-arr[i], arr, n)):
                return True
    return False
#재귀함수를 조건문안에 넣어서 True인 경우 그대로 True를 반환하게끔 하고
#False인 경우 아예 if문을 실행하지 않되 for문은 돌아 다음 차례의 수를 뺄수 있게
#구성하였다... 나는 음수일 경우 False를 return할 것은 생각했지만 false가 나온후
#어떻게 다음수로 넘어가 재귀함수를 계속 진행할지 난감해 했었는데... 재귀함수를
# 조건문에 넣음으로써 단번에 해결하였다...
            

n=int(input())
for i in range(n):
    target, number=map(int, input().split())
    
    arr=list(map(int, input().split()))
    length=len(arr)
    print(cansum(target, arr, length))

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Main{
    static LinkedList<Integer>list;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        for(int i=0;i<num;i++) {
            int target=sc.nextInt();
            int len=sc.nextInt();
            int[]arr=new int[len];
            for(int j=0;j<len;j++)
                arr[j]=sc.nextInt();
            list=howSum(target, arr);
            if(list==null)
                System.out.println(-1);
            else {
                System.out.print(list.size()+" ");
                Iterator<Integer>it=list.iterator();
                while(it.hasNext()) {
                    System.out.print(it.next()+" ");
                }
                System.out.println();
                list.clear();
            }
        }
         
    }
    private static LinkedList<Integer> howSum(int target, int[] arr) {
        LinkedList<Integer>list;
        if(target<0)return null;
        if(target==0)return new LinkedList<Integer>();
        for(int i=0;i<arr.length;i++) {
            list=howSum(target-arr[i], arr);
            if(list!=null) {
                list.add(arr[i]);
                return list;
            }
        }
        return null;
    }
     
}

2023.02.15

# 2023.02.15 Python으로(내려가면서 답을 구하는 별로 추천하지 않는코드. 무엇보다 지저분함)

def howSum(arr, target, length):
    if(target<0):
        answer.pop(-1)
        return False
    if(target==0):
        return True
    for i in range(length):
        answer.append(arr[i])
        if(howSum(arr, target-arr[i], length)):
            return True
    if(len(answer)>0):
        answer.pop(-1)
    return False

n=int(input())
for i in range(n):
    target, number=map(int, input().split())
    arr=list(map(int, input().split()))
    length=len(arr)
    answer=[]
    if(howSum(arr,target,length)):
        le=len(answer)
        print(le, end=' ')
        for i in range(le):
            print(answer[i],end=' ')
        print()
    else:
        print(-1)
        
#2023.2.26 올라오면서 답을 구하는 코드

def howSum(target, arr):
    if(target<0):
        return None
    if(target==0):
        return []
    for i in range(len(arr)):
        answer=howSum(target-arr[i], arr)
        if(answer!=None):
            answer.append(arr[i])
            return answer
    return None

    

n=int(input())
for i in range(n):
    target, number=map(int, input().split())
    arr=list(map(int, input().split()))
    answer=howSum(target, arr)
    if(answer==None):
        print(-1)
    else:
        print(len(answer), *answer)
        
        
#2023.7.4 학기가 끝난후 아래와 같은 방식으로 해결해 보았다. 하지만 위의 풀이가 더 깔끔한거 같다. 
#참고로 기록하여 둔다.


from sys import stdin

def howSum(target, arr, answer):
    if(target==0):
        print(len(answer), *answer)
        return True
    if(target<0):
        return False
    
    for i in range(len(arr)):
        answer.append(arr[i])
        if howSum(target-arr[i], arr, answer):
            return True
        else:
            answer.pop()
    return False

def main():
    num=int(stdin.readline())
    for _ in range(num):
        target, n=map(int, stdin.readline().split())
        arr=list(map(int, stdin.readline().split()))
        answer=list()
        if not howSum(target, arr, answer):
            print(-1)

main()

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static int answer;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        for (int i = 0; i < num; i++) {
            int target = sc.nextInt();
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int j = 0; j < n; j++)
                arr[j] = sc.nextInt();
            answer = countSum(target, arr);
            System.out.println(answer);
        }
 
    }
 
    public static int countSum(int target, int[] arr) {
        int result=0;
        if (target < 0)
            return 0;
        if (target == 0)
            return 1;
 
        for (int i = 0; i < arr.length; i++) 
                result+=countSum(target-arr[i],arr); 
        return result;
         
    }
}

2023.02.15

 #2023.02.15 파이썬으로 다시 품
def countSum(arr, target, length):
    global count
    if(target<0):
        return 
    if(target==0):
        count+=1
        return 
    for i in range(length):
        countSum(arr, target-arr[i], length)


n=int(input())
for i in range(n):
    target, number=map(int, input().split())
    arr=list(map(int, input().split()))
    length=len(arr)
    count=0
    countSum(arr, target, length)
    print(count)
    
#2023.2.18 전역변수 쓰지 않고 풀기
def countSum(arr, target):
    count=0
    if(target==0):
        return 1
    if(target<0):
        return 0
    for i in range(len(arr)):
        count+=countSum(arr, target-arr[i])
    return count

num=int(input())
for _ in range(num):
    target, number=map(int, input().split())
    arr=list(map(int, input().split()))
    result=countSum(arr,target)
    print(result)

 

 

 

 

 

우선 아래 BestSum문제에 대한 코드는 전역변수를 사용해서 해결한다는 점이 가장 잘못되었다. 전역변수는 가급적 지양해야 하고 이문제는 전역변수 없이도 해결가능하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
 
 
public class Main {
    public static LinkedList<Integer> list = new LinkedList<>();
    public static LinkedList<Integer> slist = new LinkedList<>();
 
    public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        for (int i = 0; i < num; i++) {
            int target = sc.nextInt();
            int len = sc.nextInt();
            int[] arr = new int[len];
            for (int j = 0; j < len; j++)
                arr[j] = sc.nextInt();
 
            bestSum(target, arr, slist);
 
            if (list.isEmpty()) {
                if(target==0)
                    System.out.println("0");
                else
                    System.out.println("-1");
            }
            else {
                System.out.print(list.size()+" ");
                Iterator<Integer>it=list.iterator();
                while(it.hasNext())
                    System.out.print(it.next()+" ");
                System.out.println();
            }
            list.clear();
        }
    }
 
    public static void bestSum(int target, int[] arr, LinkedList<Integer> slist) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            if (list.isEmpty()) {
                Iterator<Integer> it = slist.iterator();
                while (it.hasNext())
                    list.add(it.next());
			//매번 list와 slist의 길이를 비교하고 있음... 이렇게 되면 상당히 피곤함...	                    	
            }else if (list.toArray().length > slist.toArray().length) {
                list.clear();
                Iterator<Integer> it = slist.iterator();
                while (it.hasNext())
                    list.add(it.next());
            }
//             System.out.println("What's in slist?" + slist.toString());
//               System.out.println("What's in list?" + list.toString());
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            slist.add(arr[i]);
            bestSum(target - arr[i], arr, slist);
            slist.pollLast();
        }
    }
}

교수님께서 bestsum문제에 대한 내가 생각해 낸 해결책에 대해 " 원래 강의 슬라이드에 있는 예제는 위로 올라오면서 best를 찾는데, 학생 코드는 0애 도달했을 떄 답을 찾고 있습니다" 라고 말씀하신다. 그래서 원래 출제자의 의도(?)에 맞게끔 위로 올라가면서 답을 찾게끔 코드를 남겨놓는다. 왜 이게 올라가면서 답을 찾는거고 내가 한것은 아래로 내려가면서 답을 찾는것 인지 명확하게 인식해 놓자! (23.2.16. 정답부터 말하자면 아래로 내려가면서 답을 찾는 다는 것은 답을 내리는 요소의 작성과정을 재귀문 앞에 놓는지 뒤에 놓는지이다. 예를 들어 아래 교수님 코드에서 답을 출력하는데 필수적인 요소인min, cur LinkedList는 재귀문인 bestSum2(target-arr[i], arr)문 다음에 작성되고 있다(cur.add([arr[i]) ).

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        for (int i = 0; i < num; i++) {
            int target = sc.nextInt();
            int len = sc.nextInt();
            int[] arr = new int[len];
            for (int j = 0; j < len; j++)
                arr[j] = sc.nextInt();
 
            LinkedList<Integer> answer = bestSum2(target, arr);
            if (answer == null)
                System.out.println(-1);
            else {
                System.out.print(answer.size() + " ");
                System.out.print(answer.stream().map(Object::toString).collect(Collectors.joining(" ")));
                System.out.println();
            }
        }
    }
       //재귀함수가 어느 위치에 놓여있는지, 예를들면 if문안에 들어가 있는지 재귀를 반복문이 감싸고 있는지에 
       //따라 그 그림은 시시각각변한다. 뿐만 아니라 이번 코드를 통해 배운점은 재귀함수안에 어떤 문장이 있고
       //그것을 어떻게 사용하는지가 그림의 전개방식을 다르게 한다. 이 모두
    //가 재귀함수는 쉽게 그림이 그려지지 않아서 어렵게 느껴지는 것이다. 다른방법이 없다. 코드가 이러이러하게
    //구성되어있을때 그림이 어떻게 그려지고 전개되는지를 익숙히 하는 방법 밖에는
  
    public static LinkedList<Integer> bestSum2(int target, int[] arr) {
        LinkedList<Integer> min = null;//재귀함수 앞부분에 이렇게 있으면 이는 매 단계를 시작할때마다 min=null값을 갖게 된다. 
        if (target < 0)
            return null;
        if (target == 0)
            return new LinkedList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            LinkedList<Integer> cur = bestSum2(target - arr[i], arr);
            if (cur != null) {
            	//min=null인경우 ==>> 가장 밑바닥에 있을때 그리고 해당레벨에서 한번도 정답의 후보를 
                //가져본적이 없는 경우. min.size()>cur.size()인경우 ==>> 이미정답의 후보가 나왔지만 새로운 
    			//후보가 발견되는 경우
                if (min == null || min.size() > cur.size()) {
                    cur.add(arr[i]);
                    min = cur;
                }
            }
        }
        return min;
    }
 
}

명확한 이해를 위해(사실 이렇게 그림을 그려 머릿속에 남겨 놓는 과정이 제일 중요하다.) 내가 작성한 글과 그림을 남겨논다.

"min=매번 한단계 위로 올라갈때 마다 null로 된다. 이것이 바로 올라오면서 답을 구할수 있게 되는 핵심이다. 반면 min이 구해져있을때 다시 내려가서 새로운 리스트가 생성될 경우에는 그 min과 cur의 사이즈가 비교되는 것이다(min이 구해져있다는 것은 min이 null이 아니라는 것이므로).

하나로 쭈욱 내려가는 과정에서 min.size() > cur.size() 이 참인경우는 없다. 
min.size() > cur.size()이 고려되는 경우는 하나의 min이 결정된 후 그와 같은 레벨에서 다른 배열의 인덱스  트리를 타고 내려간(물론 이 내려가는 과정에서 min.size() > cur.size()이 쓰이는 일 역시 없다) 후 얻은 결과와 비교할때 쓰인다."

 

 

왜 전역변수를 쓰면 안되나? 에 대한 답을 명확히 알려주는 문제다. 이 문제 때문에 참고생도 많이 했다.  가장 중요한 점은 이것이다. 만약 전역변수를 쓴다면 그림에서 4부분이 끝나고min=[3]이 될것이다. 그리고 반복문에 의해 3쪽으로 재귀호출하면 min=null이라는 코드에 의해 min은 전역변수는 이므로 다시 null이 될것이다.

본 코드 내용의 일부내용

위 코드에서 target이 0이 되는 지점이 발견되어 null이 아닌 값이 반환되었을때. 그렇다면 cur!=null이고 min==null이므로 cur.add(something) 그후 min=cur 그 min은 어떤값을 담고 있게됨. 근데 여기서 반복문의 다음 인덱스를 타면 다시 한레벨 깊이 내려가야하는데 이때 min이 전역변수로 쓰인다면 그 이전에 뭔가를 담고 있던 그 min에 영향을 받게 되어 다시 쌩 null로 초기화 되는 것이다. 물론 지역변수를 써도 그냥 이름만 같은 min이라는 지역변수가null로 시작되는 것은 마찬가지다. 하지만 알다시피 이 함수에서의 min이 윗레벨 함수에서의 min이 아니다. 따라서 새로이 생성된 min이라는 지역변수에 상관없이 기존의 값은 영향을 받지 않게되는것이다.

 

2023.2.16

#23.2.26 내가 짠 코드
def bestSum(target, arr):
    min=None
    if(target<0):
        return None
    if(target==0):
        return list()
    for i in range(len(arr)):
        cur=bestSum(target-arr[i], arr)
        if cur !=None:
            if min==None or len(min)>len(cur):
                cur.append(arr[i])
                min=cur
    return min


n=int(input())
for i in range(n):
    target, number=map(int, input().split())
    arr=list(map(int, input().split()))
    answer=bestSum(target, arr)
    if answer==None:
        print(-1)
    else:
        print(len(answer), *answer)
        
        
        
        # 2023.02.15 Python으로.내려가면서 답을 구하는 지양해야 하는 코드
import sys
import copy
def bestSum(arr, target, length,collector):
    global answers
    if(target<0):
        collector.pop(-1)
        return 
    if(target==0):
        temp=copy.deepcopy(collector)
        answers.append(temp)
        if(len(collector)>0):
            collector.pop(-1)
        return 
    for i in range(length):
        collector.append(arr[i])
        bestSum(arr, target-arr[i], length,collector)
    if(len(collector)>0):
        collector.pop(-1)
    return 

n=int(input())
for i in range(n):
    target, number=map(int, input().split())
    arr=list(map(int, input().split()))
    length=len(arr)
    answers=[]
    bestSum(arr, target, length,[])
    le=len(answers)
    if le==0:
        print(-1)
    else:
        comp=sys.maxsize
        result=[]
        for i in range(le):
            if(len(answers[i])<comp):
                comp=len(answers[i])
                result=copy.deepcopy(answers[i])
        print(comp, *result)

 

 

import java.util.*;
public class Main{
    public static HashSet<Integer>hs=new HashSet<Integer>();
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        for (int i = 0; i < num; i++) {
            int len = sc.nextInt();
            int[] arr = new int[len];
            boolean[] visited=new boolean[len];
            int[]p=new int[3];
            for (int j = 0; j < len; j++)
                arr[j] = sc.nextInt();
             
            Arrays.sort(arr);
            ArrayList<Integer>list=new ArrayList<>();
             
            int count=0;
            list.add(arr[0]);
            for(int j=1;j<arr.length;j++) {
                if(arr[j-1]!=arr[j]) {
                    list.add(arr[j]);
                    count=0;
                }
                else {
                    count++;
                    if(count>=3)
                        continue;
                    else
                        list.add(arr[j]);
                }
            }
            Object[] arr2=list.toArray();
            solve(arr2,visited,p,0);
               if (hs.isEmpty()){
                    System.out.println();
                    System.out.println();
                }
                else {
                    Object[] answer=hs.toArray();
                    Arrays.sort(answer);
                    for(int k=0;k<answer.length;k++)
                        System.out.print(answer[k]+" ");
                }
                hs.clear();
            }
        }
    private static void solve(Object[] arr, boolean[] visited, int[]p, int depth) {
        if(depth==3) {
            int num=0;
            for(int i=0;i<3;i++) 
                num+=p[i]*Math.pow(10, 2-i);
            if((num/100!=0)&&(num%2==0))
                hs.add(num);
            return;
        }
        for(int i=0;i<arr.length;i++) {
            if(visited[i])
                continue;
            visited[i]=true;
            p[depth]=(Integer)arr[i];
            solve(arr, visited,p,depth+1);
            visited[i]=false;
        }
    }
}

 

교수코드와 내코드의 알고리즘은 같다. 다만 입출력 처리를 교수의 코드는 더 효율적으로 처리했다는 점. 그리고 나의 fancy하다는 점.

0이 될 때 까지 내려가고 리스트에 값을 채워 올라오는 구조. 만약 target이 0보다 작은 경우 null이 반환되어 코드구조상 그것은 버리게끔 되어 있다.

1.내코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Testing{
	LinkedList<Integer>list=new LinkedList<Integer>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int num=sc.nextInt();
		for(int i=0;i<num;i++) {
			int target=sc.nextInt();
			int n=sc.nextInt();
			int[]arr=new int[n];
			for(int j=0;j<n;j++)
				arr[j]=sc.nextInt();
			LinkedList<Integer>answer= howSum(target,arr);
			if(answer==null)
				System.out.println("-1");
			else {
				System.out.print(answer.size()+" ");
				Iterator<Integer>it=answer.iterator();
				while(it.hasNext()) {
					System.out.print(it.next()+" ");
				}
				System.out.println();
			}
		}		
	}
	public static LinkedList<Integer> howSum(int target, int[] arr) {
		if(target<0)return null;
		if(target==0)return new LinkedList<>();
		for(int i=0;i<arr.length;i++) {
			LinkedList<Integer>curr=howSum(target-arr[i],arr);
			if(curr!=null) {
				curr.add(arr[i]);
				return curr;
			}
		}
		return null;
	}
}

2.교수 코드