내일은 알고리즘

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

람다식을 활용한 정렬을 사용하면 쉽게 풀리는 문제입니다.

우선 문제의 조건을 만족하도록 실패율을 구해줍니다. n번째 스테이지에 멈춰있는 인원이 Xn명이라면, n+1번째 스테이지에 도달한 인원은 n번째 스테이지에 도달한 인원 - nX명 이 됩니다.

즉, 첫 스테이지에는 모두가 도달했으므로 실패율이 (첫 스테이지에 멈춘 인원 / 전체 인원)이라면 두번째 스테이지는 (두번째 스테이지에 멈춘 인원 / (전체인원 - 첫 스테이지에 멈춘 인원)) 이 됩니다.

실패율을 계산해 주고, 만약 도달인원이 없다면 그냥 0으로 처리해주고 (divide zero 런타임 에러를 막기 위함) 얻은 실패율을 스테이지의 순서와 함께 묶어 리스트에 저장한 뒤 실패율을 기준으로 내림차순 정렬, 두번째 요소는 스테이지를 기준으로 오름차순 정렬을 해주면 됩니다.

fail_rate.sort(key=lambda x:(-x[0], x[1]))

x[0]이 실패율로 내림차순 정렬을 위해 마이너스 부호를 붙여주고, x[1]은 스테이지 번호로 오름차순 정렬이 됩니다.

def solution(N, stages):
    answer = []
    
    fail_rate = [[0, i+1] for i in range(N)]
    stage_user = [0 for i in range(N+1)]
    total_user = len(stages)
    
    for stage in stages:
        stage_user[stage - 1] += 1
    
    for i in range(N):
        if total_user == 0:
            fail_rate[i][0] = 0
        else:
            fail_rate[i][0] = stage_user[i] / total_user
            total_user -= stage_user[i]
    
    fail_rate.sort(key=lambda x:(-x[0], x[1]))
    
    for i in fail_rate:
        answer.append(i[1])
    
    return answer

print(solution(	5, [2, 1, 2, 6, 2, 4, 3, 3]))

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

기본적인 반복문과 사칙연산, 약수의 원리 정도만 알면 쉽게 풀이가 가능한 문제입니다.

left <= num <= right 범위의 숫자들에 대해서 반복문을 돌려 탐색하고 1과 자기 자신은 반드시 약수이므로 약수의 갯수 2개를 잡아두고 시작합니다. (단 1은 자기 자신이 1이므로 1부터 시작합니다.)

나를 제외한 약수의 최댓값은 num/2이므로 탐색도 거기서 멈춰주시면 됩니다.

def solution(left, right):
    answer = 0
    
    for num in range(left, right+1):
        count = 2 if num != 1 else 1
        for div in range(2, (num//2) + 1):
            if num % div == 0:
                count += 1 
        if count % 2 == 0:
            answer += num
        else:
            answer -= num
    
    return answer

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

Heap, 또는 PriorityQueue로 알려진 우선순위 큐를 활용하는 문제입니다.

라이브러리 내의 heapq등의 완성된 자료구조를 사용해도 되지만 직접 구현해서 풀이했습니다.

아이디어는 간단합니다, 현재 시간에 요청이 들어온 작업들을 우선순위 큐에 넣고 작업이 끝났을때 시간을 기준으로 

끝난시간 - 요청시간 = 총 대기시간이 됩니다. 

작업이 끝나면 그 시간으로 시간을 진행시켜줍니다. 이 방법으로 모든 업무가 큐에 들어가고 큐가 빌때까지 진행해 주었습니다.

def solution(jobs):

    jobs.sort(key=lambda x: (x[0], x[1]))

    time = jobs[0][0]
    exec_time = 0
    index = 0
    heap = MinHeap()

    while True:
        while index < len(jobs):
            if jobs[index][0] <= time:
                heap.insert(jobs[index])
                index += 1
            elif len(heap.queue) == 0 and index < len(jobs):
                time = jobs[index][0]
            else:
                break

        task = heap.pop()
        if not task:
            break
        exec_time += time + task[1] - task[0]
        time += task[1]

    return int(exec_time / len(jobs))


class MinHeap(object):

    def __init__(self) -> None:
        self.queue = []

    def insert(self, n) -> None:
        index = len(self.queue)
        self.queue.append(n)
        while 0 <= index:
            pIndex = self.parent((index))
            if 0 <= pIndex and self.queue[pIndex][1] > self.queue[index][1]:
                self.swap(index, pIndex)
                index = pIndex
            else:
                break

    def pop(self):
        if len(self.queue) == 0:
            return False

        last = len(self.queue) - 1
        self.swap(0, last)
        front = self.queue.pop()
        self.sort(0)
        return front

    def sort(self, index):
        left = self.leftChild(index)
        right = self.rightChild(index)
        smaller = index

        if left < len(self.queue) and self.queue[smaller][1] > self.queue[left][1]:
            smaller = left
        if right < len(self.queue) and self.queue[smaller][1] > self.queue[right][1]:
            smaller = right

        if index != smaller:
            self.swap(index, smaller)
            self.sort(smaller)

    def swap(self, a, b) -> None:
        temp = self.queue[a]
        self.queue[a] = self.queue[b]
        self.queue[b] = temp

    def parent(self, index) -> int:
        return (index - 1) // 2

    def leftChild(self, index) -> int:
        return index * 2 + 1

    def rightChild(self, index) -> int:
        return index * 2 + 2


print(solution([[1, 9], [0, 3], [2,8], [4,10], [2, 6],[150,1]]))

https://leetcode.com/problems/reverse-linked-list/

LinkedList를 뒤집는 문제입니다.

재귀함수를 이용해 리스트를 타고 끝을 찾은 뒤 끝에서부터 재귀함수를 빠져나오면서 연결 방향을 거꾸로 뒤집었습니다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if(not head or not head.next):
            return head
        
        rest = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return rest

input = ListNode(1,ListNode(2, ListNode(3,ListNode(4, ListNode(5,None)))))
# input = None

answer = Solution().reverseList(input)
while(answer):
    print(answer.val)
    answer = answer.next

https://leetcode.com/problems/merge-two-sorted-lists/

구현은 어렵지 않지만 LinkedList에 낯설면 접근하기 어려울 수도 있는 문제입니다.

두개의 정렬된 LinkedList가 주어지는데 이 둘을 합쳐 정렬된 하나의 LinkedList를 만들어야 합니다.

결과를 저장하기 위한 새로운 하나의 리스트를 만들고 입력된 두개의 리스트를 비교하면서 작은 순서대로 새로운 리스트에 붙여나갔습니다.

만약 입력 리스트 중에 하나가 끝난다면 결과 리스트의 맨 끝이 남은 입력리스트를 가리키게 하고 리턴했습니다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        root = ListNode()
        index = root
        
        while(list1 and list2):
            if(list1.val > list2.val):
                index.next = list2
                list2 = list2.next
                index = index.next
            else:
                index.next = list1
                list1 = list1.next
                index = index.next
        
        if(list1):
            index.next = list1
        elif(list2):
            index.next = list2
        
        return root.next
    

input = [[ListNode(1,ListNode(2, ListNode(4,None))),ListNode(1,ListNode(3, ListNode(4,None)))],
         [None,None],
         [None,ListNode(1,ListNode(3, ListNode(4,None)))],
         [ListNode(1,None),None]]

for i in input:
    answer = Solution().mergeTwoLists(i[0],i[1])
    while(answer):
        print(answer.val)
        answer = answer.next

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

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

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

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

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

보통 부분집합을 응용하는 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)

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://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))