내일은 알고리즘

https://book.naver.com/bookdb/book_detail.naver?bid=7390287 

두 번째 챕터입니다.

사실 그동안 PS를 하면서 편하고 익숙한 방법대로 작성한 경우가 많았습니다.

Class를 생성하지 않고 Integer 배열의 순서에 값을 집어넣는다던지, 아무 의미 없이 flag, sum, num 같은 변수명을 사용한다던지...

시간 제약이 있고 나만 보는 PS에선 큰 상관이 없을지도 모르지만 다른 사람들에게도 내 코드를 보여주어야 하는 업무상황에선 참 좋지 않은 습관이고 고쳐야겠다는 생각이 이번 챕터를 읽으면서 더 명확해졌습니다.

의도를 분명히 밝혀라.

list = []

이 리스트는 무슨 의미일까요?

List<> list = new ArrayList<>();

Python이 아니라 Java를 쓰면 달라질까요?

반복문이나 함수에서 간단하게 쓰이고 사라지는 변수여도 그 의도와 목적을 이름으로 밝힌다면 누가 보더라도 프로그래머의 의도를 파악하기 쉬워질 것입니다.

그릇된 정보를 피하라.

저도 자주 쓰는 알파벳이 꼭 집어 지적되어 당황했습니다.

for(int l = 0; l < L; 1++){
	if(l % 2 == O){
    	I++;
    }
}

이 코드에서 반복문의 증감자는 소문자 l이 아니라 1이고 조건문의 우항은 숫자 0이 아니라 대문자 O이고 안의 연산은 소문자 l이 아니라 대문자 I입니다.

제가 써놓고도 구분하기가 힘듭니다. 

대부분의 오탈자는 IDE에서 붉은 줄로 지적을 해주겠지만 가끔은 코드의 문법적 논리는 틀리지 않는 경우가 있습니다.

l L i I o O 앞으로는 절대로 사용을 지양하겠습니다. 

의미있게 구분하라.

학생 N명의 언수외탐 네 가지 점수를 저장해야 하는 문제를 풀 때 어떻게 구현할까요?

가장 손쉬운건 int[][] grade = new int[N][4]; 따위의 2차원 배열을 만드는 것일 겁니다.

하지만 grade가 점수라는 건 알 수 있어도 각 원소의 첫 번째 값과 두 번째 값의 의미는 사라져 버립니다.

사전 지식 없이 grade[n][0]이 언어 점수이고 grade[n][1]이 수리 점수라는 걸 추측할 수 있는 사람은 없을 겁니다.

따로 객체를 만든다면 어떨까요?

public class Grade{
    int korean;
    int math;
    int english;
    int science;
    ...
    
    int getKorean(){
    	return this.korean;
    }
    ...
}

Grade[] grade = new Grade[N];

grade[n].korean 혹은 grade[n].getKorean()라는 코드를 본다면 못해도 90% 이상의 프로그래머는 언어 점수를 의미한다는 걸 알 수 있을 겁니다.

또 메소드명을 getKorean(), setKorean(), isKorean(), passKorean() 같은 식으로 일관성 있게 작성한다면 한 달, 1년이 지나도 코드를 다시 봤을 때 이해하기가 쉬울 겁니다.

검색하기 쉬운 이름을 사용하라.

IDE가 발전하면서 검색, 치환 같은 기능을 사용할 일이 무척 많습니다.

검색이 쉽다는 건 코드의 구조를 이해하기도 쉽다는 뜻이고, 검색이 쉽다는건 변수명이 바뀌거나 수정이 필요한 경우 찾아가기도 쉽다는 것입니다.

의미 있는 맥락을 추가하고 불필요한 맥락을 없애라.

RPG 게임을 만든다고 합시다.

이름은 코드킹의 전설 쯤이 좋겠네요. 영어로는 Legend of Codeking이 되겠습니다.

이제 이 게임 안에서 플레이어의 정보를 담은 객체를 만드려고 합니다.

코드킹의 전설 속 플레이어니까 LOC_Player로 작성했습니다.

만약 접두어 LOC_가 없다면 우리가 이 Player 객체가 어느 게임에서 쓰이는지를 모를까요?

게임이 여러 개 묶여있는 개발 형태라면 몰라도 당연한 맥락을 프로그래머의 손가락을 써가며 덧붙여 치는 건 낭비입니다.  

덧붙여서 IDE를 사용한다면 후자는 P만 눌러도 인텔리센스로 Player를 자동완성할 수 있겠지만, 전자는 L을 누른다면 LOC_Player, LOC_Item, LOC_Monster... 따위의 자동완성이 무분별하게 제공될 겁니다.

생산성을 위해서도 맥락은 꼭 필요한 것만! 

https://school.programmers.co.kr/learn/courses/30/lessons/81301

오늘 푼 다른 문제들과 비슷한 간단한 시뮬레이션 문제입니다.

앞에서부터 입력된 List를 쭉 읽어가면서 영어로 된 숫자가 나오면 변환하고 단어의 길이만큼 점프해 진행했습니다.

숫자가 나오면 바로 answer에 누적해주었습니다.

자릿수 문제는 앞에서부터 List를 읽어가기 때문에 새로운 숫자가 더해지기 전에 기존의 answer에 10을 곱하고 더하는 식으로 구현했습니다. 

List에 각 자릿수의 숫자를 하나씩 append하고 반복문이 끝난 후 마지막에 List를 숫자로 변환시켜도 같은 결과가 나옵니다.

def solution(s):
    answer = 0
    i = 0
    # numList = []
    while(i < len(s)):
        character = ord(s[i])
        num = 0
        if(48 <= character and character <= 57):
            num = int(s[i])
            i += 1
        else : 
            if(s[i] == 'z'): 
                num = 0
                i += 4
            elif(s[i] == 'o'):
                num = 1
                i += 3
            elif(s[i] == 'e'):
                num = 8
                i += 5
            elif(s[i] == 'n'):
                num = 9
                i += 4
            elif(s[i] == 't'):
                if(s[i+1] == 'w'):
                    num = 2
                    i += 3
                else : 
                    num = 3
                    i += 5
            elif(s[i] == 'f'):
                if(s[i+1] == 'o'):
                    num = 4
                    i += 4
                else : 
                    num = 5
                    i += 4
            else :
                if(s[i+1] == 'i'):
                    num = 6
                    i += 3
                else : 
                    num = 7
                    i += 5
        answer = answer * 10
        answer += num
        # numList.append(str(num))
    # print(numList)
    # numString = "".join(numList)
    # answer = int(numString)
    return answer

input = ["one4seveneight","23four5six7","2three45sixseven","123"]

for i in input:
    print(solution(i))

https://school.programmers.co.kr/learn/courses/30/lessons/72410

문자열이나 문자의 비교, 아스키코드를 알아야 쉽게 풀 수 있는 시뮬레이션 문제입니다.

입력된 문자열을 7단계를 거쳐 요구하는 조건에 맞는 문자열로 변형시켜야 하는데, 한 함수 안에서 동작해도 상관 없지만 구현시에 헷갈리지 않기 위해 7단계를 step 1~7로 쪼개어 각각 구현했습니다.

def solution(new_id):
    
    id = step1(new_id)
    id = step2(id)
    id = step3(id)
    id = step4(id)
    id = step5(id)
    id = step6(id)
    id = step7(id)

    answer = ""
    for i in id:
        answer += i
    return answer

def step1(id):
    result = []
    for i in id:
        character = ord(i)
        if(65 <= character and character <= 90):
            result.append(chr(character + 32))
        else:
            result.append(i)

    return result

def step2(id):
    result = []
    for i in id:
        character = ord(i)
        if((97 <= character and character <= 122) or (48 <= character and character <= 57) or character == 45 or character == 46 or character == 95):
            result.append(i)

    return result

def step3(id):
    result = []
    before = ''
    for i in id:
        if(before == '.' and i == '.'):
            continue
        else :
            result.append(i)
            before = i

    return result

def step4(id):
    if(len(id) > 0 and id[0] == '.'):
        id = id[1:]
    if(len(id) > 0 and id[-1] == '.'):
        id = id[0:-1]
    return id

def step5(id):
    if(len(id) == 0):
        return ['a']
    return id

def step6(id):
    if(len(id) > 15):
        id = id[0:15]
        if(len(id) > 0 and id[-1] == '.'):
            id = id[0:-1]
    return id

def step7(id):
    while(len(id) < 3):
        id.append(id[-1])
    return id


input = ["...!@BaT#*..y.abcdefghijklm","z-+.^.","=.=","123_.def","abcdefghijklmn.p"]
# input = ["...!@BaT#*..y.abcdefghijklm"]

for i in range(len(input)):
    print(solution(input[i]))

https://school.programmers.co.kr/learn/courses/30/lessons/67256

조금 머리를 써야하는 시뮬레이션 문제입니다.

왼손과 오른손의 엄지를 써서 누르는 방법이 정해진 번호 (1,4,7,*)과 (3,6,9,#)은 그대로 진행하면 되지만 중앙의 (2,5,8,0) 번호는 현재 상황에서 더 가까운 손가락을 사용해야 합니다.

저는 각 번호마다 해당 번호와의 거리를 미리 계산해놓고, 현재 손가락의 위치를 통해 거리를 비교하는 식으로 구현했습니다.

def solution(numbers, hand):
    distance = [[3,1,0,1,2,1,2,3,2,3,4,4],[2,2,1,2,1,0,1,2,1,2,3,3],[1,3,2,3,2,1,2,1,0,1,2,2],[0,4,3,4,3,2,3,2,1,2,1,1]]
    # 순서대로 2,5,8,0과 각 버튼(0~9,*,#)의 거리
    flag = (hand == "right")
    left = 10
    right = 11
    answer = ''

    for i in numbers :
        if(i == 1 or i == 4 or i == 7):
            left = i
            answer += 'L'
        elif(i == 3 or i == 6 or i == 9):
            right = i
            answer += 'R'
        else : 
            target = 0
            if(i == 5):
                target = 1
            if(i == 8):
                target = 2
            if(i == 0):
                target = 3
            
            if(distance[target][left] == distance[target][right]):
                if(flag) : 
                    right = i
                    answer += 'R'
                else : 
                    left = i
                    answer += 'L'
            elif(distance[target][left] < distance[target][right]):
                    left = i
                    answer += 'L'
            else : 
                    right = i
                    answer += 'R'
    return answer

numbers = [[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5],[7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2],[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]]
hand = ["right", "left", "right"]

for i in range(0,3):
    print(solution(numbers[i],hand[i]))

https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스 사이트가 리뉴얼 되었습니다.

전보다 훨씬 세련되고 보기 좋아졌습니다. 또 새로운 컨텐츠가 들어갈 페이지도 생긴것 같습니다.

파이썬을 오랜만에 쓸 겸 1 레벨 문제를 쭉 풀어봤습니다.

아주 간단한 시뮬레이션 문제입니다.

요구사항대로 입력을 탐색해서 인형을 고르고, 먼저 뽑힌 바구니의 인형과 비교해서 터트려주면 됩니다.

바구니의 구현은 Stack을 이용해도 될것 같지만 List로도 충분하고 더 간단할 것 같아서 List로 구현했습니다.

def solution(board, moves):
    answer = 0
    besket = []

    for i in moves:
        for j in range(0, len(board)):
            if(board[j][i-1] != 0):
                pick = board[j][i-1]
                # print(pick)
                board[j][i-1] = 0

                if(len(besket) > 0 and besket[-1] == pick):
                    besket = besket[0: -1]
                    answer += 2
                else : 
                    besket.append(pick)
                break
    return answer


board = [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]
moves = [1,5,3,5,1,2,1,4]
print(solution(board, moves))

https://book.naver.com/bookdb/book_detail.naver?bid=7390287 

클린 코드. 유명하고 프로그래머라면 정말 많이 추천받는 책입니다.

저도 아마 대학을 졸업했을 즈음 추천을 받아 구입했는데요.

사놓고 제대로 정독한 적이 없는 것 같아서 매일 1 챕터씩 정리하면서 읽어보려고 합니다.

너무 자세한 내용을 적으면 책의 저작권을 침해하니까요. 중요한 키워드와 Inspiration을 준 문구들을 위주로 제가 가진 경험과 함께 정리해보려고 합니다.

나쁜 코드가 쌓일수록 생산성은 떨어진다. 그러다가 마침내 0에 근접한다.

프로그래밍을 할때 자주 쓰는 말이 있습니다.

"이게 왜 되지?" 그리고 "이게 왜 안되지?"

간단히 생각하면 전자는 원하는 목표에 도착했다는 것이고 후자는 목적을 달성하는데 실패했다는 얘기입니다.

하지만 실제로 저런 상황을 맞이했을 때, 후자의 경우가 디버깅을 통해 문제를 찾기가 더 쉽습니다.

처음부터 접근을 잘못한게 아니라면 버그가 발생한 코드를 찾아 고칠 수 있습니다.

반면 전자는 당장은 코드가 돌아갈지 몰라도 예외 케이스에 걸리거나 이후 다른 문제가 발생했을 때 난감한 상태가 되는 일이 많았습니다.

블로그에 포스팅을 작성하면서 예전에 제가 썼던 코드를 보고 수정하는 일이 많은데 제가 쓴 코드이다보니 어지간하면 이해가 되지만 가끔 무슨 생각으로 짠 거지? 싶은 코드들이 있습니다. 

코드를 짠 장본인도 이해하지 못하는 코드를 동료, 상사, 고객들이 이해하길 바라는건 욕심이겠죠.

잘못은 전적으로 프로그래머에게 있다. 우리가 전문가 답지 못했다.

책의 부연설명을 조금 덧붙이면, 요구사항이나 기획이 아름답지 못할때 그것을 지적하고 고치는 것도 프로그래머의 일이라는 얘기였습니다.

저도 프로젝트를 진행할 때 기획이 여러번 엎어지거나 FE와 BE간에 명세서나 API 문서를 작성하면서 충돌했던 경험이 있습니다. 왜 그렇게 기능을 개발할 수 없는지, 왜 이런 방식으로 코드를 짜는지 설득하려면 내 코드가 그만큼 깔끔하고 정확해야 하겠죠.

논리가 간단해야 버그가 숨어들지 못한다.

PS를 할 때 많이 체감되는 문구입니다.

문제를 보고 떠오른 풀이방법대로 코드를 작성하는 경우가 억지로 예외사항과 조건을 좁혀가며 코드를 작성하는 경우보다 더 정확한 일이 많았습니다.

당연히 버그가 생겼을때 수정하기도 더욱 쉬웠습니다.

중복을 피하라. 한 기능을 수행하라. 제대로 표현해라. 작게 추상화해라.

클린 한 코드가 왜 필요한지, 왜 써야 하는지 동기를 부여하는 1장이었습니다.

다음 2장은 코드에서 "이름"을 잘 사용하는 방법에 대한 내용이 진행됩니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo 

시뮬레이션의 정수를 담은 문제입니다.

주어진 문제의 조건과 순서를 따라 잘 구현하면 되지만 잘 구현하는것이 어렵습니다.

코드의 가독성을 높이기 위해 여러 단계를 나누어 함수로 구현하고

실행 시간을 줄이기 위해 재귀함수를 이용해서 이전 상태를 기억해 거기서부터 다시 탐색합니다.

상태를 기억할때는 Map이 2차원 배열임을 감안해 깊은 복사를 위해 copy() 함수를 따로 만들었습니다.

Java언어에서 N차원 배열로 모든 배열을 순회하며 복사해도 되지만 clone() 메소드가 Array에 존재해 활용했습니다.

모든 경우를 탐색해야하기 때문에 효율적인 코드를 짜는게 중요할 것 같습니다.

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

public class q5656_SWEA_벽돌깨기 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int answer, N, W, H;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] map;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			answer = Integer.MAX_VALUE;
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());

			map = new int[H][W];
			for (int h = 0; h < H; h++) {
				st = new StringTokenizer(br.readLine());
				for (int w = 0; w < W; w++) {
					map[h][w] = Integer.parseInt(st.nextToken());
				}
			}

			dfs(0);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void dfs(int count) {
		if (count == N) {
			answer = Math.min(answer, countBlock(map));
			return;
		}
		int[][] save = new int[H][W];
		for (int w = 0; w < W; w++) {		
			copy(map, save);				
			shoot(w);
			dfs(count + 1);
			copy(save, map);

		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < H && 0 <= y && y < W) {
			return true;
		}

		return false;
	}

	static void copy(int[][] from, int[][] to) {
		for (int h = 0; h < H; h++) {
			to[h] = from[h].clone(); 
		}
	}

	static int countBlock(int[][] result) {
		int count = 0;
		for (int h = 0; h < H; h++) {
			for (int w = 0; w < W; w++) {
				if (result[h][w] != 0) {
					count++;
				}
			}
		}
		return count;
	}

	static void shoot(int w) {			
		for (int h = 0; h < H; h++) {	
			if (map[h][w] != 0) {		
				boom(h, w);
				return;
			}
		}
		return;
	}

	static void boom(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { x, y, map[x][y]-1 });
		map[x][y] = 0;

		while (!queue.isEmpty()) {
			int[] now = queue.poll();
			int range = now[2];

			for (int i = 0; i < 4; i++) {
				int nX = now[0];
				int nY = now[1];
				for (int r = 0; r < range; r++) {
					nX += delta[i][0];
					nY += delta[i][1];
					if (isIn(nX, nY) && map[nX][nY] != 0) {
						queue.offer(new int[] { nX, nY, map[nX][nY]-1 });
						map[nX][nY] = 0;
					}
				}
			}
		}

		gravity();
	}

	static void gravity() {
		Queue<Integer> queue;

		for (int w = 0; w < W; ++w) {   
			queue = new LinkedList<>();	

			for (int h = H - 1; h >= 0; --h) {
				if (map[h][w] > 0) {
					queue.offer(map[h][w]);
				}
			}

			for (int h = H - 1; h >= 0; --h) {
				if (!queue.isEmpty()) {
					map[h][w] = queue.poll();
				} else {
					map[h][w] = 0;
				}
			}
		}

	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWRuoqCKkE0DFAXt 

넓은 범위의 소수를 모두 구하는 '에라토스테네스의 채'를 응용한 문제입니다.

에라토스테네스의 채를 구현하는 방법을 알면 큰 어려움 없이 풀이할 수 있습니다.

이번 문제처럼 여러번 소수를 사용하는 문제에서도 필요한 범위의 소수를 미리 구해놓고 정답체크를 진행하면 매번 새로 소수를 구하는 것보다 좋은 성능을 얻을 수 있습니다. 

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

public class q4698Re_SWEA_테네스의특별한소수 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		int[] arr = new int[1_000_001];

		arr[1] = 1;

		for (int i = 2; i <= 1_000_000; i++) {
			if (arr[i] == 0) {
				for (int j = i * 2; j <= 1_000_000; j += i) {
					arr[j] = 1;
				}
			}
		}

		for (int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			int D = Integer.parseInt(st.nextToken());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int cnt = 0;

			for (int i = A; i <= B; i++) {
				if (arr[i] == 0) {
					if (String.valueOf(i).contains(String.valueOf(D))) {
						cnt++;
					}
				}
			}

			sb.append("#").append(t).append(" ").append(cnt).append("\n");
		}

		System.out.println(sb);
	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw 

주어진 조건에 맞게 양팔저울에 추를 올리는 경우의 수를 구하는 문제입니다.

Java의 경우에는 모든 경우에 대해 순열을 구하고 그 순열이 조건에 적합한지 검증을 하면서 가지치기를 해도 주어진 실행시간 안에 통과가 되지만, 조금 더 효율적으로 코드를 짤 수 있는 방법들이 있어 3가지를 전부 소개해드리겠습니다.

우선 기본적으로 모든 순열을 만들고, 이후 조건에 맞는 경우를 찾는 코드입니다.

시간 초과를 방지하기 위해 좌측의 무게가 절반을 넘어서는 경우 이후의 경우는 검증하지 않고 2^(N-현재 단계)만큼 더해주었습니다.

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

public class q3234_SWEA_준환이의양팔저울 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, answer, total;
	static Integer[] gram;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			answer = 0;
			total = 0;
			gram = new Integer[N];

			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				gram[n] = Integer.parseInt(st.nextToken());
				total += gram[n];
			}
			total /= 2;

			makePermutation(0, new int[N], new boolean[N]);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void makePermutation(int count, int[] choosed, boolean[] visited) {
		if (count == N) {
			check(1, choosed, choosed[0], 0);
			return;
		}
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				choosed[count] = gram[i];
				makePermutation(count + 1, choosed, visited);
				visited[i] = false;
			}
		}
	}

	static void check(int count, int[] choosed, int left, int right) {
		if (count == N) {
			answer++;
			return;
		}
		if (total < left) {
			int num = 1;
			for (int i = 0; i < N - count; i++) {
				num *= 2;
			}
			answer += num;
			return;
		}

		if (left >= right + choosed[count]) {

			check(count + 1, choosed, left, right + choosed[count]);
		}
		check(count + 1, choosed, left + choosed[count], right);

	}
}

두 번째론 모든 순열을 만들지 않고, 순열을 만드는 과정 안에 조건에 따른 검증을 넣어서 가지치기한 코드입니다.

마찬가지로 시간 초과를 방지하기 위해 좌측의 무게가 절반을 넘어서는 경우 이후의 경우는 검증하지 않고, (N-현재 단계)! * 2^(N-현재 단계)만큼 더해주었습니다.

순열이 다 만들어지지 않았기 때문에 경우의 수를 계산할 때 남은 추의 개수 팩토리얼까지 곱해주어야 합니다.

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

public class q3234_SWEA_준환이의양팔저울Re {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, answer, total;
	static Integer[] gram;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			answer = 0;
			total = 0;
			gram = new Integer[N];

			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				gram[n] = Integer.parseInt(st.nextToken());
				total += gram[n];
			}
			total /= 2;

			makePermutation(0, new boolean[N], 0, 0);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void makePermutation(int count, boolean[] visited, int left, int right) {
		// System.out.println(count + "선택됨," + left + " : " + right);

		if (count == N) {
			answer++;
			return;
		}

		if (total < left) {
			int num = 1;
			for (int i = 1; i <= N - count; i++) {
				num *= 2;
				num *= i;
			}
			answer += num;
			return;
		}

		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				makePermutation(count + 1, visited, left + gram[i], right);
				if (right + gram[i] <= left) {
					makePermutation(count + 1, visited, left, right + gram[i]);
				}
				visited[i] = false;
			}
		}
	}
}

세 번째로 메모이제이션을 활용해서 이미 탐색한 경우를 스킵한 코드입니다.

어떤 방법으로든 추의 위치 배정이 똑같은 시점이 오면 이후의 경우의 수의 개수는 같아집니다.

예를 들어 1,2,8,... 의 무게를 가진 추가 주어졌을때, 8(좌) → 1(우) → 2(우) 경우나 8(좌) → 2(우) → 1(우) 경우나 추의 현재 상태는 같습니다.

추의 상태가 같으면 이후 가능한 경우의 수도 같아집니다.

추의 상태를 사용한 추 (갯수가 작기 때문에 비트 마스킹으로 기록), 좌측에 놓인 무게로 저장하고 이전에 탐색한 적이 있다면 더 탐색을 하지 않고 그 값을 사용하는 코드입니다.

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

public class q3234_SWEA_준환이의양팔저울Re2 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, total;
	static int[] gram;
	static int[][] memo;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			total = 0;
			gram = new int[N];

			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				gram[n] = Integer.parseInt(st.nextToken());
				total += gram[n];
			}

			memo = new int[total + 1][1 << N];

			sb.append("#").append(tc).append(" ").append(makePermutation(0, 0, 0, 0)).append("\n");
		}

		System.out.println(sb);
	}

	static int makePermutation(int count, int bitmask, int left, int right) {
		if (count == N) {
			return 1;
		}

		int sum = memo[left][bitmask];

		if (sum == 0) {
			for (int i = 0; i < N; i++) {
				if ((bitmask & (1 << i)) == 0) {
					sum += makePermutation(count + 1, bitmask | (1 << i), left + gram[i], right);
					if (right + gram[i] <= left) {
						sum += makePermutation(count + 1, bitmask | (1 << i), left, right + gram[i]);
					}
				}
			}
			return memo[left][bitmask] = sum;
		}
		return sum;
	}
}

위에서부터 순서대로 메모이제이션 → 순열구하면서 가지치기 → 순열 구하고 가지치기 코드의 실행결과입니다.

여러가지로 생각할 거리가 많은 좋은 문제였습니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqUzj0arpkDFARG 

문제 자체는 기본적인 DFS 백트래킹을 사용해서 풀 수 있는 문제입니다.

하지만 가지치기에 따라 실행시간이 큰 차이를 보였습니다.

생각해보면 문제에서 주어진 테스트케이스의 조건에서, R과 C의 크기가 1 이상 20 이하입니다.

즉 최대 400칸의 맵이 주어지는 건데 알파벳의 개수는 26개로 제한되어있기 때문에 가지치기를 통해 자르지 않는 경우 생각보다 훨씬 더 많은 추가 탐색이 실행될 걸 알 수 있습니다.

가지치기의 아이디어는 간단합니다.

가능한 최대값을 이미 정답으로 가지고 있는 경우, answer = 26인 경우 더이상의 탐색을 하지않고 재귀를 끝내면 됩니다.

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

public class q7699_SWEA_수지의수지맞는여행 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int R, C, answer;
	static int[][] map;
	static boolean[] visit;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			answer = 0;
			st = new StringTokenizer(br.readLine());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());

			map = new int[R][C];
			visit = new boolean[26];

			for (int r = 0; r < R; r++) {
				String input = br.readLine();
				for (int c = 0; c < C; c++) {
					map[r][c] = input.charAt(c) - 'A';
				}
			}
			visit[map[0][0]] = true;
			dfs(0, 0, 1);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void dfs(int x, int y, int count) {
		if (answer == 26) {
			return;
		}
		answer = Math.max(answer, count);

		for (int i = 0; i < 4; i++) {
			int nX = x + delta[i][0];
			int nY = y + delta[i][1];

			if (isIn(nX, nY)) {
				if (!visit[map[nX][nY]]) {
					visit[map[nX][nY]] = true;
					dfs(nX, nY, count + 1);
					visit[map[nX][nY]] = false;
				}
			}
		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < R && 0 <= y && y < C) {
			return true;
		}
		return false;
	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWyNQrCahHcDFAVP 

8458. 원점으로 집합과 비슷한 문제입니다.

상하좌우로 N칸을 움직여서 원하는 목적지로 가면 되지만 (상,하)와 (좌,우)를 연속으로 움직일 수 없고 번갈아가면서 움직여야합니다.

8458번과 비슷한 방식으로 접근할 수 있습니다.

내 위치와 목적지의 X좌표, Y좌표의 거리(절댓값)가 홀짝이 같은지에 따라 정답이 나뉩니다.

예를들어 내 위치가 (0,0)이고 목적지가 (2,4)처럼 X Y좌표 모두 짝수거리만큼 떨어져있다면,

상우상우로움직여 (2,2)위치로 이동하고,상 두번을 움직이기 위해 상 좌 상 우 이런식으로 좌우 움직임을 상쇄해서 도착하면 됩니다.

홀수의 경우에도 더 작은 거리를 0으로 만들만큼 움직이면, 남은 짝수 거리를 같은 방법으로 상쇄하여 도착합니다.

즉, X Y 거리가 모두 짝수거나 모두 홀수면 (둘 중 더 먼 거리 * 2배) 만큼 움직여서 목적지에 도착할 수 있습니다.

둘의 홀짝이 다르면 어떨까요?

내 위치가 (0,0)이고 목적지가 (2,3)이라면

상우상우로 움직여 (2,2)에 도착하고 바로 상으로 움직여 5번만에 목적지에 도착할 수 있습니다.

(우상우상으로 움직이면 도착을 못합니다)

이때는 (둘 중 더 먼 거리 * 2배) - 1 만큼 움직여서 목적지에 도착할 수 있습니다.

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

public class q8382_SWEA_방향전환 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		int answer;

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			int aX = Integer.parseInt(st.nextToken());
			int aY = Integer.parseInt(st.nextToken());
			int bX = Integer.parseInt(st.nextToken());
			int bY = Integer.parseInt(st.nextToken());
			int x = Math.abs(aX - bX);
			int y = Math.abs(aY - bY);

			answer = Math.abs(x - y) % 2 == 0 ? 2 * Math.max(x, y) : 2 * Math.max(x, y) - 1;

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWzaq5KKk_ADFAVU 

(문제에서 주어진 조건설명이 살짝 부족한 문제여서 혼동의 여지가 많습니다.)

원점에서 각기 다른 거리만큼 떨어져 있는 점들은 1... N칸씩 움직여서 모두가 원점에 도착하게 하는 게 목표입니다.

이때 N칸은 상하좌우 어느 방향으로든 나누어 움직일 수 있습니다.

(N이 3칸일때 상상좌 상하상 이런 식으로 움직일 수 있습니다. 단, 자기 자리에서 움직이지 않는 건 안됩니다.)

가만히 생각해보면 원점에 먼저 도착한 점들은 원점에서 진동하듯 좌우로 움직이기만해도 된다는 걸 알 수 있습니다.

예를 들어서, N=3일때 원점에 도착한 점 A는 다음 N=4의 움직임에서 좌우좌우로 움직이면 그대로 원점입니다.

다만 이후 N=5일때 움직이면 어떻게 움직이던지 원점에서 한 칸 이상 나가게 됩니다.

여기서 아이디어를 얻어 우리는 홀짝을 이용해 점들이 원점에 모두 모일 수 있는지 없는지를 알 수 있습니다.

원점으로부터의 거리가 모두 홀수거나 모두 짝수면 어떤 N일 때 확실하게 원점으로 모일 수 있으나, 거리가 홀수와 짝수가 섞여 있다면 어떤 방법으로도 동시에 원점에 멈추는 게 불가능합니다.

점 A가 원점에서 한 칸, B가 두 칸 떨어진 테스트케이스가 있다고 해봅시다.

처음 N=1일때 점 A는 원점으로 들어갑니다. 점 B는 원점으로 향하지만 한 칸 떨어진 위치에 멈춥니다.

다음 N=2일때 점 A는 좌우로 움직여 그대로 원점에 남습니다. 점 B는 원점을 지나 다시 한 칸 떨어집니다.

N=3일땐 반대로 점 B가 원점에 들어가고 좌우로 움직여 원점에 남습니다. 하지만 점 A가 원점에서 나가게 됩니다.

어떤 방법으로도 점 A와 B가 둘 다 원점에 들어가게 할 수 없습니다.

이렇게 해결할 수 없는 경우를 걸러내고, 이제 몇 칸을 움직여야 원점에 들어갈 수 있는지를 계산해봅시다.

위에서 말했다시피 원점에 먼저 도착한 점들은 원점에서 왕복운동을 하면서 대기하면 됩니다.

즉 우리는 원점에서 가장 멀리있는 점만 생각하면 됩니다. 

가장 멀리있는 점이 원점으로 도착했을때도 분기가 나뉩니다.

예를들어 가장 멀리있던 점이 8칸 떨어져 있었다고 생각해봅시다.

N=1, N=2, N=3을 지나며 다른 점들은 원점에 도달해 왕복운동을 하며 대기합니다.

N=4일때 가장 멀리있던 점이 원점에 도착합니다. 하지만 두번의 움직임이 남습니다.

이 남은 움직임이 짝수라면, 먼저 도착한 점들과 같이 왕복운동을 해 소모하면 됩니다.

홀수라면, 다음 기회를 노려야합니다. 즉, 다시 한 번 홀수번 움직여 원점에 맞춰야합니다.

정리하면 

1. 점들이 모두 홀수거나 모두 짝수여야 원점에 모이는게 가능하다.

2. 가장 먼 점에서부터 N을 늘려가며 거리를 줄인다.

3. 가장 먼 점이 원점에 도착했을때, 남은 횟수가 짝수라면 바로 종료, 홀수라면 홀수번 움직여야 종료된다.

(원점에 도착했을때의 움직임이 짝수였다면 다음 홀수번으로, 원점에 도착했을때의 움직임이 홀수였다면 짝수,홀수번 2번의 움직임을 더 해야 종료할 수 있습니다.)

설명도 조금 미흡했고 이해하기도 어려웠던 원점으로집함 문제였습니다. 감사합니다.

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

public class q8458_SWEA_원점으로집합 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			int answer = 0;
			boolean flag = false;
			int N = Integer.parseInt(br.readLine());

			st = new StringTokenizer(br.readLine());
			long X = Integer.parseInt(st.nextToken());
			long Y = Integer.parseInt(st.nextToken());
			long odd = (Math.abs(X) + Math.abs(Y)) % 2;
			long gap = Math.max(0, Math.abs(X) + Math.abs(Y));

			for (int n = 1; n < N; n++) {
				st = new StringTokenizer(br.readLine());
				X = Integer.parseInt(st.nextToken());
				Y = Integer.parseInt(st.nextToken());

				if ((Math.abs(X) + Math.abs(Y)) % 2 != odd) {
					flag = true;
				}

				gap = Math.max(gap, Math.abs(X) + Math.abs(Y));
			}

			if (flag) {
				sb.append("#").append(tc).append(" -1").append("\n");
			} else {

				while (gap > 0) {
					answer++;
					gap -= answer;
				}
				answer = gap % 2 == 0 ? answer : (answer % 2 == 0 ? answer + 1 : answer + 2);

				sb.append("#").append(tc).append(" ").append(answer).append("\n");
			}
		}

		System.out.println(sb);
	}
}