내일은 알고리즘

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

나쁜 코드에 주석을 달지 마라.
주석은 나쁜 코드를 보완하지 못한다.
코드를 새로 짜라.

배배꼬인 스파게티 코드를 작성하고 주석으로 설명을 빙자한 변명을 단 경험이 많이 있을겁니다.

코드는 명확한 결과(성공하거나 에러를 띄우거나)를 알려주지만 주석은 아닙니다.

/* 완벽하게 잘 동작하는 코드 */ 라는 주석이 달려있다고 해서 그 코드가 정말 잘 동작할거란 보장은 없습니다.

오히려 주석을 달면서 생기는 실수로 인해 다른 프로그래머에게 오정보를 줄 수도 있습니다.

IDE는 코드의 문법상 에러는 찾아내지만 주석의 에러를 찾아내지는 못하니까요.

주석이 아니라 코드로 의도를 표현하라.

int[][] list = new int[N][3];

...

/* 직원중 1억 이상 고연봉자의 수를 세는 함수 */
for(int i = 0; i < list.length; i++){
	if(list[i][2] > 100_000_000){
    	count++;
    }
}

주석을 가리고 본다면 어떤 동작이 이루어지는지 파악하기 참 힘든 코드일겁니다.

1억이란 숫자는 무엇을 의미하는지, list 배열은 무슨 의미인지 알 수가 없습니다. 

Employee[] employeeList = new employeeList[N];
static int highSalary = 10_000_000;

...

for(int i = 0; i < employeeList.length; i++){
	if(employeeList[i].salary > highSalary){
    	count++;
    }
}

주석이 없지만 for문이 무슨 동작을 하는지 알수 있는 코드입니다.

적절한 이름을 통해 주석 없이도 코드를 설명할 수 있습니다.

필요한 주석

1. 법적 권리, 저작권 라이센스 등 코드 외적인 내용을 알려주는 주석
   코드로는 설명 할 수 없는 내용을 코드 안에 표현하려면 주석밖엔 없겠죠.
   
   
2. 경고의 의미를 담은 주석
   /*이 함수는 완료까지 8시간이 걸림*/
   /*이 작업은 주요 데이터를 삭제함*/
3. TODO 주석
   /*어쩌구저쩌구한 기능을 구현할 곳*/

책에서는 좋지 않은 나쁜 주석도 알려주는데요.

너무 종류가 많아서 그냥 꼭 필요한걸 제외한 모든 주석이라고 생각하셔도 될 것 같습니다.

ㅋㅋㅋ

오랜만에 다시 쓰는 알고리즘 글입니다.

오늘은 부분집합을 만드는 법에 대해 알아보겠습니다.

제가 수학 전공은 아니기 때문에 집합, 부분집합에 관한 기본적인 수학적 지식은 넘기고 설명을 하겠습니다.

부분집합은 어떤 집합에 속한 원소들로만 이루어진 집합입니다.

멱집합은 어떤 집합에서 만들 수 있는 모든 부분집합들을 모은 집합입니다.

보통 부분집합을 응용하는 PS는 이런 멱집합을 구하고 풀이하는 경우가 많습니다.

N개의 원소를 가진 집합의 부분집합의 개수는 2^N개입니다.

부분집합을 만들 때 집합의 어떤 원소를 넣던가 넣지 않던가 두 가지 선택이 가능하고 이런 원소가 N개 있으므로 2^N개의 부분집합이 생기는 것도 당연할 겁니다.

멱집합을 만드는 코드도 이 아이디어를 이용해서 진행합니다.

1~6까지의 숫자를 가진 집합이 있다고 생각해 봅시다.

이 집합의 부분집합으로 하나의 원소를 가진 부분집합 {1}, 여러 원소를 가진 부분집합 {1,2,3}, 공집합 { }, 집합 전체와 같은  {1,2,3,4,5,6}등 여러 종류가 있을 겁니다.

위에서 얻은 아이디어대로 하나의 원소를 넣고 빼는 두 가지 경우를 체크하며 부분집합을 만들어 봅시다.

6개의 원소가 있는 집합이지만 첫 번째 원소 1만 가졌다고 생각해 봅시다.

이 집합의 부분집합은 1이 들어있거나 안 들어있는 두 가지 경우로 나뉩니다.

이 두가지 경우에 대해 우리는 {1}과 { }라는 두 개의 부분집합을 만들 수 있습니다.

두 번째 원소 2를 더해 생각해볼까요?

1과 2 두 개의 원소를 가진 집합의 부분집합은 앞에서 구한 부분집합들에 2가 들어가거나 안 들어가는 두 가지 경우로 생각할 수 있습니다.

즉 우리는 {1,2} {1}, {2}, { }라는 4개의 부분집합을 얻을 수 있습니다.

집합의 원소가 늘어날 때마다 부분집합의 개수는 2배로 늘어나는 것이죠.

3을 포함시켜 {1,2,3}이라는 집합의 부분집합을 구해본다면 앞에서 구한 {1,2} {1}, {2}, { } 4개의 부분집합에 3이 들어가거나 안 들어가는 두 가지 경우로 {1,2,3} {1,3}, {2,3}, {3}, {1,2} {1}, {2}, { } 8개의 부분집합을 만들 수 있을 겁니다.

이렇게 구한 모든 부분집합의 집합을 멱집합이라고 부릅니다.

이 진행과정을 Java와 Python 두 개로 구현해 보았습니다.

부분집합, 조합, 순열 등의 개념을 응용하는 문제는 무척 많기 때문에 익숙해지시면 유용하게 쓰실 수 있습니다.

Java

public class algo_01_subset {
	static int[] number = {1,2,3,4,5,6};
	static int size = 6;
	public static void main(String[] args) {
		makeSubset(0, new boolean[size]);
	}
	
	public static void makeSubset(int idx, boolean[] used) {
		if(idx == size) {
			printSubset(used);
			return;
		}
		
		used[idx] = false;
		makeSubset(idx+1, used);
		used[idx] = true;
		makeSubset(idx+1, used);
	}
	
	public static void printSubset(boolean[] used) {
		StringBuilder sb = new StringBuilder();
		sb.append("{ ");
		for(int i = 0; i < size; i++) {
			if(used[i]) {
				sb.append(number[i]).append(" ");
			}
		}
		sb.append("}");
		
		System.out.println(sb.toString());
	}
}

Python

def makeSubset(idx, used):
    global size
    if(idx == size):
        printSubset(used)
        return
    
    used[idx] = False
    makeSubset(idx+1, used)
    used[idx] = True
    makeSubset(idx+1, used)

def printSubset(used):
    global size
    global number
    msg = "{ "
    for i in range(0,size):
        if(used[i]):
            msg += str(number[i])
            msg += " "
    msg += "}"
    print(msg)

number = [1,2,3,4,5,6]
size = 6

makeSubset(0, [False]*size)

3NF(Third Normal Form) 정규형

3NF 정규형을 만족하려면 릴레이션 내의 이행적 함수 종속을 제거해야 합니다.

이행적 함수 종속은 이전에 설명했듯 (X→Y) 종속관계이고 (Y→Z) 종속관계일때 (X→Z)도 성립하는 경우를 말합니다.

예를 들어 어떤 전자회사의 인적자원을 위와 같은 릴레이션으로 관리할 때, 사원번호를 알면 소속팀을 알 수 있습니다.

그런데 소속부서는 소속 팀을 통해서 알 수 있어 이행적 함수 종속이 발생합니다.

또 이런 이행적 종속으로 인해 이상현상이 발생하게 됩니다.

해결방법은 앞의 다른 정규형들처럼 테이블을 나눠 이행적 종속관계를 없애면 됩니다.

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

참가자와 완주자 사이에 맞지 않는 한 명을 찾는 문제입니다.

HashMap (파이썬의 Dictionary)자료구조를 사용해 풀이했습니다.

문제를 처음 보면 참가자들을 저장하고, 완주자들을 제외 한 뒤 남은 한 명을 구하는 식으로 구현해야할것 같습니다.

하지만 가만히 생각해보면 완주자들을 저장한 뒤 참가자들을 순회하면서 완주자 목록에 없는 사람을 찾는 역순으로 구현하는게 더 간단합니다. 

완주자들의 이름을 key로 Dictionary에 넣어 존재하지 않는다면 value를 1로 저장하고 동명이인이 있다면 value+1로 갱신해줍니다.

이후 참가자들의 이름을 완주자를 저장한 Dictionary에서 확인하면서 하나씩 지워주다가 존재하지 않는 이름이나 완주 목록이 이미 0이 된 이름이 나오면 그 참가자가 우리가 찾는 답이 됩니다.

def solution(participant, completion):
    map = {}

    for i in completion :
        if(i in map):
            map[i] = map.get(i) + 1
        else : 
            map[i] = 1

    for i in participant:
        if(i in map and map[i] > 0):
            map[i] = map.get(i) - 1
        else : 
            return i


participant = [["leo", "kiki", "eden"], ["marina", "josipa", "nikola", "vinko", "filipa"], ["mislav", "stanko", "mislav", "ana"]]
completion = [["eden", "kiki"], ["josipa", "filipa", "marina", "nikola"], ["stanko", "ana", "mislav"]]

for i in range(0,3):
    print(solution(participant[i], completion[i]))

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

특정 범위의 소수를 구하는 에라토스테네스의 채와 조합을 응용하는 문제입니다.

우선 세가지 수를 뽑아 나올수 있는 합의 범위는 3000입니다.

매번 합을 구해 소수인지 판별하는것 보다 미리 소수를 구해놓고 비교하는게 더 빠릅니다. 특정 범위안의 모든 소수를 구하는 방법으론 에라토스테네스의 채가 있습니다. 이를 활용해서 3000이하의 모든 수에 관해 소수 여부를 미리 구해놓습니다.

다음으론 더할 세가지 수를 뽑습니다. 순서와 상관없이 합을 구하기 때문에 조합을 응용해 구하면 됩니다.

이번 경우에는 뽑아야할 수가 3개로 정해져 있으므로 3중 for문을 사용해도 구현이 가능합니다.

import copy

def solution(nums):

    def sumCombination(combination):
        return combination[0] + combination[1] + combination[2]

    def makeCombination(list, idx, count):
        if(count == 3):
            combinationList.append(copy.deepcopy(list))
            return
        
        for i in range(idx,len(nums)):
            list[count] = nums[i]
            makeCombination(list, i+1, count+1)


    def makePrimeNumber():
        number = [0 for i in range(3_001)]
        number[1] = 1
        for i in range(2,3_001):
            if(number[i] == 0):
                j = i * 2
                while(j < 3_001):
                    number[j] = 1
                    j += i
        return number

    combinationList = []
    primeNumber = makePrimeNumber()
    makeCombination([0]*3, 0, 0)
    answer = 0
    for i in combinationList:
        sum = sumCombination(i)
        if(primeNumber[sum] == 0):
            answer += 1
            
    return answer


nums = [1,2,7,6,4]
print(solution(nums))

def solution(nums):

    def makePrimeNumber():
        number = [0 for i in range(3_001)]
        number[1] = 1
        for i in range(2, 3_001):
            if(number[i] == 0):
                j = i * 2
                while(j < 3_001):
                    number[j] = 1
                    j += i
        return number

    primeNumber = makePrimeNumber()
    answer = 0

    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            for k in range(j+1, len(nums)):
                sum = nums[i] + nums[j] + nums[k]
                if(primeNumber[sum] == 0):
                    answer += 1
            
    return answer


nums = [1,2,7,6,4]
print(solution(nums))

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

어제 예비군을 참가해서 하루 휴식(?)했습니다.

비가 온 다음날이라 습하고 덥고 난리도 아니었네요.

세번째 챕터는 함수입니다.

작게 만들어라.
함수는 한 가지를 해야 한다. 그 한 가지를 잘 해야 한다. 그 한 가지만을 해야 한다.

PS에서 Solution 함수를 작성할 때 우리는 항상 유혹에 부딪힙니다.

이 코드정도는 그냥 따로 빼지 않아도 되지 않을까? 

생각해 보면 제가 PS에서 함수를 쪼개는 경우는 isIn() isTrue()와 같은 조건문을 빼거나 복잡한 시뮬레이션 문제를 쪼갤때 정도였습니다. 간단한 문제라면 함수의 분리가 없어도 되겠지만 구현해야되는 코드의 수준이 복잡해질수록 함수를 쪼개는 일이 중요한걸 느끼게 됩니다.

함수 안의 추상화 수준을 같게 하라. 위에서 아래로 내려가라.

어떤 함수에서 넘겨받은 인자의 홀수/짝수 그리고 음수/양수를 판독한다고 생각해 봅시다.

간단한 조건문으로도 작성할 수 있을겁니다.

if(num % 2 == 0){
	...
}

if(num > 0){
	...
}

조건부분을 함수로 따로 분리하면 어떨까요.

이것도 보기에 나쁘지 않습니다.

if(isEven(num)){
	...
}
if(isPositive(num)){
	...
}

그럼 이런 코드는 어떨까요?

if(num % 2 == 0){
	...
}
if(isPositive(num)){
	...
}

위의 코드에선 내용이 간단하다보니 이해에 문제는 없지만, 조금 더 복잡하고 난해한 코드에선 이런 일관성을 해치는 코드가 큰 오해를 만들 수도 있습니다.

예상할 수 없는 결과를 일으키지 마라.
명령과 조회를 분리하라.

위에서 사용했던 isPositive() 함수를 생각해 봅시다.

다른 사람이 짠 해당 코드를 발견했고, 마침 양수를 구분해야할 필요가 있던 저는 제 개발파트에 해당 함수를 가져다 썼습니다. 그런데 알고보니 isPositive() 안이 이런코드로 구현되었다면요?

public boolean isPositive(int num){
    if(num > 0){
        answer ++;
        return true;
    }
    return false;
}

isPositive()가 호출되고 받은 인자를 양수로 판독할때마다 어딘가의 static한 변수 answer를 늘려주고 있었다면, 단순히 양수를 판독하려던 저는 프로그램을 망가트리는 치명적인 버그를 만들 수도 있습니다.

지키고 있던 내용도 있고, 알면서 지키지 않았던 내용도 많은 제 코드를 회고해보게 만드는 챕터였습니다.

감사합니다.

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

https://nodingco.tistory.com/77

Java코드와 풀이 접근방법은 위쪽 포스팅에서 확인해주세요.

class Operation:
    def __init__(self, plus, minus, multiple, divide):
        self._plus = plus
        self._minus = minus
        self._multiple = multiple
        self._divide = divide

def dfs(value, count, operation):
    global minValue
    global maxValue

    if(count == N):
        minValue = min(minValue, value)
        maxValue = max(maxValue, value)
        return
    
    if(operation._plus > 0):
        operation._plus -= 1
        dfs(value + number[count], count+1, operation)
        operation._plus += 1
    if(operation._minus > 0):
        operation._minus -= 1
        dfs(value - number[count], count+1, operation)
        operation._minus += 1
    if(operation._multiple > 0):
        operation._multiple -= 1
        dfs(value * number[count], count+1, operation)
        operation._multiple += 1
    if(operation._divide > 0):
        operation._divide -= 1
        dfs(int(value / number[count]), count+1, operation)
        operation._divide += 1

def createOperation(tempOp):
    operation = Operation(tempOp[0],tempOp[1],tempOp[2],tempOp[3])
    return operation

T = int(input())
for test_case in range(1, T + 1):
    minValue = 100_000_001
    maxValue = -100_000_001
    N = int(input())
    operation = createOperation(list(map(int, input().split())))
    number = list(map(int, input().split()))

    dfs(number[0], 1, operation)

    print("#{} {}".format(test_case, maxValue-minValue))

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

숫자카드는 고정되어 있고 그 사이에 들어갈 연산자만 정해주면 됩니다.

연산의 순서는 우리가 기존에 알던 수학과 달리 무조건 좌측부터 진행됩니다.

조금 더 효율적인 계산을 위해 연산자를 모두 정하고 나서 계산하지 않고, 재귀함수 내부에서 값을 가진 채 진행하면서 구현했습니다.

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

public class q4008_SWEA_숫자만들기 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, max, min;
	static int[] num;
	
	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++){
			max = Integer.MIN_VALUE; 
			min = Integer.MAX_VALUE;
			N = Integer.parseInt(br.readLine());
			num = new int[N];
			
			st = new StringTokenizer(br.readLine());
			int[] op = {Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())};
			
			st = new StringTokenizer(br.readLine());
			for(int n = 0; n < N; n++) {
				num[n] = Integer.parseInt(st.nextToken());
			}
			
			dfs(num[0], 1, op[0], op[1], op[2], op[3]);
			
			answer = max-min;
			
			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		
		System.out.println(sb);
	}
	
	static void dfs(int result, int count, int plus, int minus, int multiple, int divide) {
		
		if(count == N) {
			if(result < min) {
				min = result;
			}
			
			if(result > max) {
				max = result;
			}
		}
		
		if(plus > 0) {
			dfs(result + num[count], count+1, plus-1, minus, multiple, divide);
		}
		if(minus > 0) {
			dfs(result - num[count], count+1, plus, minus-1, multiple, divide);
		}
		if(multiple > 0) {
			dfs(result * num[count], count+1, plus, minus, multiple-1, divide);
		}
		if(divide > 0) {
			dfs(result / num[count], count+1, plus, minus, multiple, divide-1);
		}
		
	}
}