내일은 알고리즘

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]))

https://leetcode.com/problems/isomorphic-strings/

상당히 낯선 단어인데 Isomorphic은 동형사상이라는 뜻이라고 합니다.

Isomorphic String은 두 String의 형태가 닮아있는 것을 말하는데요. 예를 들어 glass와 shell이 동형관계입니다.

두 단어는 생김새가 전혀 다르지만 알파벳이 등장하는 순서대로 번호를 매기면 12344, 12344로 구조가 같음을 알 수 있습니다.

반대로 banana와 canada는 단어 생긴건 비슷하지만 번호를 매기면 123232와 123242로 차이가 있습니다.

문제에서 주어진 String을 앞에서부터 읽어가며 처음 만나는 알파벳인 경우 Dictionary에 Index값을 넣어주고, 이미 만났던 알파벳인 경우 Index값을 비교해 같은 구조인지 체크해줬습니다.

물론 알파벳의 내용은 다르므로 Dictionary를 두개 만들어서 따로 저장했습니다.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        sDict = {}
        tDict = {}
        idx = 0

        for i in range(0,len(s)):
            if(not (s[i] in sDict) and not (t[i] in tDict)):
                sDict[s[i]] = idx
                tDict[t[i]] = idx
                idx += 1
            elif(s[i] in sDict and t[i] in tDict):
                if(sDict[s[i]] != tDict[t[i]]):
                    return False
            else: 
                return False
        
        return True

input = [["egg","add"],["foo","bar"],["paper","title"]]

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

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

BFS + 비트마스킹으로 풀이하는 문제입니다.

벽부수기 같은 문제처럼 visited 체크를 열쇠의 소유상태에 따라 다르게 해줘야 합니다.

해당 부분을 비트마스킹 Integer로 저장하거나 배열을 통해 저장하거나 편한 방법으로 풀이할 수 있습니다.

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 q1194_BOJ_달이차오른다가자 {
	static StringTokenizer st;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int R, C;

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

		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		char[][] map = new char[R][C];
		boolean[][][] visited = new boolean[R][C][64];

		Queue<Player> queue = new LinkedList<>();

		for (int r = 0; r < R; r++) {
			String input = br.readLine();
			for (int c = 0; c < C; c++) {
				map[r][c] = input.charAt(c);
				if (map[r][c] == '0') {
					queue.offer(new Player(r, c, 0));
					visited[r][c][0] = true;
					map[r][c] = '.';
				}
			}
		}

		int time = 0;
		boolean flag = false;

		loop: while (!queue.isEmpty()) {
			int size = queue.size();
			time++;
			while (size-- > 0) {
				Player p = queue.poll();
				int x = p.x;
				int y = p.y;
				int key = p.key;

				for (int i = 0; i < 4; i++) {
					int nX = x + delta[i][0];
					int nY = y + delta[i][1];
					if (isIn(nX, nY) && map[nX][nY] != '#' && !visited[nX][nY][key]) {
						if (map[nX][nY] == '.') {
							queue.offer(new Player(nX, nY, key));
							visited[nX][nY][key] = true;
						} else if (map[nX][nY] == '1') {
							flag = true;
							break loop;
						} else if (map[nX][nY] < 'a' && canOpen(map[nX][nY], key)) {
							queue.offer(new Player(nX, nY, key));
							visited[nX][nY][key] = true;
						} else if (map[nX][nY] >= 'a') {
							int nKey = (1 << (map[nX][nY] - 'a')) | key;
							queue.offer(new Player(nX, nY, nKey));
							visited[nX][nY][nKey] = true;
						}
					}
				}
			}

		}

		if (flag) {
			System.out.println(time);
		} else {
			System.out.println("-1");
		}
	}

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

	static boolean canOpen(char door, int key) {
		if ((1 << (door - 'A') & key) > 0) {
			return true;
		}
		return false;
	}

	static class Player {
		int x, y, key;

		public Player(int x, int y, int key) {
			this.x = x;
			this.y = y;
			this.key = key;
		}
	}
}

https://leetcode.com/problems/find-pivot-index/

좌측합과 우측합을 같게 만드는 중심을 찾는 꽤 재밌는 문제였습니다.

슬라이딩 윈도우와 비슷한 느낌으로 구현했는데, 좌측합이 0, 우측합이 모든 누적합인 상태로 시작해서 이번 턴에 중심으로 테스트하는 값을 우측합에서 빼고 이전 턴에 테스트한 값을 좌측합에 더하는 식으로 구현했습니다.

testcase 1번값의 풀이진행을 그림으로 나타내면 아래와 같습니다.

class Solution:
    # def pivotIndex(self, nums: List[int]) -> int:
    def pivotIndex(self, nums: list) -> int:
        pivot = -1
        idx = 0
        leftSum = 0
        rightSum = self.getRightSum(nums)

        while(idx < len(nums)):
            rightSum -= nums[idx]
            if(idx > 0):
                leftSum += nums[idx-1]
            
            if(leftSum == rightSum):
                pivot = idx
                break
            idx += 1

        return pivot
    
    def getRightSum(self, nums:list):
        rightSum = 0
        for i in nums:
            rightSum += i

        return rightSum


input = [[1,7,3,6,5,6],[1,2,3],[2,1,-1]]
for i in input:
    print(Solution().pivotIndex(i))

https://leetcode.com/problems/running-sum-of-1d-array/

LeetCode의 14일짜리 코스를 시험삼아 시작해봤습니다.

하루에 2문제씩 14일간 28문제를 푸는 코스네요.

배열의 누적합 문제입니다.

딱히 설명할 부분은 없는 간단한 문제였습니다.

LeetCode에서 주어지는 Example 코드가 Python 3.5 이상에서만 돌아가는 코드여서 주석처리 했습니다.

class Solution:
    # def runningSum(self, nums: List[int]) -> List[int]:
    def runningSum(self, nums: list) -> list:
        sum = 0
        answer = []
        for i in nums:
            sum += i
            answer.append(sum)
        
        return answer


input = [[1,2,3,4],[1,1,1,1,1],[3,1,2,10,1]]
for i in input:
    print(Solution().runningSum(i))