공부블로그

오늘의 공부 키워드

• 1791 Find Center of Star Graph

1791 Find Center of Star Graph

문제 해석

 이 문제는 n개의 노드(점)로 이루어진 무방향 스타 그래프에 관한 것입니다. 스타 그래프는 하나의 중심 노드가 있고, 나머지 n-1개의 노드가 그 중심 노드와 연결된 구조를 가집니다.

 edges라는 2차원 정수 배열이 주어집니다.  edges[i] = [ui, vi]는 노드 ui와 노드 vi 사이에 엣지가 있다는 것을 나타냅니다. 주어진 스타 그래프의 중심 노드를 반환하는 것이 이 문제의 목표입니다.

예시

예시 1:

입력: edges = [[1,2],[2,3],[4,2]]

출력: 2

설명: 노드 2는 다른 모든 노드와 연결되어 있으므로 중심 노드입니다.

예시 2:

입력: edges = [[1,2],[5,1],[1,3],[1,4]]

출력: 1

설명: 노드 1은 다른 모든 노드와 연결되어 있으므로 중심 노드입니다.

해결 방안

중심 노드를 찾기 위해서는 각 엣지에서 공통적으로 등장하는 노드를 찾으면 됩니다. 왜냐하면 스타 그래프에서 중심 노드는 모든 엣지에 등장하기 때문입니다. 아래의 방법으로 문제를 해결할 수 있습니다:

1. 첫 번째 엣지를 선택합니다. (edges[0])
2. 첫 번째 엣지의 두 노드 중 하나는 중심 노드입니다.
3. 두 번째 엣지에서도 이 두 노드 중 하나가 등장하는지를 확인합니다.
4. 등장한다면 그 노드가 중심 노드입니다.

코드

def findCenter(edges):
    # 첫 번째 엣지의 두 노드를 선택합니다.
    a, b = edges[0]
    
    # 두 번째 엣지에서 a 또는 b가 등장하는지를 확인합니다.
    # 만약 a가 등장하면 a가 중심 노드입니다.
    if edges[1][0] == a or edges[1][1] == a:
        return a
    # 그렇지 않으면 b가 중심 노드입니다.
    else:
        return b

# 예시 테스트
print(findCenter([[1, 2], [2, 3], [4, 2]]))  # 출력: 2
print(findCenter([[1, 2], [5, 1], [1, 3], [1, 4]]))  # 출력: 1

오늘의 공부 키워드

• 1351.Count Negative Numbers in a Sorted Matrix

1351.Count Negative Numbers in a Sorted Matrix

이 문제는 m x n 행렬(grid)이 행과 열 모두 내림차순으로 정렬되어 있을 때, 행렬 안의 음수 숫자의 개수를 세는 문제입니다.

문제 이해

주어진 행렬은 각 행과 각 열이 내림차순으로 정렬되어 있습니다 예를 들어 아래 행렬에서는 음수 숫자가 8개 있습니다.

grid = [[4, 3, 2, -1],
        [3, 2, 1, -1],
        [1, 1, -1, -2],
        [-1, -1, -2, -3]]

접근 방법

이 문제를 해결하기 위한 효율적인 방법은 다음과 같습니다:

1. 각 행에 대해, 오른쪽에서 왼쪽으로 이동하면서 음수를 찾습니다.
2. 음수를 찾으면, 그 열 이하의 모든 값이 음수라는 것을 알 수 있습니다(왜냐하면 내림차순이기 때문입니다).
3. 따라서 그 지점에서 남은 모든 값을 음수로 간주하고, 음수의 개수를 누적합니다.

구체적인 단계는 다음과 같습니다:

1. 행(row)별로 반복합니다.
2. 각 행의 오른쪽 끝부터 시작하여 왼쪽으로 이동합니다.
3. 음수를 만나면 해당 지점에서 그 행의 끝까지 남은 요소의 개수를 더합니다.
4. 다음 행으로 이동하여 동일한 과정을 반복합니다.

예제

위의 예제 행렬을 통해 설명하면:

• 첫 번째 행: [-1]에서 음수를 만나므로 1개의 음수 발견
• 두 번째 행: [-1]에서 음수를 만나므로 1개의 음수 발견
• 세 번째 행: [-1, -2]에서 음수를 만나므로 2개의 음수 발견
• 네 번째 행: [-1, -1, -2, -3]에서 음수를 만나므로 4개의 음수 발견

이렇게 총 8개의 음수를 발견하게 됩니다.

코드

from typing import List

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        count = 0
        # 시작은 마지막 열의 처음 행
        row, col = 0, n - 1
        
        while row < m and col >= 0:
            if grid[row][col] < 0:
                # 음수를 만나면, 해당 열 아래 모든 행이 음수이므로 추가
                count += (m - row)
                col -= 1
            else:
                # 음수를 만나지 않으면 다음 행으로 이동
                row += 1
        
        return count

# 예제 테스트
solution = Solution()

grid1 = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
print(solution.countNegatives(grid1))  # 8

grid2 = [[3,2],[1,0]]
print(solution.countNegatives(grid2))  # 0

설명

1. 시작 지점: 맨 위 행(row)의 마지막 열(col)에서 시작합니다.
2. 탐색 방식:
   • 현재 위치의 값이 음수일 경우, 해당 열 이하의 모든 값이 음수임을 알 수 있으므로, 그 수만큼 카운트합니다. 그리고 왼쪽 열로 이동합니다.
   • 현재 위치의 값이 음수가 아닐 경우, 다음 행으로 이동합니다.
3. 반복: 행(row) 또는 열(col)의 끝에 도달할 때까지 반복합니다.
4. 결과 반환: 모든 음수의 개수를 반환합니다.

이 방식은 매번 음수를 만날 때마다 그 아래 모든 값을 계산하기 때문에 더 효율적이며, 시간 복잡도는 최악의 경우 O(m+n))입니다.

오늘의 회고

• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자
• 새로운 개념을 배울수 있어서 좋았다.

오늘의 공부 키워드

• 이진 탐색
• 35.Search Insert Position

이진 탐색의 개념

이진 탐색은 다음과 같은 단계를 거칩니다:

1. 초기 설정: 배열의 처음과 끝을 가리키는 두 개의 포인터(left와 right)를 설정합니다.
2. 중간 요소 찾기: left와 right의 중간 지점을 계산하여 mid로 설정합니다.
3. 비교:
   • nums[mid]가 타겟 값과 같으면, mid를 반환합니다.
   • nums[mid]가 타겟 값보다 작으면, 타겟 값은 mid의 오른쪽에 있으므로 left를 mid + 1로 이동시킵니다.
   • nums[mid]가 타겟 값보다 크면, 타겟 값은 mid의 왼쪽에 있으므로 right를 mid - 1로 이동시킵니다.
4. 반복: left가 right보다 작거나 같을 때까지 2-3 단계를 반복합니다.
5. 결과: 탐색 범위가 없으면 타겟 값이 배열에 없음을 의미하며, 이때 삽입 위치를 반환할 수 있습니다.

예시

정렬된 배열 nums = [1, 3, 5, 7, 9]와 타겟 값 target = 7을 찾는 예시를 통해 설명하겠습니다:

1. 초기 설정: left = 0, right = 4 (배열의 인덱스 범위)
2. 중간 요소 찾기: mid = (0 + 4) // 2 = 2
   • nums[2] = 5
3. 비교: 5 (nums[mid]) < 7 (target)
   • left = mid + 1 = 3
4. 반복:
   • 새로운 중간 요소 찾기: mid = (3 + 4) // 2 = 3
   • nums[3] = 7
5. 비교: 7 (nums[mid]) == 7 (target)
   • 타겟 값을 찾았으므로 mid = 3 반환

이 과정에서 타겟 값을 효율적으로 찾을 수 있습니다.

35. Search Insert Position

이 문제는 주어진 정렬된 배열에서 특정 값을 찾는 문제입니다. 만약 해당 값을 찾으면 그 인덱스를 반환하고, 찾지 못하면 그 값을 정렬된 순서에 맞게 삽입할 때의 인덱스를 반환하는 문제입니다. 이 문제는 이진 탐색 알고리즘을 사용하면 O(log n)의 시간 복잡도로 해결할 수 있습니다.

이진 탐색은 배열의 중간 요소와 타겟 값을 비교하고, 비교 결과에 따라 탐색 범위를 절반으로 줄여가는 방식으로 동작합니다. 정렬된 배열에서 빠르게 값을 찾거나 삽입할 위치를 찾기에 적합합니다.

예시

예를 들어보겠습니다:

1. 입력: nums = [1, 3, 5, 6], target = 5 출력: 2 (타겟 값 5는 배열의 2번 인덱스에 존재합니다.)
2. 입력: nums = [1, 3, 5, 6], target = 2 출력: 1 (타겟 값 2는 배열에 없으며, 2가 들어가면 [1, 2, 3, 5, 6]가 되므로 인덱스 1에 삽입됩니다.)
3. 입력: nums = [1, 3, 5, 6], target = 7 출력: 4 (타겟 값 7은 배열에 없으며, 7이 들어가면 [1, 3, 5, 6, 7]가 되므로 인덱스 4에 삽입됩니다.)

코드

def searchInsert(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return left

이 코드를 한 단계씩 설명하면 다음과 같습니다:

1. left와 right 포인터를 배열의 시작과 끝으로 설정합니다.
2. 배열이 유효한 범위 (left가 right보다 작거나 같을 때)에서 반복합니다.
3. 중간 인덱스 mid를 계산합니다.
4. 중간 값 nums[mid]가 타겟 값과 같으면 mid를 반환합니다.
5. nums[mid]가 타겟 값보다 작으면 타겟은 오른쪽에 있으므로 left를 mid + 1로 이동합니다.
6. nums[mid]가 타겟 값보다 크면 타겟은 왼쪽에 있으므로 right를 mid - 1로 이동합니다.
7. 반복이 끝난 후에도 값을 찾지 못하면, 타겟 값을 삽입해야 하는 위치는 left가 됩니다.

이진 탐색을 사용하여 이 문제를 해결하면 O(log n)의 시간 복잡도로 효율적으로 해결할 수 있습니다.

오늘의 회고

• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자
• 새로운 개념을 배울수 있어서 좋았다.

오늘의 공부 키워드

• 1025 Divisor Game

1025 Divisor Game

디바이저 게임에서는 앨리스와 밥이 차례로 게임을 합니다. 게임 규칙은 다음과 같습니다:

1. 게임은 숫자 nnn으로 시작합니다. 앨리스가 먼저 시작합니다.
2. 각 턴마다 플레이어는 0<x<n0 < x < n0<x<n이면서 n%x==0n \% x == 0n%x==0인 숫자 xxx를 선택해야 합니다. (즉, xxx는 nnn의 약수여야 합니다.)
3. 선택한 숫자 xxx를 nnn에서 빼고, 새로운 nnn값으로 바꿉니다.
4. 더 이상 움직일 수 없는 플레이어가 게임에서 집니다.

목표

게임이 시작할 때 n이 주어졌을 때, 앨리스가 이길 수 있는지 여부를 판단해야 합니다. (두 플레이어 모두 최적으로 게임을 한다고 가정합니다.)

핵심 통찰

게임의 결과는 숫자 n이 짝수인지 홀수인지에 따라 달라집니다:

• n이 짝수일 때, 앨리스는 항상 밥에게 홀수를 남기도록 만들 수 있습니다. 모든 짝수는 최소 하나의 약수(1)를 가지기 때문에, 앨리스는 항상 움직일 수 있습니다.
• n이 홀수일 때, 앨리스가 어떤 움직임을 하든 밥에게 짝수를 남기게 됩니다. 이 경우 밥이 유리하게 됩니다.

따라서, nnn이 짝수로 시작하면 앨리스가 이기고, 홀수로 시작하면 밥이 이깁니다.

예시

• 예시 1:
  • 입력: n=2
  • 앨리스는 1을 선택합니다 (2의 약수).
  • nnn은 2−1=1 이 됩니다.
  • 밥은 더 이상 움직일 수 없기 때문에 앨리스가 이깁니다.
  • 출력: true
• 예시 2:
  • 입력: n=3
  • 앨리스는 1을 선택합니다 (3의 약수).
  • nnn은 3−1 = 2 가 됩니다.
  • 밥은 1을 선택합니다 (2의 약수).
  • nnn은 2−1=1 이 됩니다.
  • 앨리스는 더 이상 움직일 수 없기 때문에 밥이 이깁니다.
  • 출력: false

해결 방법

앨리스가 이길 수 있는지 확인하려면 n 이 짝수인지 홀수인지 확인하면 됩니다.

코드

def divisor_game(n: int) -> bool:
    return n % 2 == 0

# 예시로 함수 테스트
print(divisor_game(2))  # 출력: True
print(divisor_game(3))  # 출력: False

설명

1. 함수 정의: divisor_game이라는 함수를 정의하고, 정수 n을 입력으로 받습니다.
2. 짝수/홀수 확인: 나머지 연산자 %를 사용하여 nnn이 짝수인지 확인합니다. 만약 n%2==0이면 n은 짝수이고, 함수는 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

이 해결 방법은 주어진 범위 1≤n≤1000내의 어떤 n에 대해서도 효율적으로 작동합니다.

오늘의 회고

• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자
• 재미있는 문제여서 풀기 좋았다.

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
...

오늘의 공부 키워드

• 피보나치수열
• 509. Fibonaci Number

피보나치 수열

피보나치 수열은 수학에서 매우 유명한 수열 중 하나로, 각 숫자가 그 앞의 두 숫자의 합으로 이루어진 수열입니다. 이 수열은 이탈리아의 수학자 피보나치(Leonardo of Pisa, 피사르 피보나치)에 의해 서양에 소개되었습니다. 피보나치 수열은 다음과 같은 규칙을 따릅니다

• 첫 번째 숫자 (F(0))는 0입니다.
• 두 번째 숫자 (F(1))는 1입니다.
• 세 번째 숫자부터는 이전 두 숫자의 합입니다. 즉, F(n) = F(n-1) + F(n-2) (n > 1인 경우).

피보나치 수열의 초기 값은 다음과 같습니다:

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
...

이 수열은 다음과 같이 시작됩니다: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

피보나치 수열의 특징

1. 재귀적 정의: 피보나치 수열은 간단한 재귀적 정의를 가지고 있습니다.
2. 기하학적 성질: 피보나치 수열은 황금비와 밀접한 관련이 있습니다. 두 연속된 피보나치 수의 비율은 황금비(약 1.618)에 점점 가까워집니다.
3. 자연과 예술에서의 응용: 피보나치 수열은 자연현상(예: 나선형 조개껍질, 해바라기 씨앗의 배열)과 예술작품에서 종종 발견됩니다.

피보나치 수열 대표적인 방법

1. 재귀적 방법

가장 간단한 방법으로, 피보나치 수열의 정의에 따라 재귀적으로 계산하는 방법입니다.

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        return self.fib(n - 1) + self.fib(n - 2)

• 장점: 구현이 매우 간단합니다.
• 단점: 같은 계산을 반복하기 때문에 시간 복잡도가 O(2^n)으로 매우 비효율적입니다.

2. 메모이제이션 (재귀적 방법의 개선)

재귀적 방법의 단점을 보완하기 위해 메모이제이션을 사용하여 이미 계산된 값을 저장합니다.

class Solution:
    def __init__(self):
        self.memo = {}
    
    def fib(self, n: int) -> int:
        if n in self.memo:
            return self.memo[n]
        if n <= 1:
            return n
        self.memo[n] = self.fib(n - 1) + self.fib(n - 2)
        return self.memo[n]

• 장점: 중복 계산을 피할 수 있어서 시간 복잡도가 O(n)으로 개선됩니다.
• 단점: 추가적인 메모리 공간이 필요합니다.

3. 반복적 방법

반복문을 사용하여 피보나치 수를 계산하는 방법입니다

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b

• 장점: 시간 복잡도가 O(n)으로 효율적이며, 추가적인 메모리 공간이 거의 필요하지 않습니다.
• 단점: 코드가 재귀적 방법보다 조금 복잡합니다.

4. 동적 프로그래밍 (탑다운 접근법)

DP 배열을 사용하여 각 피보나치 수를 저장하면서 계산하는 방법입니다.

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

• 장점: 중복 계산을 피할 수 있고, 코드가 직관적입니다.
• 단점: O(n)의 추가 메모리 공간이 필요합니다.

5. 행렬 제곱 방법

피보나치 수열을 행렬을 사용해 계산하는 방법으로, 시간 복잡도가 O(log n)입니다.

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        
        def matrix_mult(A, B):
            return [
                [A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]],
                [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]
            ]
        
        def matrix_pow(M, power):
            result = [[1, 0], [0, 1]]
            base = M
            while power:
                if power % 2 == 1:
                    result = matrix_mult(result, base)
                base = matrix_mult(base, base)
                power //= 2
            return result
        
        F = [[1, 1], [1, 0]]
        result = matrix_pow(F, n - 1)
        return result[0][0]

• 장점: 시간 복잡도가 O(log n)으로 매우 효율적입니다.
• 단점: 코드가 복잡하며, 행렬 연산을 이해해야 합니다.

509 Fibonaci Number

피보나치 수열은 각 숫자가 이전 두 숫자의 합으로 구성된 수열입니다. 이 문제에서는 주어진 n에 대해 피보나치 수 F(n)을 계산하는 방법을 찾고자 합니다. 피보나치 수열은 다음과 같이 정의됩니다:

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 1) + F(n - 2) (n > 1인 경우)

이를 바탕으로 몇 가지 예제를 살펴보겠습니다:

예제 1:

• 입력: n = 2
• 출력: 1
• 설명: F(2) = F(1) + F(0) = 1 + 0 = 1

예제 2:

• 입력: n = 3
• 출력: 2
• 설명: F(3) = F(2) + F(1) = 1 + 1 = 2

예제 3:

• 입력: n = 4
• 출력: 3
• 설명: F(4) = F(3) + F(2) = 2 + 1 = 3

문제 해결 방법

이 문제를 해결하기 위해 두 가지 방법을 고려할 수 있습니다: 재귀적 방법과 반복적 방법. 여기서는 반복적 방법을 사용하여 효율적으로 피보나치 수를 계산하겠습니다.

반복적 방법

반복적 방법은 시간 복잡도가 O(n)으로, 재귀적 방법보다 더 효율적입니다. 다음과 같은 단계를 따릅니다:

1. F(0)과 F(1)을 초기화합니다.
2. 반복문을 통해 F(2)부터 F(n)까지의 값을 계산합니다.
3. 최종적으로 F(n)을 반환합니다.

코드

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b

코드 설명:

1. n이 0인 경우 0을 반환합니다.
2. n이 1인 경우 1을 반환합니다.
3. a와 b를 각각 0과 1로 초기화합니다.
4. for 반복문을 통해 n까지 반복하면서 a와 b를 업데이트합니다. a는 이전 값, b는 현재 값이 됩니다.
5. 반복이 끝난 후, b는 F(n)의 값이 됩니다.

이 코드를 사용하면 주어진 n에 대해 피보나치 수를 효율적으로 계산할 수 있습니다.

오늘의 회고

• 새로운 개념인 피보나치 수열을 배울수 있었다.
• 좀더 끈질기게 고민하고 문제를 풀어야 하는데 쉽게 포기하는게 아닌가 하고 반성하게 된다.
• 코딩테스트 문제만 풀지말고 기록도 남겨야 함을 느낀다.
• 공부할것은 더욱 많음을 느낀다.
• 문제를 지금 거의 풀수는 없지만 복습하고 복습하고 복습하기 위해 기록을 남긴다.
• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자

오늘의 공부 키워드

• 동적계획법
• 118. Pascal`s Triangle

118. Pascal`s Triangle

문제 해석

파스칼의 삼각형(Pascal's Triangle)은 삼각형 모양의 배열로, 각 숫자는 바로 위 두 숫자의 합으로 구성됩니다. 주어진 numRows 정수는 파스칼의 삼각형에서 몇 줄까지 출력할지를 나타냅니다. 예를 들어, numRows = 5이면 다음과 같은 형태가 됩니다:

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

풀이 방법

1. Solution 클래스의 generate 메서드는 numRows를 입력으로 받아 파스칼의 삼각형의 처음 numRows 줄을 반환합니다.
2. 파스칼의 삼각형을 저장할 빈 리스트를 생성합니다.
3. 각 줄을 순차적으로 생성하여 파스칼의 삼각형 리스트에 추가합니다.
4. 각 줄은 처음과 끝이 1로 시작하며, 중간의 값들은 이전 줄의 인접한 두 값의 합으로 계산됩니다.
5. 주어진 numRows만큼 반복하여 모든 줄을 생성합니다.

코드

from typing import List

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        # 파스칼 삼각형을 저장할 리스트 초기화
        triangle = []
        
        for i in range(numRows):
            # 현재 줄을 저장할 리스트 초기화
            row = [None for _ in range(i + 1)]
            # 첫 번째와 마지막 원소는 항상 1
            row[0], row[-1] = 1, 1
            
            # 중간 원소는 이전 줄의 두 원소의 합
            for j in range(1, len(row) - 1):
                row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
            
            # 현재 줄을 파스칼 삼각형에 추가
            triangle.append(row)
        
        return triangle

세부 설명

1.파스칼 삼각형 리스트 초기화:

triangle = []

2. 반복문을 통한 줄 생성:

for i in range(numRows):

3. 각 줄 초기화 및 첫 번째와 마지막 원소 설정:

row = [None for _ in range(i + 1)]
row[0], row[-1] = 1, 1

• 각 줄을 [None]으로 초기화하고, 첫 번째와 마지막 원소를 1로 설정합니다.

4.중간 원소 계산:

for j in range(1, len(row) - 1):
    row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]

5.현재 줄을 파스칼 삼각형에 추가:

triangle.append(row)

6. 결과 반환:

return triangle

생성된 파스칼 삼각형을 반환합니다.

이와 같은 방식으로 주어진 numRows에 대해 파스칼의 삼각형을 생성할 수 있습니다.

오늘의 회고

• 동적계획법의 다른 방법을 배울수 있었습니다..
• 문제를 좀더 끈질기게 집요하게 매달려봐야겠다.
• 코드 리뷰와 문제 이해는 정말 중요한거 같다.
• 코딩테스트 문제만 풀지말고 기록하자
• 공부할것은 더욱 많음을 느낀다.
• 문제를 지금 거의 풀수는 없지만 복습하고 복습하고 복습하기 위해 기록을 남긴다.
• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자

오늘의 공부 키워드

• 동적계획법의 개념
• 338. Counting Bits

동적 계획법의 개념

동적 계획법(Dynamic Programming, DP)은 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 재사용함으로써 전체 문제를 효율적으로 해결하는 방법입니다. 이 문제에서는 각 숫자 iii의 이진 표현에서 1의 개수를 계산할 때, 이전에 계산한 결과를 재사용하여 중복 계산을 피할 수 있습니다.

338. Counting Bits

문제 해석

주어진 정수 n이 있을 때, 길이가 n+1인 배열 ans를 반환하는 문제입니다. 배열 ans는 다음과 같은 조건을 만족해야 합니다: 각 iii (0 <= i <= n)에 대해, ans[i]는 iii의 이진 표현에서 1의 개수입니다.

예시

• 입력: n=2
• 출력: [0,1,1][0, 1, 1][0,1,1]
  • 설명:
    • 0 -> 0 (이진수: 0, 1의 개수: 0)
    • 1 -> 1 (이진수: 1, 1의 개수: 1)
    • 2 -> 10 (이진수: 10, 1의 개수: 1)
• 입력: n=5n = 5n=5
• 출력: [0,1,1,2,1,2]
  • 설명:
    • 0 -> 0 (이진수: 0, 1의 개수: 0)
    • 1 -> 1 (이진수: 1, 1의 개수: 1)
    • 2 -> 10 (이진수: 10, 1의 개수: 1)
    • 3 -> 11 (이진수: 11, 1의 개수: 2)
    • 4 -> 100 (이진수: 100, 1의 개수: 1)
    • 5 -> 101 (이진수: 101, 1의 개수: 2)

제약 조건

• 0≤n≤105

추가 도전 과제

• 시간 복잡도를 O(nlog⁡n)이 아닌 O(n)으로 줄일 수 있는지 확인합니다.
• 내장 함수(__builtin_popcount와 같은)를 사용하지 않고 문제를 풀 수 있는지 확인합니다.

문제 풀이 방법

이 문제를 풀기 위한 최선의 방법은 동적 계획법(DP)을 이용하는 것입니다. 각 숫자 iii에 대해, iii가 짝수인지 홀수인지에 따라 1의 개수를 다르게 계산할 수 있습니다.

• 짝수 iii: 이진수로 나타낸 iii는 마지막 비트가 0입니다. 따라서 iii를 2로 나눈 몫의 1의 개수와 동일합니다. 즉, ans[i]=ans[i//2]입니다.
• 홀수 iii: 이진수로 나타낸 iii는 마지막 비트가 1입니다. 따라서 iii를 2로 나눈 몫의 1의 개수에 1을 더한 값과 같습니다. 즉, ans[i//2]+1입니다.

이 규칙을 이용하면 시간 복잡도 O(n)에 문제를 해결할 수 있습니다.

코드 설명

def countBits(n):
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        ans[i] = ans[i >> 1] + (i & 1)
    return ans

# 예시 테스트
print(countBits(2))  # [0, 1, 1]
print(countBits(5))  # [0, 1, 1, 2, 1, 2]

코드 설명

1. 배열 ans를 크기 n+1n + 1n+1로 초기화합니다.
2. 1부터 nnn까지 반복하면서 각 숫자에 대해 1의 개수를 계산하여 ans에 저장합니다.
   • i >> 1은 i를 2로 나눈 몫입니다.
   • i & 1은 i의 마지막 비트가 1인지 0인지를 나타냅니다.
3. 최종적으로 배열 ans를 반환합니다.

오늘의 회고

• 새로운 개념인 동적계획법을 배울수 있었다.
• 좀더 끈질기게 고민하고 문제를 풀어야 하는데 쉽게 포기하는게 아닌가 하고 반성하게 된다.
• 코드 리뷰와 문제 이해는 정말 중요한거 같다.
• 코딩테스트 문제만 풀지말고 기록도 남겨야 함을 느낀다.
• 공부할것은 더욱 많음을 느낀다.
• 문제를 지금 거의 풀수는 없지만 복습하고 복습하고 복습하기 위해 기록을 남긴다.
• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자

오늘의 공부 키워드

• 탐욕법(greedy)
• 1221. Split a String in Balanced Strings

문제 해석

문제는 'L'과 'R' 문자가 같은 수만큼 있는 문자열 s가 주어졌을 때, 이를 'L'과 'R'이 같은 수만큼 포함된 부분 문자열들로 최대 몇 개로 나눌 수 있는지를 찾는 것입니다.

문제 해결 방법

1. 균형잡힌 문자열: 문자열이 균형잡혔다면, 'L'과 'R'의 수가 동일하다는 뜻입니다. 예를 들어 "RL", "RLRL", "RRLL" 등이 있습니다.
2. 부분 문자열 나누기: 주어진 문자열을 여러 개의 균형잡힌 부분 문자열로 나눠야 합니다. 예를 들어 "RLRRLLRLRL"을 "RL", "RRLL", "RL", "RL"로 나누면 각 부분 문자열이 'L'과 'R'이 동일한 수를 가집니다.

해결 방법 단계별 설명

1. 카운터 변수 사용: 'L'과 'R'의 개수를 세기 위해 카운터 변수를 사용합니다.
2. 부분 문자열 나누기: 문자열을 순서대로 탐색하면서 'L'을 만나면 카운터를 증가시키고, 'R'을 만나면 카운터를 감소시킵니다. 카운터가 0이 되는 순간, 하나의 균형잡힌 부분 문자열을 찾았음을 의미합니다.
3. 결과 값 증가: 카운터가 0이 될 때마다 결과 값을 증가시킵니다.

코드 설명

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        balance = 0
        count = 0

        for char in s:
            if char == 'R':
                balance -= 1
            else:  # char == 'L'
                balance += 1
            
            if balance == 0:
                count += 1
        
        return count

코드 설명

1. 클래스 정의: class Solution을 정의합니다.
2. 메서드 정의: 클래스 내부에 balancedStringSplit이라는 메서드를 정의합니다. 이 메서드는 문자열 s를 매개변수로 받아 균형잡힌 문자열의 최대 개수를 반환합니다.
3. 변수 초기화:
   • balance: 'L'과 'R'의 균형을 맞추기 위한 변수입니다. 초기값은 0입니다.
   • count: 균형잡힌 문자열의 개수를 세기 위한 변수입니다. 초기값은 0입니다.
4. 문자열 순회:
   • for char in s: 문자열 s의 각 문자를 하나씩 순회합니다.
5. 균형 맞추기:
   • if char == 'R': 현재 문자가 'R'인 경우, balance를 1 감소시킵니다.
   • else: 현재 문자가 'L'인 경우, balance를 1 증가시킵니다.
6. 균형잡힌 문자열 찾기:
   • if balance == 0: balance가 0이 되는 순간, 균형잡힌 문자열을 찾은 것입니다.
   • count += 1: 균형잡힌 문자열을 찾았으므로 count를 1 증가시킵니다.
7. 결과 반환:
   • return count: 최종적으로 찾은 균형잡힌 문자열의 개수를 반환합니다.

예시사용법

# 예시 입력
s1 = "RLRRLLRLRL"
s2 = "RLRRRLLRLL"
s3 = "LLLLRRRR"

solution = Solution()
print(solution.balancedStringSplit(s1))  # 출력: 4
print(solution.balancedStringSplit(s2))  # 출력: 2
print(solution.balancedStringSplit(s3))  # 출력: 1

이 코드를 통해 주어진 문자열 s를 최대한 많은 균형잡힌 문자열로 나눌 수 있습니다. 각 문자에 따라 균형을 맞추고, 균형이 맞을 때마다 개수를 세어 최종 결과를 반환합니다.

오늘의 공부 키워드

• 탐욕법(greedy)에 대한 개념
• 프로그래머스 체육복 문제 풀이

탐욕법(greedy)

탐욕법(Greedy Algorithm)은 최적해를 구하는 알고리즘 설계 기법 중 하나로, 각 단계에서 현재 상황에서 가장 좋다고 생각되는 선택을 하는 방법입니다. 이 방법은 전체 문제를 해결하기 위한 전역 최적해(global optimal solution)가 아닌, 각 단계에서의 지역 최적해(local optimal solution)를 선택함으로써 문제를 해결하려고 합니다.

탐욕법의 기본 아이디어

탐욕법은 다음과 같은 방식으로 작동합니다:

1. 현재 상태에서 최선의 선택을 한다: 현재 상황에서 가장 좋다고 생각되는 선택을 합니다.
2. 선택을 확정하고, 이를 기반으로 다음 상태로 이동한다: 현재 선택이 전체 문제에 어떻게 영향을 미칠지에 대해 신경 쓰지 않고, 다음 단계로 이동합니다.
3. 이 과정을 반복한다: 최종적으로 문제를 해결할 때까지 반복합니다.

탐욕법의 특징

• 단순함: 각 단계에서 최선의 선택을 하므로 구현이 간단합니다.
• 빠름: 각 단계에서의 선택이 한 번에 이루어지므로 일반적으로 시간 복잡도가 낮습니다.
• 최적해 보장 여부: 탐욕법이 항상 최적해를 보장하지는 않습니다. 문제의 특성에 따라 전역 최적해를 보장할 수도 있고, 그렇지 않을 수도 있습니다. 탐욕법이 최적해를 보장하려면 특정 조건(예: 탐욕적 선택 속성, 최적 부분 구조)이 만족되어야 합니다.

탐욕법의 적용 예시

탐욕법은 여러 문제에서 효과적으로 사용됩니다. 대표적인 예시로는 다음이 있습니다:

1. 거스름돈 문제:
   • 거스름돈을 줄 때 동전의 수를 최소화하기 위해 가장 큰 단위의 동전부터 거슬러 주는 방법입니다.
2. 최소 신장 트리(MST, Minimum Spanning Tree):
   • 그래프에서 모든 정점을 연결하는 최소 비용의 트리를 찾기 위해 사용하는 Kruskal 알고리즘이나 Prim 알고리즘이 탐욕법을 사용합니다.
3. 활동 선택 문제(Activity Selection Problem):
   • 주어진 활동들의 시작 시간과 종료 시간 중에서 가장 많은 활동을 선택하는 문제에서 각 단계마다 가장 빨리 끝나는 활동을 선택하는 방법입니다.

체육복

문제 해석

1. 학생들의 번호는 체격 순으로 매겨져 있습니다.
2. 도난당한 학생(lost)은 체육복이 없어서 수업을 들을 수 없습니다.
3. 여벌의 체육복을 가진 학생(reserve)은 도난당한 학생들에게 체육복을 빌려줄 수 있습니다.
4. 여벌의 체육복을 가진 학생도 도난당한 경우, 본인의 체육복이 하나 남기 때문에 다른 학생에게 빌려줄 수 없습니다.
5. 한 학생은 자신의 바로 앞번호나 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.

접근 방법

1. 여벌의 체육복을 가진 학생이 도난당한 경우 처리:
   • 여벌의 체육복을 가진 학생(reserve) 목록과 도난당한 학생(lost) 목록에서 공통으로 포함된 학생을 찾아 처리합니다. 이들은 체육복이 하나 남기 때문에 빌려줄 수 없습니다.
2. 도난당한 학생들에게 체육복 빌려주기:
   • 도난당한 학생을 순회하면서 앞번호 학생(reserve - 1)이나 뒷번호 학생(reserve + 1)에게 빌릴 수 있는지 확인하고 빌려줍니다.
3. 최종적으로 체육수업을 들을 수 있는 학생 수 계산:
   • 도난당한 학생(lost) 중 체육복을 빌린 학생을 제외하고 나머지 학생 수를 전체 학생 수(n)에서 빼면 체육수업을 들을 수 있는 학생 수가 됩니다.

코드 설명

def solution(n, lost, reserve):
    # 여벌 체육복을 가진 학생이 도난당한 경우 처리
    reserve_set = set(reserve) - set(lost)
    lost_set = set(lost) - set(reserve)

    # 체육복을 빌려주기
    for r in sorted(reserve_set):
        if r - 1 in lost_set:
            lost_set.remove(r - 1)
        elif r + 1 in lost_set:
            lost_set.remove(r + 1)

    # 체육수업을 들을 수 있는 학생 수
    return n - len(lost_set)

# 테스트 예제
print(solution(5, [2, 4], [1, 3, 5]))  # 5
print(solution(5, [2, 4], [3]))        # 4
print(solution(3, [3], [1]))           # 2

설명

1. reserve_set = set(reserve) - set(lost)와 lost_set = set(lost) - set(reserve):
   • 여벌 체육복을 가진 학생 중에서 도난당하지 않은 학생과 도난당했지만 여벌 체육복이 없는 학생을 구분합니다.
2. for r in sorted(reserve_set):
   • 여벌 체육복을 가진 학생들을 순회하면서 앞번호 학생이나 뒷번호 학생에게 체육복을 빌려줍니다.
3. lost_set.remove(r - 1) 또는 lost_set.remove(r + 1):
   • 체육복을 빌려준 학생을 도난당한 학생 목록에서 제거합니다.
4. n - len(lost_set):
   • 전체 학생 수에서 체육복이 없는 학생 수를 뺀 값을 반환하여 체육수업을 들을 수 있는 학생 수를 계산합니다.

오늘의 공부 키워드

• 이진검색 트리(BST) 트리 최대 깊이 관련 내용 
• 104 Maximum Depth of Binary Tree
• 재귀함수의 개념

104 Maximum Depth of Binary Tree

문제 해석

이진 트리의 최대 깊이는 루트 노드부터 가장 멀리 있는 리프(leaf) 노드까지의 노드 수를 의미합니다. 즉, 루트 노드에서 가장 아래쪽에 있는 노드까지 가는 경로 중에서 가장 긴 경로의 노드 개수를 구하면 됩니다.

문제 예시

1. 예시 1:
   • 입력: root = [3, 9, 20, null, null, 15, 7]
   • 출력: 3
   • 설명: 이 트리는 다음과 같습니다

    3
   / \
  9  20
     / \
    15  7

2. 예시 2:

• 입력: root = [1, null, 2]
• 출력: 2
• 설명: 이 트리는 다음과 같습니다

    1
     \
      2

문제 풀이 방법

이 문제를 풀기 위해서는 재귀(Recursive) 함수를 사용하는 방법이 효과적입니다. 이진 트리의 각 노드에 대해 왼쪽 자식 노드와 오른쪽 자식 노드의 깊이를 재귀적으로 계산한 다음, 두 깊이 중 더 큰 값에 1을 더하면 현재 노드의 깊이가 됩니다.

코드설명

# 이진 트리의 노드를 나타내는 클래스
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 최대 깊이를 계산하는 함수
def maxDepth(root):
    # 만약 노드가 없으면 깊이는 0
    if root is None:
        return 0
    
    # 왼쪽과 오른쪽 자식 노드의 깊이를 재귀적으로 계산
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    
    # 현재 노드의 깊이는 자식 노드 깊이 중 큰 값에 1을 더한 값
    return max(left_depth, right_depth) + 1

코드 설명

1. TreeNode 클래스: 이 클래스는 이진 트리의 노드를 나타냅니다. 각 노드는 값(val), 왼쪽 자식 노드(left), 오른쪽 자식 노드(right)를 가집니다.
2. maxDepth 함수: 이 함수는 주어진 이진 트리의 최대 깊이를 계산합니다.
   • 기본 조건: 만약 노드가 없으면(즉, root가 None이면) 깊이는 0입니다.
   • 재귀 호출: 왼쪽 자식 노드와 오른쪽 자식 노드의 깊이를 각각 재귀적으로 계산합니다.
   • 현재 노드의 깊이 계산: 왼쪽 깊이와 오른쪽 깊이 중 더 큰 값에 1을 더한 값을 반환합니다. 여기서 1을 더하는 이유는 현재 노드 자체도 깊이에 포함되기 때문입니다.

재귀 함수란?

재귀 함수는 자기 자신을 다시 호출하는 함수예요. 좀 더 쉽게 말하면, 함수 안에서 자기 자신을 또 다시 부르는 함수를 재귀 함수라고 해요.

예시로 이해하기

    3
   / \
  9  20
     /  \
    15   7

1. 루트 노드 3에서 maxDepth(3)을 호출해요.
2. maxDepth(3)는 maxDepth(9)와 maxDepth(20)을 호출해요.
3. maxDepth(9)는 자식이 없어서 1을 반환해요.
4. maxDepth(20)는 maxDepth(15)와 maxDepth(7)을 호출해요.
5. maxDepth(15)와 maxDepth(7)은 자식이 없어서 각각 1을 반환해요.
6. maxDepth(20)는 1 + max(1, 1) = 2를 반환해요.
7. 마지막으로 maxDepth(3)는 1 + max(1, 2) = 3을 반환해요.

오늘의 회고

• 이진 검색 트리의 문제에서 최대 깊이의 문제를 풀었다.
• 재귀 함수의 개념에 대해서 익힐수 있었다.
• 코드 리뷰라고 하더라도 문제를 이해하는게 정말 중요함을 느낀다.
• 코딩테스트 문제만 풀지말고 기록도 남겨야 함을 느낀다.
• LV1의 문제라지만 생각을 많이 하는 문제는 정말 좋은거 같다.