공부블로그

오늘의 공부 키워드

933 Number of Recent Calls

933 Number of Recent Calls

문제 설명

RecentCounter 클래스는 특정 시간 프레임 내에서 최근 요청의 수를 카운트하는 클래스입니다. 이 클래스를 구현하세요:

• RecentCounter(): 초기화 시, 최근 요청의 수를 0으로 설정합니다.
• int ping(int t): 시간 t에서 새로운 요청을 추가합니다. 여기서 t는 밀리초 단위의 시간을 나타내며, 지난 3000 밀리초 동안(새로운 요청을 포함하여) 발생한 요청의 수를 반환합니다. 구체적으로, [t - 3000, t] 범위에 해당하는 요청의 수를 반환합니다.

각 ping 호출은 이전 호출보다 엄격히 더 큰 값을 사용합니다.

예제 1:

입력:

["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]

출력:

[null, 1, 2, 3, 3]

설명:

RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // 요청 = [1], 범위는 [-2999, 1], 반환 값은 1
recentCounter.ping(100);   // 요청 = [1, 100], 범위는 [-2900, 100], 반환 값은 2
recentCounter.ping(3001);  // 요청 = [1, 100, 3001], 범위는 [1, 3001], 반환 값은 3
recentCounter.ping(3002);  // 요청 = [1, 100, 3001, 3002], 범위는 [2, 3002], 반환 값은 3

제약 사항:

• 1 <= t <= 10^9
• 각 테스트 케이스는 ping을 호출할 때 엄격히 증가하는 값을 사용합니다.
• 최대 10^4번 ping을 호출할 수 있습니다.

파이썬코드

from collections import deque

class RecentCounter:
    def __init__(self):
        self.queue = deque()

    def ping(self, t: int) -> int:
        self.queue.append(t)
        # Remove elements that are out of the 3000ms range
        while self.queue[0] < t - 3000:
            self.queue.popleft()
        return len(self.queue)

# Example usage
recentCounter = RecentCounter()
print(recentCounter.ping(1))     # Output: 1
print(recentCounter.ping(100))   # Output: 2
print(recentCounter.ping(3001))  # Output: 3
print(recentCounter.ping(3002))  # Output: 3

풀이 방법

이 문제를 해결하기 위해서 RecentCounter 클래스를 큐를 사용하여 구현할 수 있습니다. 큐를 사용하면 가장 오래된 요청을 효율적으로 제거하면서 새로운 요청을 추가할 수 있습니다. 다음은 구체적인 풀이 단계입니다:

1. 초기화:
   • __init__ 메서드에서 큐를 초기화합니다.
2. ping 메서드:
   • 새로운 요청이 들어오면 큐에 추가합니다.
   • 큐에서 t - 3000보다 작은 모든 요청을 제거합니다.
   • 큐의 크기를 반환합니다.

오늘의 공부 키워드

2089 Find Target Indices After Sorting Array

2089 Find Target Indices After Sorting Array

예제

예제 1:

• 입력: nums = [1, 2, 5, 2, 3], target = 2
• 출력: [1, 2]
• 설명: 정렬 후 nums는 [1, 2, 2, 3, 5]가 됩니다. nums[i] == 2인 인덱스는 1과 2입니다.

예제 2:

• 입력: nums = [1, 2, 5, 2, 3], target = 3
• 출력: [3]
• 설명: 정렬 후 nums는 [1, 2, 2, 3, 5]가 됩니다. nums[i] == 3인 인덱스는 3입니다.

예제 3:

• 입력: nums = [1, 2, 5, 2, 3], target = 5
• 출력: [4]
• 설명: 정렬 후 nums는 [1, 2, 2, 3, 5]가 됩니다. nums[i] == 5인 인덱스는 4입니다.

해결 방법

이 문제를 해결하기 위해 다음과 같은 단계를 따를 수 있습니다:

1. 배열 nums를 오름차순으로 정렬합니다.
2. 정렬된 배열에서 target 값을 갖는 인덱스를 찾아 저장합니다.
3. 저장된 인덱스 목록을 반환합니다.

코드 구현

다음은 위 과정을 반영한 파이썬 코드입니다:

def target_indices(nums, target):
    # 1. nums를 정렬합니다.
    nums.sort()
    
    # 2. target 값을 갖는 인덱스를 저장할 리스트를 만듭니다.
    result = []
    
    # 3. 정렬된 nums에서 target 값을 찾고 인덱스를 result에 추가합니다.
    for i in range(len(nums)):
        if nums[i] == target:
            result.append(i)
    
    # 4. 결과 리스트를 반환합니다.
    return result

예제 테스트

위의 코드가 주어진 예제들을 제대로 처리하는지 확인해보겠습니다:

print(target_indices([1, 2, 5, 2, 3], 2))  # 예상 출력: [1, 2]
print(target_indices([1, 2, 5, 2, 3], 3))  # 예상 출력: [3]
print(target_indices([1, 2, 5, 2, 3], 5))  # 예상 출력: [4]

결론

이 문제는 배열을 정렬하고 목표 값을 찾는 간단한 문제입니다. 중요한 점은 정렬 후 목표 값을 찾아 인덱스를 반환하는 과정입니다. 이 과정을 통해 배열 내 목표 값의 인덱스를 효율적으로 찾을 수 있습니다.

오늘의 회고

• 아주  재미있던 문제였다.
• 문제가 점점 난이도가 있는거같다..
• 실력만이 답이라는 사실을 기억하자

오늘의 공부 키워드

2733 Neither Minimum nor Maximum

2733 Neither Minimum nor Maximum

문제 해석

주어진 정수 배열 nums에는 서로 다른 양의 정수가 포함되어 있습니다. 이 배열에서 최소값도 최대값도 아닌 수를 찾아 반환하는 문제입니다. 만약 그런 수가 없다면 -1을 반환해야 합니다.

예제 1:

• 입력: nums = [3,2,1,4]
• 출력: 2
• 설명: 이 예제에서 최소값은 1이고 최대값은 4입니다. 따라서 2나 3 중 하나가 유효한 답이 될 수 있습니다.

예제 2:

• 입력: nums = [1,2]
• 출력: -1
• 설명: 이 배열에서는 최소값도 최대값도 아닌 수가 없기 때문에 답이 없습니다.

예제 3:

• 입력: nums = [2,1,3]
• 출력: 2
• 설명: 2는 최소값도 최대값도 아니므로 유효한 답입니다.

코드

def find_number(nums):
    if len(nums) <= 2:
        return -1

    min_value = min(nums)
    max_value = max(nums)

    for num in nums:
        if num != min_value and num != max_value:
            return num
    
    return -1

풀이 방법

이 문제를 해결하기 위한 단계는 다음과 같습니다:

1. nums 배열에서 최소값과 최대값을 찾습니다.
2. 배열을 순회하면서 최소값도 최대값도 아닌 값을 찾습니다.
3. 만약 그런 값이 있다면 해당 값을 반환하고, 없다면 -1을 반환합니다.

예제 실행

예제 1:

nums = [3,2,1,4]
print(find_number(nums))  # 출력: 2

예제 2

nums = [1,2]
print(find_number(nums))  # 출력: -1

예제3

nums = [2,1,3]
print(find_number(nums))  # 출력: 2

이 방법은 배열을 순회하면서 최소값과 최대값을 제외한 값을 찾는 간단한 논리로 문제를 해결합니다.

오늘의 회고

• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자
• 새로운 개념을 배울수 있어서 좋았다.
• 생각보다 긴 코드라서 배우고 있는 입장에서 정말 어려웠다

오늘의 공부 키워드

• 1528 Suffle String

1528 Shuffle String

주어진 문자열 s와 정수 배열 indices가 있습니다. 문자열 s의 각 문자는 indices 배열의 값에 따라 재배열됩니다.
즉, s의 i번째 위치에 있는 문자는 indices[i] 위치로 이동합니다. 재배열된 문자열을 반환해야한다.

예시

1. 예시 1:
   • 입력: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
   • 출력: "leetcode"
   • 설명: "codeleet"의 각 문자는 인덱스 배열에 따라 "leetcode"로 재배열됩니다.
2. 예시 2:
   • 입력: s = "abc", indices = [0,1,2]
   • 출력: "abc"
   • 설명: 각 문자가 제자리에서 움직이지 않으므로 결과는 "abc"입니다.

제약 조건

• s.length == indices.length == n
• 1 <= n <= 100
• s는 소문자 영어 문자로만 구성됩니다.
• 0 <= indices[i] < n
• indices의 모든 값은 고유합니다.

해결 방법

이 문제를 해결하기 위해서는 다음 단계를 따릅니다:

1. indices 배열의 각 위치에 맞게 문자를 재배열할 빈 문자열을 만듭니다.
2. indices 배열을 순회하며 각 인덱스 위치에 s의 문자를 배치합니다.
3. 재배열된 문자열을 반환합니다.

구체적인 알고리즘은 다음과 같습니다:

1. 결과를 저장할 동일한 길이의 빈 리스트 shuffled를 만듭니다.
2. indices 배열을 순회하면서, 각 indices[i] 위치에 s[i] 문자를 배치합니다.
3. 리스트를 문자열로 변환하여 반환합니다

코드

from typing import List

class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        shuffled = [''] * len(s)
        for i, index in enumerate(indices):
            shuffled[index] = s[i]
        return ''.join(shuffled)

# 예제 테스트
sol = Solution()
s1 = "codeleet"
indices1 = [4, 5, 6, 7, 0, 2, 1, 3]
print(sol.restoreString(s1, indices1))  # "leetcode"

s2 = "abc"
indices2 = [0, 1, 2]
print(sol.restoreString(s2, indices2))  # "abc"

s3 = "aiohn"
indices3 = [3, 1, 4, 2, 0]
print(sol.restoreString(s3, indices3))  # "nihao"

코드 설명

• shuffled 리스트를 s와 동일한 길이로 초기화합니다.
• indices 배열을 순회하면서 각 인덱스 위치에 s의 문자를 배치합니다.
• 최종적으로 리스트를 문자열로 변환하여 반환합니다.

오늘의 공부 키워드

• 1773 Count Items Matching a Rule

1773 Count Items Matching a Rule

문제 설명

당신은 items라는 배열을 받았습니다. 여기서 각 items[i] = [typei, colori, namei]는 i번째 아이템의 타입, 색상, 이름을 나타냅니다. 또한 두 개의 문자열 ruleKey와 ruleValue로 표현된 규칙이 주어집니다.

i번째 아이템은 다음 중 하나가 참일 경우 주어진 규칙과 일치한다고 말합니다:

• ruleKey == "type"이고 ruleValue == typei
• ruleKey == "color"이고 ruleValue == colori
• ruleKey == "name"이고 ruleValue == namei

주어진 규칙과 일치하는 아이템의 개수를 반환하세요.

예제

예제 1:

• 입력: items = [["phone","blue","pixel"],["computer","silver","lenovo"],["phone","gold","iphone"]], ruleKey = "color", ruleValue = "silver"
• 출력: 1
• 설명: 주어진 규칙과 일치하는 아이템은 ["computer","silver","lenovo"] 하나입니다.

예제 2:

• 입력: items = [["phone","blue","pixel"],["computer","silver","phone"],["phone","gold","iphone"]], ruleKey = "type", ruleValue = "phone"
• 출력: 2
• 설명: 주어진 규칙과 일치하는 아이템은 ["phone","blue","pixel"]와 ["phone","gold","iphone"] 두 개입니다. ["computer","silver","phone"]은 일치하지 않습니다.

코드

def countMatches(items, ruleKey, ruleValue):
    # ruleKey에 따른 인덱스를 설정합니다.
    index = {"type": 0, "color": 1, "name": 2}[ruleKey]
    
    # 일치하는 아이템의 개수를 셉니다.
    count = 0
    for item in items:
        if item[index] == ruleValue:
            count += 1
    
    return count

# 예제 실행
items1 = [["phone","blue","pixel"],["computer","silver","lenovo"],["phone","gold","iphone"]]
ruleKey1 = "color"
ruleValue1 = "silver"
print(countMatches(items1, ruleKey1, ruleValue1))  # 출력: 1

items2 = [["phone","blue","pixel"],["computer","silver","phone"],["phone","gold","iphone"]]
ruleKey2 = "type"
ruleValue2 = "phone"
print(countMatches(items2, ruleKey2, ruleValue2))  # 출력: 2

풀이법

1. ruleKey에 따라 인덱스를 설정합니다:
   • ruleKey가 "type"이면 인덱스는 0입니다.
   • ruleKey가 "color"이면 인덱스는 1입니다.
   • ruleKey가 "name"이면 인덱스는 2입니다.
2. 각 아이템에 대해 주어진 ruleValue와 일치하는지 확인합니다.
3. 일치하는 아이템의 개수를 셉니다.

주요 포인트

1. 인덱스 설정: ruleKey에 따라 아이템의 어느 부분을 비교할지 결정하기 위해 인덱스를 설정합니다. 이를 위해 사전(dictionary)을 사용하여 "type", "color", "name"에 대응하는 인덱스를 매핑합니다.
2. 아이템 필터링: 각 아이템을 순회하면서 지정된 인덱스의 값이 ruleValue와 일치하는지 확인합니다.
3. 카운팅: 일치하는 경우 카운트를 증가시키고, 최종적으로 일치하는 아이템의 개수를 반환합니다.

이 코드 구조는 매우 효율적이고 명확하며, 각 단계에서 무엇을 하는지 쉽게 이해할 수 있습니다.

오늘의 회고

• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자
• 새로운 개념을 배울수 있어서 좋았다
• 잘은 못하지만 꾸준히 뭔가를 한다는건 좋았다.
• 계속적으로 습관을 가지자

오늘의 공부 키워드

• 2942 Find Words Containing Character

2942 Find Words Containing Character

문제 설명

0부터 시작하는 문자열 배열 words와 문자 x가 주어집니다.

문자 x를 포함하는 단어의 인덱스를 나타내는 배열을 반환하세요.

반환된 배열은 임의의 순서일 수 있습니다.

예제

예제 1:

• 입력: words = ["leet","code"], x = "e"
• 출력: [0, 1]
• 설명: "e"는 "leet"와 "code"에 모두 포함되어 있으므로, 인덱스 0과 1을 반환합니다.

예제 2:

• 입력: words = ["abc","bcd","aaaa","cbc"], x = "a"
• 출력: [0, 2]
• 설명: "a"는 "abc"와 "aaaa"에 포함되어 있으므로, 인덱스 0과 2를 반환합니다.

예제 3:

• 입력: words = ["abc","bcd","aaaa","cbc"], x = "z"
• 출력: []
• 설명: "z"는 어떤 단어에도 포함되지 않으므로, 빈 배열을 반환합니다.

제약 사항

• words.length는 1 이상 50 이하입니다.
• words[i].length는 1 이상 50 이하입니다.
• x는 소문자 영어 문자입니다.
• words[i]는 소문자 영어 문자로만 이루어져 있습니다.

풀이 방법

1. 빈 리스트 만들기: 결과를 저장할 빈 리스트 result를 만듭니다.
2. 각 단어 확인하기: 각 단어와 인덱스를 하나씩 확인합니다.
3. 문자 포함 여부 확인: 만약 단어에 문자 x가 포함되어 있다면, 그 단어의 인덱스를 result에 추가합니다.
4. 결과 반환: 최종적으로 result 리스트를 반환합니다.

코드

def findWordsContainingCharacter(words, x):
    # 결과를 저장할 빈 리스트를 만듭니다.
    result = []
    
    # 각 단어와 그 단어의 인덱스를 하나씩 확인합니다.
    for index, word in enumerate(words):
        # 만약 단어에 문자 x가 포함되어 있다면
        if x in word:
            # 그 단어의 인덱스를 result 리스트에 추가합니다.
            result.append(index)
    
    # 최종적으로 result 리스트를 반환합니다.
    return result

코드 설명

result = []

 2. 각 단어 확인하기:

for index, word in enumerate(words):

• for 반복문을 사용해서 words 리스트의 각 단어와 그 단어의 인덱스를 하나씩 가져옵니다.
• enumerate 함수를 사용하면 index에는 인덱스가, word에는 단어가 들어갑니다.

3. 문자 포함 여부 확인:

if x in word:
    result.append(index)

• if 문을 사용해서 현재 단어(word)에 문자 x가 포함되어 있는지 확인합니다.
• 만약 포함되어 있다면, 그 단어의 인덱스를 result 리스트에 추가합니다.

4. 결과 반환:

return result

• 모든 단어를 확인한 후, result 리스트를 반환합니다. 이 리스트에는 문자 x를 포함한 단어들의 인덱스가 들어 있습니다.

오늘의 회고

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

오늘의 공부 키워드

• 브루트 포스의 개념
• 해시맵의 개념
• 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 배열에 대해 좋은 쌍의 개수를 효율적으로 계산합니다.

오늘의 회고

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

오늘의 공부 키워드

• 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에 대해 피보나치 수를 효율적으로 계산할 수 있습니다.

오늘의 회고

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