공부블로그

오늘의 공부 키워드

• 이진검색 트리(BST) 구조 반전
• 226 Invert Binary Tree

226 . Invert Binanay Tree

문제 해석

"Binary Tree Invert" 문제는 주어진 이진 트리(Binary Tree)의 구조를 반전시키는 문제입니다. 이진 트리란 각 노드가 최대 두 개의 자식을 가지는 트리입니다. 이 문제에서 반전이란 왼쪽 자식과 오른쪽 자식을 서로 바꾸는 것을 의미합니다.

    4
   / \
  2   7
 / \ / \
1  3 6  9

    4
   / \
  7   2
 / \ / \
9  6 3  1

문제 해결 방법

이 문제를 해결하기 위해, 다음의 단계들을 따릅니다:

1. 기본 아이디어: 트리의 각 노드에 대해, 그 노드의 왼쪽 자식과 오른쪽 자식을 서로 교환합니다.
2. 재귀 함수 사용: 트리 구조는 재귀적으로 정의되므로, 각 노드에 대해 재귀적으로 왼쪽과 오른쪽 자식을 교환하는 방법을 사용할 수 있습니다.

단계별 해결 방법

1. 기본 케이스: 현재 노드가 None인 경우(즉, 트리가 비어 있거나 리프 노드의 자식인 경우), 그대로 None을 반환합니다.
2. 재귀적 호출: 현재 노드의 왼쪽 자식과 오른쪽 자식을 서로 교환하고, 각각의 자식에 대해 다시 이 과정을 재귀적으로 수행합니다.

코드설명

from typing import Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 트리가 비어 있는 경우
        if root is None:
            return None
        
        # 왼쪽과 오른쪽 자식을 교환합니다.
        root.left, root.right = root.right, root.left
        
        # 재귀적으로 각 자식에 대해 invertTree를 호출합니다.
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        return root

코드 설명

1. 주어진 이진 트리가 비어 있는지 확인합니다. 비어 있다면 None을 반환합니다.
2. 현재 노드의 왼쪽 자식과 오른쪽 자식을 교환합니다.
3. 왼쪽 자식과 오른쪽 자식에 대해 재귀적으로 invertTree 메서드를 호출하여 각각의 하위 트리를 반전시킵니다.
4. 최종적으로 반전된 트리의 루트 노드를 반환합니다.

이 알고리즘은 모든 노드에 대해 한 번씩 방문하므로, 시간 복잡도는 O(n)이며, 여기서 n은 트리의 노드 수입니다.

오늘의 회고

• 이진 검색 트리의 문제가 정말 많다는걸 느꼈다.
• 이진 검색 트리를 정말 잘 익혀야 한다는 생각이 든다.
• 여전히 개념에 대한 이해가 안되어 코드 리뷰 수준으로 문제를 푼점은 다시한번 아쉽게 된다.
• 그래도 이렇게 기록으로 남기는건 나중에 다시한번 풀어보려는 이유 및
    어떻게 풀었는지 알기 위해서 기록을 남긴다.
• LV1의 문제라지만 생각을 많이 하는 문제는 정말 좋은거 같다.

오늘의 공부 키워드

• 이진검색 트리(BST) 새로운 문제
• 2331 Evaluate Boolean Binary Tree

LeetCode 2331 Evaluate Boolean Binary Tree

문제 설명

주어진 문제는 이진 트리를 평가하여 그 결과를 반환하는 것입니다. 이진 트리는 다음과 같은 특징을 가지고 있습니다:

1. 리프 노드 (Leaf nodes): 자식이 없는 노드로 값이 0 또는 1입니다. 여기서 0은 False(거짓), 1은 True(참)을 나타냅니다.
2. 비 리프 노드 (Non-leaf nodes): 자식이 있는 노드로 값이 2 또는 3입니다. 2는 논리 OR 연산을 나타내고, 3은 논리 AND 연산을 나타냅니다.

이진 트리 평가는 다음과 같이 이루어집니다:

• 리프 노드의 경우, 그 값이 평가 결과가 됩니다.
• 비 리프 노드의 경우, 두 자식 노드를 평가하고, 그 결과에 대해 해당 노드의 논리 연산(OR 또는 AND)을 적용합니다.

문제 해결

이 문제를 해결하기 위해서는 주어진 이진 트리를 재귀적으로 평가하는 방법을 사용합니다. 트리를 탐색하면서 각 노드를 평가하고, 그 결과를 반환합니다.

코드

# TreeNode 클래스를 정의합니다.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def evaluateTree(root):
    # 리프 노드일 경우, 그 값을 반환합니다.
    if root.left is None and root.right is None:
        return root.val == 1
    
    # 좌측과 우측 자식을 재귀적으로 평가합니다.
    left_val = evaluateTree(root.left)
    right_val = evaluateTree(root.right)
    
    # 비 리프 노드일 경우, 해당 연산을 수행합니다.
    if root.val == 2:  # OR 연산
        return left_val or right_val
    elif root.val == 3:  # AND 연산
        return left_val and right_val

# 예제 1
root1 = TreeNode(2)
root1.left = TreeNode(1)
root1.right = TreeNode(3, TreeNode(0), TreeNode(1))
print(evaluateTree(root1))  # 출력: True

# 예제 2
root2 = TreeNode(0)
print(evaluateTree(root2))  # 출력: False

코드 설명

1. TreeNode 클래스: 이진 트리의 노드를 정의하는 클래스입니다.
2. evaluateTree 함수: 트리를 재귀적으로 평가하는 함수입니다. 리프 노드인지 확인하고, 비 리프 노드일 경우 좌우 자식을 재귀적으로 평가하여 논리 연산을 수행합니다.
3. 예제 실행: 두 예제를 통해 함수를 테스트하고 결과를 출력합니다.

이 코드를 통해 주어진 이진 트리를 평가하여 그 결과를 반환할 수 있습니다.

오늘의 회고

• 이진 검색 트리를 다르게 푸는 방법을 알수 있어서 좋았다.
• 이진 검색 트리 새로운 문제가 많다는걸 다시한번 느껴서 도전 정신이 느껴진다.
• 여전히 개념에 대한 이해가 안되어 코드 리뷰 수준으로 문제를 푼점은 다시한번 아쉽게 된다.
• 그래도 이렇게 기록으로 남기는건 나중에 다시한번 풀어보려는 이유 및
    어떻게 풀었는지 알기 위해서 기록을 남긴다.
• LV1의 문제라지만 바로바로 문제를 풀지 못하는점은 아직도 아쉽다
• chat gpt로 코딩테스트 연습하는거도 좋다고 생각한다..

오늘의 공부 키워드

• 이진검색 트리(BST) 새로운 문제
• Leetcode 1379 Find a Corresponding Node a Binary Tree in a Clone of That Tree

Leetcode 1379 Find a Corresponding Node a Binary Tree in a Clone of That Tree

문제 설명

이 문제는 두 개의 이진 트리(original과 cloned)가 주어졌을 때, original 트리의 특정 노드(target 노드)에 대응하는 cloned 트리의 노드를 찾아 그 노드에 대한 참조를 반환하는 것입니다. 주어진 조건에 따라 트리의 구조와 노드의 값이 유일하다는 점을 고려해야 합니다.

입력

• 두 개의 이진 트리 (original과 cloned)
• original 트리의 특정 노드(target)

출력

• cloned 트리에서 original 트리의 target 노드와 동일한 위치에 있는 노드의 참조를 반환

예제

1. 예제 1:
   • 입력: tree = [7,4,3,null,null,6,19], target = 3
   • 출력: 3
   • 설명: original 트리에서 값이 3인 노드가 target 노드입니다. cloned 트리에서도 동일한 위치에 있는 노드가 반환됩니다.
2. 예제 2:
   • 입력: tree = [7], target = 7
   • 출력: 7
   • 설명: 트리가 하나의 노드만 가지고 있으므로, target 노드는 7입니다. cloned 트리에서도 동일한 노드를 반환합니다.
3. 예제 3:
   • 입력: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
   • 출력: 4
   • 설명: original 트리에서 값이 4인 노드가 target 노드입니다. cloned 트리에서도 동일한 위치에 있는 노드가 반환됩니다.

제약 조건

• 트리의 노드 수는 1 이상 10^4 이하입니다.
• 트리의 노드 값은 유일합니다.
• target 노드는 original 트리의 노드 중 하나이며 null이 아닙니다.

해결 방법

이 문제를 해결하기 위해 DFS(깊이 우선 탐색)나 BFS(너비 우선 탐색)를 사용하여 트리를 순회할 수 있습니다. 두 트리를 동시에 순회하면서 original 트리에서 target 노드를 찾을 때, 동일한 위치의 cloned 트리 노드를 반환합니다.

코드

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def getTargetCopy(original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
    if original is None:
        return None
    if original == target:
        return cloned
    left = getTargetCopy(original.left, cloned.left, target)
    if left is not None:
        return left
    return getTargetCopy(original.right, cloned.right, target)

코드 설명

1. original 노드와 cloned 노드를 동시에 탐색합니다.
2. original 노드가 target 노드와 같은 경우, cloned 노드를 반환합니다.
3. 왼쪽 서브트리를 먼저 탐색하고, 왼쪽에서 찾지 못하면 오른쪽 서브트리를 탐색합니다.

즉, 이 코드는 target 노드와 동일한 위치에 있는 cloned 트리의 노드를 반환합니다. 이로 인해 출력이 3이 되는 것입니다.

오늘의 회고

• 이진 검색 트리를 다르게 푸는 방법을 알수 있어서 좋았다.
• 여전히 개념에 대한 이해가 안되어 코드 리뷰 수준으로 문제를 푼점은 다시한번 아쉽게 된다.
• 그래도 이렇게 기록으로 남기는건 나중에 다시한번 풀어보고 어떻게 풀었는지 알기 위해서 기록을 남긴다.
• LV1의 문제라지만 바로바로 문제를 풀지 못하는점은 아직도 아쉽다.
• CODE UP 기초 문제도 순항중인데 다양한 인사이트를 얻고 있다.
• 좀더 파이썬에 대해서 공부를 해야할거같다.

오늘의 공부 키워드

• 이진검색 트리(BST)
• Leetcode 938 Range Sum of BST

이진 검색 트리란?

이진 검색 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 이진 검색 트리에서는 다음과 같은 규칙이 있습니다:

1. 왼쪽 자식 노드는 항상 부모 노드보다 값이 작습니다.
2. 오른쪽 자식 노드는 항상 부모 노드보다 값이 큽니다.

LeetCode 938 Range Sum of BST

문제설명

주어진 이진 검색 트리에서 low와 high라는 두 정수가 주어졌을 때, 이 범위 내에 있는 모든 노드의 값의 합을 구하는 문제입니다.

예시 1:

• 트리: [10, 5, 15, 3, 7, null, 18]
• 범위: [7, 15]
• 결과: 32 (7 + 10 + 15)

예시 2:

• 트리: [10, 5, 15, 3, 7, 13, 18, 1, null, 6]
• 범위: [6, 10]
• 결과: 23 (6 + 7 + 10)

해결 방법

이 문제를 해결하기 위해서는 트리를 탐색하면서 각 노드의 값을 확인해야 합니다. 이진 검색 트리의 특성을 활용하면 효율적으로 탐색할 수 있습니다. 예를 들어, 현재 노드의 값이 low보다 작으면 왼쪽 서브트리에는 low 이상인 값이 없으므로 오른쪽 서브트리만 탐색하면 됩니다. 마찬가지로, 현재 노드의 값이 high보다 크면 오른쪽 서브트리에는 high 이하인 값이 없으므로 왼쪽 서브트리만 탐색하면 됩니다.

이를 구현하는 간단한 알고리즘은 다음과 같습니다:

1. 노드가 null이면 0을 반환합니다.
2. 현재 노드의 값이 low보다 작으면 오른쪽 서브트리로 이동합니다.
3. 현재 노드의 값이 high보다 크면 왼쪽 서브트리로 이동합니다.
4. 현재 노드의 값이 low와 high 사이에 있으면 현재 노드의 값과 왼쪽, 오른쪽 서브트리의 값을 더합니다.

코드

from typing import Optional

# TreeNode 클래스 정의
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Solution 클래스 정의
class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        # 노드가 None인 경우 0 반환
        if not root:
            return 0
        
        # 노드의 값이 low보다 작으면 오른쪽 서브트리 탐색
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        
        # 노드의 값이 high보다 크면 왼쪽 서브트리 탐색
        if root.val > high:
            return self.rangeSumBST(root.left, low, high)
        
        # 노드의 값이 범위 내에 있으면 현재 노드의 값 + 왼쪽 서브트리 + 오른쪽 서브트리 값 반환
        return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)

# 사용 예시
if __name__ == "__main__":
    # 예제 트리 구성
    root = TreeNode(10)
    root.left = TreeNode(5)
    root.right = TreeNode(15)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(7)
    root.right.right = TreeNode(18)

    # Solution 객체 생성
    solution = Solution()

    # 범위 [7, 15]에 대한 합 계산
    result = solution.rangeSumBST(root, 7, 15)
    print(result)  # 출력: 32

코드 설명

1. TreeNode 클래스 정의: 트리 노드를 나타내는 클래스를 정의합니다. 각 노드는 값(val), 왼쪽 자식(left), 오른쪽 자식(right)을 가집니다.
2. Solution 클래스 정의: rangeSumBST 메서드를 포함하는 클래스를 정의합니다.
   • rangeSumBST 메서드는 재귀적으로 트리를 탐색하여 범위 내의 노드 값들을 더합니다.
   • 노드가 None인 경우 0을 반환합니다.
   • 현재 노드의 값이 low보다 작으면 오른쪽 서브트리를 탐색합니다.
   • 현재 노드의 값이 high보다 크면 왼쪽 서브트리를 탐색합니다.
   • 현재 노드의 값이 범위 내에 있으면 현재 노드의 값과 왼쪽, 오른쪽 서브트리의 값을 더합니다.
3. 사용 예시: 예제 트리를 구성하고, Solution 객체를 생성하여 rangeSumBST 메서드를 호출하여 결과를 출력합니다.

오늘의 회고

• 이진 검색 트리라는 새로운 개념을 알수 있어서 좋았다.
• 개념을 몰라 어떻게 풀지 고민하다가 chat gpt를 사용하여 문제를 풀었고 코드 리뷰를 통해 익히는 방법으로 하였다.
• 아직 python에 대해 모르는 문제가 많고 바로바로 문제를 어떻게 풀지 모르겠어서 고민이긴 하다.
• 내일은 codeup에서 계속 기초를 다지기 위해 기초 문제를 푸는중인데 그걸 집중적으로 더 풀고 프로그래머스로
  넘어가고 싶다.

TODAY TIL

99 클럽에서 진행하는 코딩 테스트 스터디를 진행하면서 오늘의 공부 내용이나 문제 풀이를 정리 합니다.

오늘의 문제는 9일차 문제 모의고사  (프로그래머스 LV1)

코딩 실력이 일천한지라 생각보다 어렵게 풀었는데요 생각보다 힘들어서 여러 자료를 참고해서 풀었습니다

💡 오늘의 학습 키워드
 패턴 정의
 for문과 if 문의 사용
 enumerate 함수의 이해

문제

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예
answers	return
[1,2,3,4,5]	[1]
[1,3,2,4,2]	[1,2,3]

입출력 예 설명

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.

코드

def solution(answers):
	# 수포자의 찍기 패턴 정의
    spoja1=[1,2,3,4,5]
    spoja2=[2,1,2,3,2,4,2,5]
    spoja3=[3,3,1,1,2,2,4,4,5,5]
    
     # 수포자가 찍은 답안을 문제 길이만큼 확장
    n= len(answers)
    answer1 = [spoja1[i % len(spoja1)] for i in range (n)]
    answer2 = [spoja2[i % len(spoja2)] for i in range (n)]
    answer3 = [spoja3[i % len(spoja3)] for i in range (n)]
     # 맞힌 개수를 세기
    score1 = sum (1 for i in range(n) if answers[i] == answer1[i] )
    score2 = sum (1 for i in range(n) if answers[i] == answer2[i] )
    score3 = sum (1 for i in range(n) if answers[i] == answer3[i] )
    
    # 각 수포자의 점수를 리스트에 저장
    scores = [score1, score2, score3]
    
    # 최고 점수를 찾기
    max_score = max(score1, score2, score3)
    
     # 최고 점수를 받은 수포자 찾기
    result = [i + 1 for i, score in enumerate(scores) if score == max_score]
    
    return result

문제 풀이

1. 패턴정의
   
   • 수포자들의 찍기 패턴이 일정한 규칙에 의거하고 있어서 패턴을 정의
2. 맞힌 수 문제 계산
   • 각 수포자가 맞힌 문제 수를 계산하기 위해 sum 함수를 사용합니다
   • spoja[i % len(spoja)]를 사용하여 각 수포자의 패턴을 반복합니다.
   • answers[i]와 비교하여 맞혔는지 확인하고, 맞힌 경우 1을 더합니다
3. 최고 점수 찾기:
   • 세 수포자의 점수를 리스트에 저장한 후, max 함수를 사용하여 최고 점수를 찾습니다.
4. 최고 점수를 받은 수포자 찾기:
   • enumerate 함수를 사용하여 최고 점수를 받은 수포자를 찾고, 결과 리스트에 저장합니다.
5. 결과 반환:
   • 최고 점수를 받은 수포자의 번호를 담은 리스트를 반환합니다.

오늘의 회고

• 생각보다 문제로 바로 머릿속에 그려지지 않아서 고생했다
• 어떻게 코딩을 해야할지 몰라서 당황하였다
• 내가 주체적으로 코딩을 하지 못한점이 아쉬웠다

내일 공부할것 

• 코딩up 기초 기출문제 10문제 풀기
• 유데미 python 강의 수강하기