공부블로그

오늘의 공부 키워드

• 동적계획법
• 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의 문제라지만 생각을 많이 하는 문제는 정말 좋은거 같다.