공부블로그

오늘의 공부 키워드

• 브루트 포스의 개념
• 해시맵의 개념
• 1512 Number of Good Pairs

브루트포스

브루트 포스(Brute Force)는 컴퓨터 알고리즘 문제를 해결하는 데 사용되는 단순하고 직관적인 방법입니다. 브루트 포스 방법은 가능한 모든 경우의 수를 모두 시도해 보는 방식으로 문제를 해결합니다. 이러한 방법은 종종 가장 간단하고 명확한 접근 방식이지만, 경우의 수가 많아지면 매우 비효율적일 수 있습니다.

브루트 포스 방법의 장단점은 다음과 같습니다:

장점

1. 단순함: 구현이 매우 간단하고 직관적입니다.
2. 보편성: 어떤 문제든 적용할 수 있습니다.

단점

1. 비효율성: 경우의 수가 많아질수록 실행 시간이 급격히 증가합니다. 시간 복잡도가 매우 높아질 수 있습니다.
2. 자원 소모: 많은 연산을 필요로 하므로 메모리와 CPU 자원을 많이 소모할 수 있습니다.

해시맵

해시맵(Hash Map)은 데이터를 키-값(key-value) 쌍으로 저장하는 데이터 구조입니다. 해시맵은 해싱(Hashing)이라는 기술을 사용하여 데이터를 빠르게 검색, 삽입, 삭제할 수 있습니다. 해시맵은 파이썬에서는 dict로 구현되어 있으며, 매우 효율적인 평균 시간 복잡도 O(1)의 검색, 삽입, 삭제 연산을 제공합니다.

해시맵의 특징

1. 키-값 쌍:
   • 데이터를 고유한 키를 통해 저장하고, 해당 키를 통해 데이터를 빠르게 검색할 수 있습니다.
2. 해싱:
   • 키를 해시 함수(hash function)에 넣어 해시값(hash value)을 생성하고, 이를 이용해 데이터의 저장 위치를 결정합니다.
   • 해시 함수는 일반적으로 입력 데이터의 특성을 잘 분산시켜 충돌을 최소화하는 역할을 합니다.
3. 충돌 해결:
   • 두 개 이상의 키가 같은 해시값을 가질 때(해시 충돌), 이를 해결하기 위해 체이닝(Chaining)이나 오픈 어드레싱(Open Addressing) 등의 방법을 사용합니다.

1512 Number of Good Pairs

정수 배열 nums가 주어졌을 때, "좋은 쌍(good pairs)"의 개수를 반환하는 문제입니다.

좋은 쌍 (i, j)는 다음과 같은 조건을 만족합니다:

• nums[i] == nums[j]
• i < j

예제 1:

• 입력: nums = [1, 2, 3, 1, 1, 3]
• 출력: 4
• 설명: 좋은 쌍은 (0, 3), (0, 4), (3, 4), (2, 5) 이므로 총 4개입니다.

예제 2:

• 입력: nums = [1, 1, 1, 1]
• 출력: 6
• 설명: 배열의 모든 쌍이 좋은 쌍입니다.

예제 3:

• 입력: nums = [1, 2, 3]
• 출력: 0
• 설명: 좋은 쌍이 없습니다.

코드

from typing import List
from collections import defaultdict

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        count = 0
        freq = defaultdict(int)
        
        for num in nums:
            if num in freq:
                count += freq[num]
            freq[num] += 1
        
        return count

# 예제 입력 테스트
solution = Solution()
print(solution.numIdenticalPairs([1, 2, 3, 1, 1, 3]))  # 출력: 4
print(solution.numIdenticalPairs([1, 1, 1, 1]))        # 출력: 6
print(solution.numIdenticalPairs([1, 2, 3]))           # 출력: 0

코드 설명

1. 필요한 모듈 임포트:
   • List 타입을 사용하기 위해 typing 모듈에서 List를 임포트합니다.
   • defaultdict을 사용하기 위해 collections 모듈에서 defaultdict을 임포트합니다.
2. Solution 클래스 정의:
   • numIdenticalPairs 메서드는 List[int] 타입의 nums를 인자로 받아 int 타입의 결과를 반환합니다.
3. numIdenticalPairs 메서드:
   • count: 좋은 쌍의 개수를 저장하는 변수입니다.
   • freq: 각 숫자의 빈도를 저장하는 defaultdict(int)입니다.
   • 배열을 순회하면서 현재 숫자가 이전에 몇 번 나왔는지 확인하고, 그 빈도 수를 count에 더해줍니다.
   • 현재 숫자의 빈도를 1 증가시킵니다.
   • 배열 순회가 끝나면 count를 반환합니다.

이렇게 작성된 코드는 주어진 nums 배열에 대해 좋은 쌍의 개수를 효율적으로 계산합니다.

오늘의 회고

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

오늘의 공부 키워드

• 1470 Shuffle the Array

1470 Shuffle the Array

주어진 배열 nums는 2n개의 요소로 구성되어 있으며, [x1, x2, ..., xn, y1, y2, ..., yn] 형태입니다.

배열을 [x1, y1, x2, y2, ..., xn, yn] 형태로 변환하여 반환하세요.

예제 1:

입력: nums = [2, 5, 1, 3, 4, 7], n = 3

출력: [2, 3, 5, 4, 1, 7]

설명: x1=2, x2=5, x3=1, y1=3, y2=4, y3=7이므로 결과는 [2, 3, 5, 4, 1, 7]입니다.

예제 2:

입력: nums = [1, 2, 3, 4, 4, 3, 2, 1], n = 4

출력: [1, 4, 2, 3, 3, 2, 4, 1]

예제 3: 입력: nums = [1, 1, 2, 2], n = 2

출력: [1, 2, 1, 2]

제약사항:

• 1 <= n <= 500
• nums.length == 2n
• 1 <= nums[i] <= 10^3

풀이 방법:

1. 결과를 저장할 빈 배열 result를 초기화합니다.
2. 인덱스 i를 0부터 n-1까지 반복합니다.
3. 각 반복에서 nums의 앞쪽 절반에서 x 값을, 뒷쪽 절반에서 y 값을 번갈아가며 result 배열에 추가합니다.
4. 결과 배열을 반환합니다.

코드

def shuffle(nums, n):
    result = []
    for i in range(n):
        result.append(nums[i])       # x 값을 추가
        result.append(nums[i + n])   # y 값을 추가
    return result

# 예제 실행
print(shuffle([2, 5, 1, 3, 4, 7], 3))  # [2, 3, 5, 4, 1, 7]
print(shuffle([1, 2, 3, 4, 4, 3, 2, 1], 4))  # [1, 4, 2, 3, 3, 2, 4, 1]
print(shuffle([1, 1, 2, 2], 2))  # [1, 2, 1, 2]

오늘의 회고

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

오늘의 공부 키워드

• 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)의 시간 복잡도로 효율적으로 해결할 수 있습니다.

오늘의 회고

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

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를 최대한 많은 균형잡힌 문자열로 나눌 수 있습니다. 각 문자에 따라 균형을 맞추고, 균형이 맞을 때마다 개수를 세어 최종 결과를 반환합니다.