99클럽 코테 스터디 18일차 TIL

 

오늘의 공부 키워드

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

오늘의 회고

 

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