문제출처

https://leetcode.com/problems/valid-anagram/description/

문제

Given two strings s and t, return true if t is an anagram of s, and false otherwise.  
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.  

Example 1:  
Input: s = "anagram", t = "nagaram"  
Output: true  

Example 2:  
Input: s = "rat", t = "car"  
Output: false  

Constraints:  
1 <= s.length, t.length <= 5 \* 104  
s and t consist of lowercase English letters.  

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Anagram은 하나의 단어를 철자 순서를 바꿔 다른 단어로 바꾸는 것이다.
한글로 친다면 고무 - 무고 이 두 단어가 anagram이다.

풀이

#1 Sorting - O(n log n)

첫번째 방식은 Sorting을 이용하는 것이다.
s와 t가 결국 같은 철자 & 개수로 이루어지면 True를 반환한다란 점을 활용한다.
코드는 간단하지만, time complexity가 O(nlogn)이란 단점이 있다.

1. s와 t를 sorting한다
2. s(sort) == t(sort) 의 값을 return한다.

def isAnagram(s: str, t: str) -> bool: 
    return sorted(s) == sorted(t)

#2 Hashmap - O(n)

이번엔 Hashmap을 이용해 time complexity를 nlogn을 n으로 줄여보자.

1. Hashmap을 만들어 놓고, s의 각 알파벳의 종류 / 개수를 업데이트한다.
2. t의 알파벳 종류 / 개수를 hashmap으로 부터 제거한다.
3. hashmap이 0이 아닐 경우 (다른 알파벳이 있거나 알파벳 개수가 달랐단 뜻이니) False를 반환한다.

def isAnagram(s: str, t: str) -> bool:
    count = {}
    for i in s:
        count[i] += 1
    for i int:
        count[i] -= 1

    for val in count.values():
        if val != 0:
            return False
    return True

#3 Hashmap, using Counter - O(n)

Python에 내장된 Counter이란 기능이 있다.
Hashable object counting하는데 특화된 딕셔너리이다.
한 줄로 끝나서 for문을 사용하는 것보다 간단하고, time complexity도 동일하다.
다만 #2 번 솔루션은 n이 길 경우, iterate 하는 도중에 맞지 않은 값이 나오면 빨리 False를 return할 수 있단 점이 장점이 될 수도 있다.

def isAnagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

Follow up :

What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

위 솔루션 모두 unicode와 ASCII 상관없이 동일하게 동작한다.
따라서 코드를 수정할 필요는 없으다.

하지만 "é" 같이 accent가 붙은 알파벳을 "e"로 표현하고 싶다면 Normalize를 고려할 수 있다.

import unicodedata
from collections import Counter

def isAnagram(s: str, t: str) -> bool:
# Normalize the strings to NFC
    s = unicodedata.normalize('NFC', s)
    t = unicodedata.normalize('NFC', t)
    return Counter(s) == Counter(t)

행렬 곱셈(Matrix Multiplication)은 컴퓨터 과학에서 매우 중요한 연산 중 하나입니다. 일반적인 행렬 곱셈 알고리즘은 (O(n^3))의 시간복잡성을 가지지만, Strassen's Algorithm은 이를 개선하여 시간복잡성을 (O(n^{2.81}))로 줄인 알고리즘입니다. 이번 글에서는 Strassen's 알고리즘이 어떻게 작동하는지, 그리고 그 작동 원리를 이해하기 쉽게 설명하겠습니다.

일반적인 행렬 곱셈

행렬 곱셈의 기본 원리를 먼저 이해해 봅시다. 두 (n \times n) 행렬 (A)와 (B)를 곱하는 경우, 결과는 또 다른 (n \times n) 행렬 (C)가 됩니다. 각 (C[i][j]) 원소는 (A)의 i번째 행과 (B)의 j번째 열의 곱의 합으로 계산됩니다.

def matrix_multiply(A, B):
    n = len(A)
    C = [[0] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]

    return C

이 알고리즘은 (O(n^3))의 시간복잡성을 가지며, 큰 행렬에 대해서는 매우 많은 계산이 필요합니다.

Strassen's Algorithm이란?

Strassen's Algorithm은 1969년에 Volker Strassen이 개발한 행렬 곱셈 알고리즘으로, 행렬 곱셈을 더 적은 계산으로 처리할 수 있는 방법을 제안했습니다. 이를 통해 시간복잡성을 (O(n^{2.81}))로 줄일 수 있습니다.

기본 개념

Strassen's Algorithm은 행렬을 단순히 나누고 정교하게 결합하여 곱셈 연산을 줄이는 방식을 사용합니다. 두 (n \times n) 행렬 (A)와 (B)를 곱할 때, 행렬을 4개의 작은 부분 행렬로 나누어 작업합니다.

즉, (A)와 (B)를 다음과 같이 분할합니다:

[
A = \begin{pmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \end{pmatrix}, \quad B = \begin{pmatrix} B_{11} & B_{12} \ B_{21} & B_{22} \end{pmatrix}
]

여기서 (A_{11}, A_{12}, A_{21}, A_{22})는 각각 (n/2 \times n/2) 크기의 부분 행렬입니다.

일반적인 행렬 곱셈에서는 8개의 행렬 곱셈이 필요합니다. 하지만 Strassen의 알고리즘은 7개의 곱셈만으로 결과를 얻을 수 있습니다.

Strassen's Algorithm 단계

1. 7개의 곱셈 계산:
   [
   M_1 = (A_{11} + A_{22}) \times (B_{11} + B_{22})
   ]
   [
   M_2 = (A_{21} + A_{22}) \times B_{11}
   ]
   [
   M_3 = A_{11} \times (B_{12} - B_{22})
   ]
   [
   M_4 = A_{22} \times (B_{21} - B_{11})
   ]
   [
   M_5 = (A_{11} + A_{12}) \times B_{22}
   ]
   [
   M_6 = (A_{21} - A_{11}) \times (B_{11} + B_{12})
   ]
   [
   M_7 = (A_{12} - A_{22}) \times (B_{21} + B_{22})
   ]

2. 결과 행렬 계산:
   [
   C_{11} = M_1 + M_4 - M_5 + M_7
   ]
   [
   C_{12} = M_3 + M_5
   ]
   [
   C_{21} = M_2 + M_4
   ]
   [
   C_{22} = M_1 - M_2 + M_3 + M_6
   ]

   최종적으로 행렬 (C)는 다음과 같이 구성됩니다:
   [
   C = \begin{pmatrix} C_{11} & C_{12} \ C_{21} & C_{22} \end{pmatrix}
   ]

Strassen's Algorithm의 구현

def add_matrix(A, B):
    n = len(A)
    C = [[A[i][j] + B[i][j] for j in range(n)] for i in range(n)]
    return C

def subtract_matrix(A, B):
    n = len(A)
    C = [[A[i][j] - B[i][j] for j in range(n)] for i in range(n)]
    return C

def strassen(A, B):
    n = len(A)

    if n == 1:
        return [[A[0][0] * B[0][0]]]

    mid = n // 2

    A11 = [row[:mid] for row in A[:mid]]
    A12 = [row[mid:] for row in A[:mid]]
    A21 = [row[:mid] for row in A[mid:]]
    A22 = [row[mid:] for row in A[mid:]]

    B11 = [row[:mid] for row in B[:mid]]
    B12 = [row[mid:] for row in B[:mid]]
    B21 = [row[:mid] for row in B[mid:]]
    B22 = [row[mid:] for row in B[mid:]]

    M1 = strassen(add_matrix(A11, A22), add_matrix(B11, B22))
    M2 = strassen(add_matrix(A21, A22), B11)
    M3 = strassen(A11, subtract_matrix(B12, B22))
    M4 = strassen(A22, subtract_matrix(B21, B11))
    M5 = strassen(add_matrix(A11, A12), B22)
    M6 = strassen(subtract_matrix(A21, A11), add_matrix(B11, B12))
    M7 = strassen(subtract_matrix(A12, A22), add_matrix(B21, B22))

    C11 = add_matrix(subtract_matrix(add_matrix(M1, M4), M5), M7)
    C12 = add_matrix(M3, M5)
    C21 = add_matrix(M2, M4)
    C22 = add_matrix(subtract_matrix(add_matrix(M1, M3), M2), M6)

    C = []
    for i in range(mid):
        C.append(C11[i] + C12[i])
    for i in range(mid):
        C.append(C21[i] + C22[i])

    return C

Strassen's Algorithm의 장단점

장점

• 시간복잡성 개선: 일반적인 행렬 곱셈 알고리즘의 (O(n^3))보다 더 빠른 (O(n^{2.81}))의 시간복잡성을 가집니다.
• 큰 행렬에 유리: 매우 큰 행렬에 대해서는 상당한 성능 향상을 기대할 수 있습니다.

단점

• 복잡한 구현: 일반적인 행렬 곱셈 알고리즘보다 구현이 복잡합니다.
• 메모리 사용량 증가: 행렬을 반복적으로 분할하고 계산하기 때문에 추가적인 메모리가 필요합니다.
• 작은 행렬에는 비효율적: 작은 행렬에서는 오히려 일반적인 행렬 곱셈이 더 효율적일 수 있습니다.

결론

Strassen's Algorithm은 행렬 곱셈에서 시간복잡성을 줄일 수 있는 중요한 기법입니다. 큰 행렬에 대해서는 상당한 성능 향상을 제공할 수 있지만, 복잡한 구현과 메모리 사용량 증가 등의 단점도 존재합니다. 따라서 특정 상황에서 적절하게 활용하는 것이 중요합니다.

Counting Inversion이란?

Counting Inversion은 배열 내에서 순서가 뒤바뀐 쌍의 개수를 세는 알고리즘입니다. 두 원소의 순서가 원래의 순서와 반대일 때, 이를 'inversion'이라고 부릅니다.

쉬운 예시

예를 들어, 배열 [2, 4, 1, 3, 5]를 봅시다:

• (2, 1)은 inversion입니다. 2가 1보다 앞에 있기 때문입니다.
• (4, 1)과 (4, 3)도 inversion입니다.

따라서 이 배열의 총 inversion 개수는 3입니다.

알고리즘 구현

Counting Inversion을 구현하는 효율적인 방법 중 하나는 merge sort 알고리즘을 변형하여 사용하는 것입니다. 이 방법을 통해 O(n log n)의 시간 복잡도로 문제를 해결할 수 있습니다.

파이썬 코드

다음은 merge sort를 이용한 counting inversion의 파이썬 구현입니다:

def merge_and_count(left, right):
    result = []
    count = 0
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            count += len(left) - i
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result, count

def sort_and_count(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, left_count = sort_and_count(arr[:mid])
    right, right_count = sort_and_count(arr[mid:])
    merged, merge_count = merge_and_count(left, right)
    return merged, left_count + right_count + merge_count

def count_inversions(arr):
    _, count = sort_and_count(arr)
    return count

코드 설명

1. merge_and_count 함수:
   • 두 정렬된 배열을 병합하면서 inversion을 세는 함수입니다.
   • 오른쪽 배열의 원소가 왼쪽 배열의 원소보다 작을 때마다 inversion을 세줍니다.
2. sort_and_count 함수:
   • 배열을 재귀적으로 분할하고 병합하면서 inversion을 세는 함수입니다.
   • 분할 정복(divide and conquer) 방식을 사용합니다.
3. count_inversions 함수:
   • 주어진 배열의 총 inversion 개수를 반환하는 메인 함수입니다.

사용 예시

arr = [2, 4, 1, 3, 5]
inversions = count_inversions(arr)
print(f"배열 {arr}의 inversion 개수: {inversions}")

이 코드를 실행하면 다음과 같은 결과가 출력됩니다:

배열 [2, 4, 1, 3, 5]의 inversion 개수: 3

결론

Counting Inversion 알고리즘은 데이터의 정렬 상태를 분석하는 데 유용합니다. 이 알고리즘은 merge sort의 아이디어를 활용하여 효율적으로 구현할 수 있으며, 데이터 분석, 정렬 알고리즘의 성능 평가 등 다양한 분야에서 활용될 수 있습니다.

알고리즘을 설계하거나 분석할 때, 우리는 주로 알고리즘의 효율성을 평가하기 위해 시간복잡성과 공간복잡성을 고려합니다. 이 두 개념은 각각 알고리즘이 실행되는 데 필요한 시간과 메모리의 양을 나타냅니다. 이러한 복잡성을 설명할 때 자주 사용하는 것이 바로 Big O 표기법입니다.

Big O 표기법이란?

Big O 표기법은 알고리즘의 성능을 수학적으로 나타내는 방법 중 하나로, 입력 크기에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 설명합니다. 시간복잡성과 공간복잡성을 표현하는 데 사용되며, 주로 최악의 경우를 기준으로 성능을 평가합니다.

Big O 표기법이 중요한 이유

1. 효율성 비교: Big O 표기법은 서로 다른 알고리즘을 공정하게 비교할 수 있는 수단을 제공합니다. 입력 크기가 커질수록 어떤 알고리즘이 더 효율적인지 쉽게 판단할 수 있습니다.
2. 최악의 경우 대비: Big O는 최악의 경우를 기준으로 성능을 평가하므로, 알고리즘이 일정 수준의 성능을 보장하는지 확인할 수 있습니다.
3. 독립적인 평가: Big O는 하드웨어나 프로그래밍 언어와 무관하게 알고리즘 자체의 복잡성을 평가하므로, 이론적 분석이 가능합니다.

시간복잡성 예시

O(1): 상수 시간복잡성

가장 간단한 시간복잡성으로, 입력 크기에 상관없이 일정한 시간이 소요됩니다.

def get_first_element(arr):
    return arr[0]

이 함수는 배열의 첫 번째 요소를 반환하는데, 배열의 크기와 상관없이 항상 동일한 시간이 소요되므로 O(1)입니다.

O(n): 선형 시간복잡성

입력 크기에 비례하여 실행 시간이 증가하는 경우입니다.

def print_all_elements(arr):
    for element in arr:
        print(element)

이 함수는 배열의 모든 요소를 출력하는데, 배열의 크기 n에 따라 실행 시간이 선형적으로 증가하므로 O(n)입니다.

O(log n): 로그 시간복잡성

입력 크기가 커질수록 실행 시간이 느리게 증가하는 경우로, 이진 탐색(Binary Search)이 대표적인 예입니다.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # 값을 찾지 못한 경우

이진 탐색은 정렬된 배열에서 특정 값을 찾을 때 배열을 절반씩 줄여가며 탐색하므로, 탐색 범위가 로그(logarithm) 비율로 줄어듭니다. 따라서 이진 탐색의 시간복잡성은 O(log n)입니다.

O(n²): 이차 시간복잡성

중첩된 반복문이 있을 때 주로 발생하며, 입력 크기가 증가함에 따라 실행 시간이 제곱에 비례하여 증가합니다.

def print_all_pairs(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i], arr[j])

이 함수는 배열의 모든 요소 쌍을 출력하며, 배열의 크기가 n이라면 실행 시간은 n * n, 즉 O(n²)가 됩니다.

공간복잡성 예시

공간복잡성은 알고리즘이 실행되는 동안 필요한 메모리의 양을 나타냅니다.

O(1): 상수 공간복잡성

입력 크기에 상관없이 일정한 메모리만 필요로 하는 경우입니다.

def sum_two_numbers(a, b):
    return a + b

이 함수는 두 숫자의 합을 구하는데, 입력 크기와 상관없이 일정한 메모리만 필요하므로 O(1)입니다.

O(n): 선형 공간복잡성

입력 크기에 비례하여 메모리 사용량이 증가하는 경우입니다.

def copy_array(arr):
    copy = []
    for element in arr:
        copy.append(element)
    return copy

이 함수는 주어진 배열을 복사하는데, 입력 배열의 크기가 n일 경우 동일한 크기의 배열을 새로 생성하므로 O(n)의 공간복잡성을 가집니다.

결론

Big O 표기법은 알고리즘의 성능을 이해하고 비교하는 데 중요한 도구입니다. 시간복잡성과 공간복잡성을 명확하게 표현함으로써, 우리는 알고리즘이 얼마나 효율적인지, 어떤 상황에서 더 적합한지를 판단할 수 있습니다. 알고리즘을 설계할 때 이러한 복잡성을 고려하면, 더 나은 성능을 가진 소프트웨어를 개발할 수 있을 것입니다.

문제 출처

https://leetcode.com/problems/valid-parentheses/description/

문제

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true
Example 2:

Input: s = "()[]{}"
Output: true
Example 3:

Input: s = "(]"
Output: false


Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

풀이

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {")":"(", "}":"{", "]":"["}

        for char in s:
            if char in mapping.values():
                stack.append(char)
            elif char in mapping.keys():
                if not stack or mapping[char] != stack.pop():
                    return False
        
        return not stack

괄호 짝을 맞추는 문제입니다. 괄호로 이루어진 string이 괄호 짝이 맞지 않으면 false, 짝이 맞으면 true를 return해야 합니다.
우선 False일 경우는 두 가지로 정리됩니다.
1.  ) , }, ] 가 (, {, [ 보다 먼저 나왔을 경우

2. (, {, [  가 먼저 나왔지만, 바로 다음에 짝을 이루는 닫는 괄호라 나오지 않을 경우

이제 문제를 해결하기 위해서는
괄호별로 여닫는 기호를 mapping한 dictionary를 생성합니다.

예시답변에사는 닫는 괄호를 key, 여는 괄호를 value로 mapping 했습니다.

이제 string안의 각 문자를 순회합니다.
1. value(여는 괄호) 일 경우, 다음에 짝이 맞는 닫는 괄호가 나오는지 확인하기 위해 stack에 임시로 append 해놓습니다.

2. key(닫는 괄호)일 경우,
a. stack이 비어 있는지 확인합니다(닫는 괄호가 처음 나온 것이니 false)
b. mapping 되어 있는 짝이 stack에 있는 문자와 맞는지 확인합니다( 다르면 false)


stack을 만들어 string 의 각 문자를 하나씩 순회하며 dictionary와 비교하게 하면 됩니다.

stack은 Last in First Out 특징이 있습니다. .pop을 이용하야 마지막에 추가된 문자부터 꺼내어 비교하게 됩니다.

출처

https://leetcode.com/problems/two-sum/description/

내용

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

풀이 - 1

List와 target이 주어진다. List 와 target은 모두 integer이다.

List 안에 있는 두 개의 숫자의 합이 target과 동일해지는 숫자의 index를 출력하는 문제이다.

조건은 동일한 index의 숫자는 반복 사용할 수 없단 것이다.

제일 처음 떠오른 방법은 for문을 이용해서 list 안의 숫자들을 모두 매칭해보는 것이었다.

(이걸 영어로는 brute force라고 표현하더라)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)): # list 안의 숫자들을 순차적으로 돌린다
            for j in range(i + 1, len(nums)): # 동일 index 반복을 하면 안되니 i+1부터 돌린다
                if nums[j] == target - nums[i]: # target과 값을 비교한다
                    return [i, j] # index를 반환한다

Time complexity: O(n2).

바깥 루프 (for i in range(len(nums))): 이 루프는 n번 반복됩니다.
안쪽 루프 (for j in range(i + 1, len(nums))): 이 루프는 매번 n-i-1번 반복됩니다. 평균적으로 봤을 때, 대략 n/2번 정도 반복된다고 할 수 있어요.
따라서, 전체 반복 횟수는 n * (n/2)가 됩니다. 이를 간단하게 표현하면 약 n^2/2가 되는데, 빅오 표기법(Big-O Notation)에서는 상수를 무시하므로 **시간 복잡도는 O(n^2)**입니다.

Space complexity: O(1)

이 함수는 주어진 배열 nums와 몇 개의 변수(i, j 등)만 사용하고 있어요. 여기서 중요한 점은 추가적인 메모리 공간을 거의 사용하지 않는다는 점이에요. 리스트나 다른 데이터 구조를 새로 만들지 않으니까요.
따라서 이 함수의 공간 복잡도는 O(1)입니다.

풀이 - 2

첫번째 풀이는 Follow up question : "Can you come up with an algorithm that is less than O(n2) time complexity?"을 충족시키지 못한다.

이를 충족시키기 위해서는 Space complexity를 희생하여 hash map을 만들어준다.

Hash map은 {숫자 : index} 로 구성되고, target 에서 현재 숫자를 뺀 값이 hash map에 존재하는지 여부를 체크하여 없다면, 이번에 확인한 숫자와 index를 hash map에 저장한다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {} # 숫자 : index 형태의 dictionary
        for i in range(len(nums)): # list의 루프를 돈다
            complement = target - nums[i] # target에서 i번째 index의 숫자를 뺀다
            if complement in hashmap: # 위의 값이 hashmap에 있다면, 목표달성
                return [i, hashmap[complement]] # 이번 숫자의 index인 i와, 기존에 저장된 index를 출력한다
            hashmap[nums[i]] = i # 위의 조건이 부합하지 않으면, i번째 숫자 (num[i])와 index (i)를 hashmap에 저장한다

Time complexity: O(n).

루프 (for i in range(len(nums))): 이 루프는 리스트 nums의 길이만큼 반복됩니다. 즉, n번 반복됩니다.
루프 내부에서는 다음과 같은 작업이 수행됩니다:

target - nums[i] 계산은 O(1) 시간 복잡도를 가집니다.
if complement in hashmap 체크도 일반적으로 O(1)입니다(해시맵에서 값을 찾는 시간은 평균적으로 상수 시간입니다).
hashmap[nums[i]] = i는 값을 해시맵에 저장하는 작업인데, 이것도 O(1) 시간 복잡도를 가집니다.

Space complexity: O(n)

해시맵에는 최대 n개의 키-값 쌍이 저장될 수 있습니다(nums 리스트의 모든 요소에 대해).
따라서 공간 복잡도는 해시맵에 저장되는 요소의 수에 비례하여 O(n)이 됩니다.