내일은 알고리즘

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

https://www.acmicpc.net/problem/1562

풀이방법 아이디어를 떠올리기 힘든 비트마스킹을 활용한 DP문제입니다.

계단수라는 것은 각 자리수의 차이가 1입니다.

즉 N-1자리의 마지막 자리가 X로 끝나는 계단수가 있다면 이 뒤에 X와 1 차이가 나는 숫자를 붙여서 N자리의 계단수를 만들 수 있습니다.

1자리의 계단수는 모두 9개로 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]입니다. (0으로 시작하는 수는 계단수가 아님)

2자리의 계단수는 1자리의 계단수에 1차이가 나는 숫자를 붙여서 만들 수 있고 마지막 자리의 숫자에 따라

10 - 0으로 끝남

21 - 1로 끝남

12 32 - 2로 끝남

23 43 - 3으로 끝남

34 54 - 4로 끝남...

이런 식으로 구분됨을 알 수 있습니다.

이때 위에서 얘기했던것처럼 0으로 끝나는 계단수는 이전 N-1자리에서 1로 끝난 계단수에 0을 붙여 만든 것이고 1로 끝나는 계단수는 0으로 끝나거나 2로 끝난 계단수에 1을 붙여 만든 것입니다.

(이번 경우에는 0으로 끝나는 1자리수 계단수가 존재하지 않습니다.)

이 방법을 N번 반복하면 우리는 X로 끝나는 N자릿수의 계단수를 구할 수 있습니다.

다만 문제에서는 0~9까지 10개의 숫자를 모두 사용한 계단수를 묻습니다.

따라서 해당 계단수에 어떤 숫자가 사용되었는지를 기억해야하는데, 개수와 상관없이 사용의 여부만 알면 되기 때문에 비트마스킹을 활용할수 있습니다.

이제 위의 아이디어를 구현하면 됩니다.

다만 N자리 계단수를 구하기 위해 필요한 N-1자리의 계단수를 고려하는것은 너무 복잡하기 때문에 N-1단계에를 완전탐색하며 이 값을 N자리 계단수로 누적합해주는 식으로 코드를 짜는게 더 간단합니다.

그리고 조건으로도 주어졌지만 진행 과정중에 변수의 범위를 넘는 경우를 막기 위해 누적될 때마다 주어진 값으로 mod 연산을 해야합니다.

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

public class q1562_BOJ_계단수 {

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

		int max = (1 << 10);
		int mod = 1_000_000_000;

		int[] bit = new int[10];
		for (int i = 0; i < 10; i++) {
			bit[i] = 1 << i;
		}

		int N = Integer.parseInt(br.readLine());
		int[][][] dp = new int[10][N + 1][max];

		for (int i = 1; i < 10; i++) {
			dp[i][1][bit[i]] = 1;
		}

		for (int n = 1; n < N; n++) {
			for (int j = 1; j < max; j++) {
				dp[1][n + 1][j | bit[1]] = (dp[1][n + 1][j | bit[1]] + dp[0][n][j]) % mod;
				for (int i = 1; i < 9; i++) {
					dp[i - 1][n + 1][j | bit[i - 1]] = (dp[i - 1][n + 1][j | bit[i - 1]] + dp[i][n][j]) % mod;
					dp[i + 1][n + 1][j | bit[i + 1]] = (dp[i + 1][n + 1][j | bit[i + 1]] + dp[i][n][j]) % mod;
				}
				dp[8][n + 1][j | bit[8]] = (dp[8][n + 1][j | bit[8]] + dp[9][n][j]) % mod;
			}
		}

		int sum = 0;

		for (int i = 0; i < 10; i++) {
			sum = (sum + dp[i][N][max-1]) % mod;
		}

		System.out.println(sum);

	}
}

https://leetcode.com/problems/min-cost-climbing-stairs/

계단문제의 변형입니다. 

가장 적은 걸음수로 계단을 오르는 유형과 흡사한 가장 적은 힘을 들이고 계단을 오르는 값을 찾는 문제입니다.

각 계단별로 여기까지 오는데 쓰는 최소한의 힘을 기억시키고 규칙에 따라 하나씩 최솟값을 채워가며 구현했습니다.

class Solution:
    def minCostClimbingStairs(self, cost: list) -> int:
        size = len(cost) + 1
        dp = [0] * size

        for i in range(2,size):
            dp[i] = min((dp[i-1] + cost[i-1]),(dp[i-2] + cost[i-2]))

        return dp[-1]



input = [[10,15,20],[1,100,1,1,1,100,1,1,100,1]]

for i in input:
    print(Solution().minCostClimbingStairs(i))

https://leetcode.com/problems/climbing-stairs/

DP의 또다른 대표 문제인 계단 문제입니다.

이 기본 유형에서는 피보나치와 코드가 거의 같다고 보셔도 될 것 같습니다.

계단을 오르는 갯수, 지뢰, 내려가기 등을 섞어 여러 유형으로 활용되는 문제입니다.

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0]*(n+1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2,n+1):
            dp[i] = dp[i-2] + dp[i-1]
        return dp[n]


for i in range(1,46):
    print(Solution().climbStairs(i))

https://leetcode.com/problems/n-th-tribonacci-number/

피보나치 문제와 99.9% 똑같지만 점화식이 이전의 세 수를 더한다는 차이점이 있습니다.

그러니 이름이 트리보나치겠죠? 간단하게 풀이했습니다.

class Solution:
    def tribonacci(self, n: int) -> int:
        dp = [0] * (38)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 1

        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

        return dp[n]

for i in range(0,26):
    print(Solution().tribonacci(i))

https://leetcode.com/problems/fibonacci-number/

정말 유명한 피보나치 DP문제입니다.

매번 피보나치 수를 새로 계산하지 않고 이전의 결과값을 사용해 계산하면 됩니다.

Memoization의 개념과 필요성을 한방에 이해시키는 좋은 문제라고 생각합니다.

class Solution:
    def fib(self, n: int) -> int:
        dp = [0] * (31)
        dp[0] = 0
        dp[1] = 1

        for i in range(2,n+1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]

for i in range(0,31):
    print(Solution().fib(i))

https://leetcode.com/problems/is-subsequence/

Subsequence는 어떤 String에서 임의의 문자들을 삭제했을때 만들어지는 String이라고 합니다.

s가 t의 Subsequence인지 묻는 문제입니다.

문제 자체는 그리디한 느낌으로 s의 문자들을 차례대로 t에서 찾으면 해결됩니다.

다만 제 풀이코드 기준에서 s와 t의 길이에 따라 index가 범위를 넘어가는 경우가 있어서 예외처리해 주었습니다.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if(len(s) > len(t)):
            return False
        if(len(s) == 0):
            return True

        idx = 0
        for i in t:
            if(i == s[idx]):
                idx += 1
            if(len(s) == idx):
                return True
        return False

input = [["abc", "ahbgdc"],["axc", "ahbgdc"]]

for i in input:
    print(Solution().isSubsequence(i[0],i[1]))