pjaehyun의 개발일지

문제

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

문제풀이 코드

import sys

input = sys.stdin.readline

N = int(input())

mod = 10**9 + 7

def mul(matrix1, matrix2):
    res = [[0] * 2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                res[i][j] += matrix1[i][k] * matrix2[k][j]
            res[i][j] %= mod
    return res

def devide(n, matrix):
    if n == 1:
        return matrix
    else:
        temp = devide(n//2, matrix)
        if n % 2 == 0:
            return mul(temp, temp)
        else:
            return mul(mul(temp, temp), matrix)

matrix = [[1, 1], [1, 0]]
if N - 1 < 2:
    print(1)
else:
    print(devide(N-1, matrix)[0][0])

풀이방식

1. 동적계획법으로 풀려고했으나, n의 최댓값이 엄청 크기때문에 동적계획법으로 해결할 수 없었다. 이에  행렬을 이용하여 피보나치 수를 구할 수 있다는 것을 확인하고 분할정복으로 행렬의 n제곱을 구하는 방식으로 해결하였다.

2. mul 함수는 matrix1과 matrix2를 곱해주는 함수이다. 

3. devide함수는 n을 2로 계속 나누면서 행렬을 연산해주는 역할을 한다.

   - n == 1이면 기본 행렬을 반환한다.

   - n % 2 == 0 이면 temp의 제곱을 반환한다.

   - n % 2 != 0 이면 temp의 제곱을 구하고 현재 matrix와의 곱셈을 구하여 반환한다.

4. devide함수를 실행하면서 temp의 값이 계속해서 연산이 되며 n제곱의 값을 얻을 수 있다.

5. devide를 시작할 때 matrix는 피보나치 수의 1에 해당하기 때문에 N에 -1을 해준 결과를 반환해준다.(-1을 안하고 [0][1]의 값을 출력해도 됨)

문제

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

문제풀이 코드

import sys, math
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

N, K = map(int, input().split())

things = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (K+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, K+1):
        if things[i-1][0] <= j:
            dp[i][j] = max(things[i-1][1] + dp[i-1][j - things[i-1][0]], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[N][K])

풀이방식: 동적 계획법(Knapsack 알고리즘)을 이용한 문제 풀이

1. 무게가 6이고 가치가 13인 물건은 배낭의 무게가 6일때 물건을 넣을 수 있고, 7일 때 무게가 6인 물건과 무게가 7 - 6인 물건을 넣을 수 있다.

2. 무게가 4이고 가치가 8인 물건은 배낭의 무게가 4, 5, 6, 7일때 물건을 넣을 수있다. 

3. 이와 마찬가지로 모든 물건들은 각자가 가진 무게와 남은 배낭 무게만큼 물건을 넣으면서 최대값을 구할 수 있다.

4. 위 표를 보면 쉽게 이해할 수있는데, (4,8)인 물건을 가방에 넣고 있을 때, 배낭의 무게가 6일때 (8, 13)을 비교하여 더 큰 값을 넣게된다.

5. 이를 식으로 나타내면 dp[i][j] = max(things[i][0] + dp[i-1][j - things[i][1], dp[i-1][j])가 된다.

6. 이러한 점화식을 가지고 반복문을 돌리면 문제를 해결할 수 있다.

문제

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

문제풀이 코드

import sys
input = sys.stdin.readline

str1 = input().strip()
str2 = input().strip()

n, m = len(str1), len(str2)

dp = [[0] * (m+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        if str1[i-1] == str2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[-1][-1])

풀이 방식: 동적 계획법(dp)를 이용하여 문제 풀이

1. str1과 str2배열을 순회하며 str1[i-1]과 str2[j-1]이 같을 때와 다를 때로 나눌 수 있다.

2. 만약 글자가 같다면 이전 문자가 추가되기 이전의 값에 +1을 해주면 된다 => dp[i][j] = dp[i-1][j-1] + 1

3. 글자가 다르다면 이전에 비교해왔던 값중 최대값으로 세팅해주면 된다. => dp[i][j] = max(dp[i-1][j], dp[i][j-1])

4. 이 두가지 점화식을 사용하여 반복문을 통해 두 문자열을 순회하며 dp배열을 초기화해주면 된다.

문제

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

import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline

N, L = map(int, input().split())

drawer = {x:x for x in range(1, L+1)}
have = {x:False for x in range(1, L+1)}

def find(x):
    if x != drawer[x]:
        drawer[x] = find(drawer[x])
    return drawer[x]

def union(x, y):
    rootX = find(x)
    rootY = find(y)

    drawer[rootX] = rootY



for i in range(N):
    x, y = map(int, input().split())

    if not have[x]:
        have[x] = True
        union(x, y)
        print("LADICA")
    elif not have[y]:
        have[y] = True
        union(y, x)
        print("LADICA")
    elif not have[find(x)]:
        have[find(x)] = True
        union(x, y)
        print("LADICA")
    elif not have[find(y)]:
        have[find(y)] = True
        union(y, x)
        print("LADICA")
    else:
        print("SMECE")

풀이방식: 주어진 서랍과 서랍들의 부모서랍의 자리가 비어있는지 확인하는 문제이므로 union-find(응용)를 사용하여 문제 풀이

1. union과 find 함수를 생성

  - find 함수는 기존 템플릿과 동일하지만, union은 기존과 조금 달라진다.

  - union함수는 더 작은 값을 가지는게 아닌 y의 root값을 가져야 한다.

2. 문제를 4가지 경우로 분류할 수 있다.

  첫번째. 서랍 A가 비어있을 때

  두번째. 서랍 A의 부모서랍이 비어있을 때

  세번째. 서랍 B가 비어있을 때

  네번째. 서랍 B의 부모서랍이 비어있을 때

  ※ 부모서랍이 비었을 때를 확인하는 것은 현재 서랍이 비어있을 때 한칸씩 옮겨야 하기 때문이다.

3. union-find를 사용하기 위해 drawer와 서랍이 비어있는지 체크하기 위한 have를 생성한다.

4. 각 input을 받아오면서 2번에 해당하는 경우들을 체크한다.

5. 비어있는 서랍을 발견했다면 해당 서랍을 채워주고 union 함수를 호출하고 "LADICA"를 출력한다.

6. 아무 조건에 해당하지 않으면 서랍이 차있는 상태이기 때문에 "SMECE"를 출력

문제

https://leetcode.com/problems/lexicographically-smallest-equivalent-string/description/

You are given two strings of the same length s1 and s2 and a string baseStr.

We say s1[i] and s2[i] are equivalent characters.

• For example, if s1 = "abc" and s2 = "cde", then we have 'a' == 'c', 'b' == 'd', and 'c' == 'e'.

Equivalent characters follow the usual rules of any equivalence relation:

• Reflexivity: 'a' == 'a'.
• Symmetry: 'a' == 'b' implies 'b' == 'a'.
• Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'.

For example, given the equivalency information from s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr = "eed", and "aab" is the lexicographically smallest equivalent string of baseStr.

Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.

Example 1:

Example 2:

Example 3:

Constraints:

• 1 <= s1.length, s2.length, baseStr <= 1000
• s1.length == s2.length
• s1, s2, and baseStr consist of lowercase English letters.

문제풀이 코드

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        UF = {}

        def find(x):
            if x not in UF:
                UF[x] = x
            
            if x != UF[x]:
                print(x, UF[x])
                UF[x] = find(UF[x])
            return UF[x]
                

        def union(x, y):
            # 두 값의 루트값을 탐색
            rootX = find(x)
            rootY = find(y)
			
            # 두 루트값 중 더 작은 값을 루트노드로 초기화한다
            if rootX > rootY:
                UF[rootX] = rootY
            else:
                UF[rootY] = rootX
        
        for i in range(len(s1)):
            union(s1[i], s2[i])
        
        answer = ""
        for s in baseStr:
            answer += find(s)
        return answer

풀이방식: 서로 연결된 알파벳들은 연결된 알파벳 중 가장 작은 알파벳으로 루트값을 가져가야 하기 때문에 Union-Find 알고리즘 사용

1. 기본적인 Union-Find 알고리즘을 구현한다

  - union: 두 값의 루트 값을 찾아 둘 중 더 작은 값을 가지는 루트값으로 루트노드를 바꿔준다.

  - find: 재귀 함수를 통해 현재 값의 루트값을 찾는다.

2. union 함수에 s1[i]와 s2[i]를 파라미터로 넣어 호출한다.(s1[i]와 s2[i]는 같은 집합)

3. 반복문이 종료되면 UF는 같은 집합끼리 묶여 그 집합내에 가장 작은 값을 루트노드로 가지게 된다.

4. baseStr의 문자들과 연결되는 값을 find함수를 통해 찾아온다.

문제

https://leetcode.com/problems/longest-path-with-different-adjacent-characters/

You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.

You are also given a string s of length n, where s[i] is the character assigned to node i.

Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.

Example 1:

Input: parent = [-1,0,0,1,1,2], s = "abacbe"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned.
It can be proven that there is no longer path that satisfies the conditions. 

Example 2:

Input: parent = [-1,0,0,0], s = "aabc"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.

Constraints:

• n == parent.length == s.length
• 1 <= n <= 105
• 0 <= parent[i] <= n - 1 for all i >= 1
• parent[0] == -1
• parent represents a valid tree.
• s consists of only lowercase English letters.

문제풀이 코드

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)

        tree = defaultdict(list)
        for end, start in enumerate(parent):
            tree[start].append(end)
        
        answer = 1
        def dfs(node):
            nonlocal answer
            res = 1
            for child in tree[node]:
                l = dfs(child)
                if s[node] != s[child]:
                    answer = max(answer, res + l)
                    res = max(res, l+1)
            return res
        dfs(0)
        return answer

1. 트리형태의 그래프를 만들어 준다. ex) {0:[1,2], 1:[3,4], 2:[5]}

2. 최소값은 자기 노드 하나이기 때문에 answer를 1로 초기화

3. 그래프를 탐색하기 위한 dfs 함수를 만들어준다.

  - 현재 연결된 노드의 최솟값은 1이기 때문에 현재 연결된 노드들을 1로 선언

  - 현재 노드의 자식노드들을 탐색한다.

  - 노드를 탐색할 때 l = dfs(child)를 통해 자식노드가 그 하위노드와 연결된 최대값을 가져온다.

  - 현재 알파벳과 자식노드의 알파벳이 다를 때 answer와 res를 초기화해준다.

    -> answer = max(answer, res+l): res+l 은 현재의 노드부터 이전에 연결된 노드들의 갯수로 초기화해준다.

    -> res = max(res, l+1): l+1은 이전 연결된 노드에 현재 노드를 연결한 값으로 초기화해준다.

4. dfs가 종료되면 answer에는 최대로 연결된 노드의 개수가 들어가있기 때문에 answer를 반환한다.

문제

https://leetcode.com/problems/word-search/

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        row, col = len(board), len(board[0])
        visited = [[False] * col for _ in range(row)]
        def dfs(x,y,s):
            if s == len(word):
                return True
            if x < 0 or x > row-1 or y < 0 or y > col-1 or word[s] != board[x][y] or visited[x][y]:
                return False
            visited[x][y] = True
            res = (dfs(x+1,y, s+1) or dfs(x,y+1, s+1) or
                   dfs(x-1,y, s+1) or dfs(x,y-1, s+1))
            visited[x][y] = False
            return res
        for i in range(row):
            for j in range(col):
                if dfs(i,j,0):
                    return True
        return False

주어진 알파벳들로 주어진 단어를 만들 수 있는지 체크하는 것이기 때문에 dfs를 이용하여 문제풀이

1. 좌,우,위.아래를 탐색해야 되기 때문에 현재 x,y가 조건에 맞는지 체크한다.

2. 그리고 가장 핵심이 되는 현재 연결된 단어가 word의 부분인지 확인하기 위해 현재 알파벳과, word의 s번째 순서의 알파벳이 같은지 비교한다.

3. 조건을 만족했을 때, 모든 방향으로 dfs를 호출한다.
4. 호출된 dfs중 하나라도 True가 존재하면 res는 True가 된다.

5. 배열을 전부 돌면서 dfs(i,j,0)이 True일 때 True를 반환하고

6. 반복문이 정상적으로 종료된다면 False를 반환한다.

문제

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

from collections import defaultdict, deque
import sys
input = sys.stdin.readline

def bfs(start, end, subways):
    if start == end:
        return 0
    visited_subway = [False for _ in range(len(subways))]
    visited_station = [False for _ in range(N + 1)]

    dq = deque()
    for subway in graph[start]:
        dq.append((subway, 0))
        visited_subway[subway] = True
    visited_station[start] = True
    
    while dq:
        subway, count = dq.popleft()
        # 현재 지하철이 갈 수 있는 지하철역을 탐색
        for station in subways[subway]:
            # 방문했던 지하철역이면 패스
            if visited_station[station]:
                continue
            # 현재 역이 도착역과 같으면 return
            if station == end:
                return count       
            visited_station[station] = True
            for trans in graph[station]:
                # 한번도 타지않은 지하철일 때 dq에 삽입
                if not visited_subway[trans]:
                    dq.append((trans, count+1))
                    visited_subway[trans] = True
    return -1
            
N, L = map(int, input().split())

# 지하철역에서 탈수있는 호선
graph = defaultdict(list)

# 호선이 지나는 지하철역
subways = []
for i in range(L):
    lst = list(map(int, input().split()))
    subways.append(lst[:-1])
    for l in lst:
        if l == -1:
            continue
        graph[l].append(i)

start, end = map(int, input().split())
result = bfs(start, end, subways)
print(result)

문제를 접하고 그래프 탐색 알고리즘인건 알았지만 그래프를 어떻게 세팅해야할지 삽질을 많이했고, 문제를 해결하면서 시간초과가 나서 이를 해결하기위해 또 많은 시간을 썻다....

1. 지하철 호선이 갈 수 있는 지하철역을 담은 배열과, 지하철역에서 탈 수 있는 호선을 담은 딕셔너리(배열도 상관없음)를 만들어준다.

2. 시작역과 도착역의 최소 환승을 구하는 문제이기 때문에 bfs를 만들어 준다.

3. bfs는 일반적인 것과 크게 다르지 않다.

   - 환승의 횟수를 구하기 위해 환승 횟수를 count하는 변수를 dq에 추가로 담아준다.

   - 지하철역과, 호선을 중복탐색하지 않도록 visited 리스트를 각각 생성해준다.

   - 현재 호선이 갈 수 있는 모든 지하철역을 탐색한다.(이전에 탐색한적이 없는 지하철역만)

   - 지하철역에서 탈 수 있는 모든 호선을 dq에 넣어준다.(이전에 탐색한적이 없는 호선만)

4. 이 과정을 반복하며 현재 지하철역이 도착역과 같을 때 현재 환승 횟수를 반환한다.

5. 출발역에서 도착역까지 도달할 수 없다면 -1을 반환한다.