ㅇ

[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 5 본문

내 생각/강의

[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 5

호랑구야 2023. 6. 23. 09:00

* 수업은 JS 기반이지만 Python으로 구현

Section 5: 문제 해결 패턴

빈도수 세기 패턴

객체나 집합의 요소가 무엇인지 혹은 요소의 빈도가 어떻게 되는지 알아볼 때 사용하며, 중첩된 루프가 필요한 상황에서 벗어나게 하거나, 배열이나 문자가 O(N^2) 시간을 필요로 하는 상황을 벗어나게 해주는 데에 자주 사용된다. 두 개의 루프가 중첩된 개별 루프보다 훨씬 나으므로, 객체를 활용하여 선형 구조를 구성한다. 배열을 객체로 세분화하여 각 배열의 요소를 분류한 다음, 각 배열을 비교할 수 있다.

# same ver1
# 첫 번째 배열 요소의 제곱이 두 번째 배열 요소인지 확인하기.
# 갯수도 같아야 한다.

def same(arr1, arr2):
	# 두 배열의 길이가 같지 않으면 False.
    if len(arr1) != len(arr2):
        return False
    
    # 두 배열의 요소 별 갯수를 확인할 dictionary 선언
    freqCnt1 = {}
    freqCnt2 = {}

	# 만약 freqCnt1에 첫 번째 배열 요소가 이미 key로 있다면, value 값을 하나 더 더해주고
    # 없었다면, key를 새로 배정하고 value에 1을 넣어라.
    for i in arr1:
      if i in freqCnt1:
        freqCnt1[i] += 1
      else:
        freqCnt1[i] = 1
    
    # 위의 과정을 두 번째 배열에도 똑같이 적용한다.
    for i in arr2:
      if i in freqCnt2:
        freqCnt2[i] += 1
      else:
        freqCnt2[i] = 1
    
    # 배열별 요소 갯수 잘 세었는지 확인하는 용도
    print(freqCnt1, freqCnt2)
    
    for i in freqCnt1:
    	# 첫 번째 배열의 제곱한 것이 두 번째 배열에 없다면 False
        if not(i ** 2 in freqCnt2):
        	return False
        # 두 번째 배열의 첫 번째 배열의 제곱한 것 요소의 수와
        # 첫 번째 배열의 요소의 수가 같지 않으면 False
        if freqCnt2[i ** 2] != freqCnt1[i]:
            return False
    # 위의 결과에 어디에도 속하지 않았다면 True
    return True
    
same([1, 2, 2, 3], [4, 9, 1, 4])
same([1, 2, 2, 3, 5], [4, 9, 1, 4, 2])
# anagrams ver 1
# 두 문자열의 알파벳 요소가 같은지 확인하라.
# 공백은 무시하고, 대 소문자도 무시한다.

def anagram(str1, str2):
	# 각 문자열을 소문자로 바꾸고, 공백을 없앤다.
    str1 = str1.lower().replace(' ', '')
    str2 = str2.lower().replace(' ', '')
    
    # 만약 두 문자열의 길이가 다르다면 False
    if len(str1) != len(str2):
        return False
	
    # 두 문자열의 요소 별 갯수를 확인할 dictionary 선언
    freqCnt1 = {}
    freqCnt2 = {}

	# 만약 freqCnt1에 첫 번째 문자열 요소가 이미 key에 있다면, value 값을 하나 더 더해주고
    # 아니라면 key를 새로 배정하고, value에 1을 넣어라.
    for i in str1:
      if i in freqCnt1:
        freqCnt1[i] += 1
      else:
        freqCnt1[i] = 1
        
    # 위의 과정을 두 번째 문자열에도 똑같이 적용한다.    
    for i in str2:
      if i in freqCnt2:
        freqCnt2[i] += 1
      else:
        freqCnt2[i] = 1
        
	# 문자열별 요소 갯수 잘 세었는지 확인하는 용도
    print(freqCnt1, freqCnt2)

    for i in freqCnt1:
    	# 첫 번째 문자열이 두 번째 문자열에 없다면 False
        if not(i in freqCnt2):
            return False
        # 첫 번째 문자열과 두 번째 문자열의 요소 별 갯수가 다르다면 False
        if freqCnt1[i] != freqCnt2[i]:
            return False
    # 위 결과 어디에도 속하지 않으면 True
    return True
    
anagram('Tom Marvolo Riddle', 'I am Lord Voldemort')
anagram('cinema', 'icemen')
# anagrams ver2
# 두 문자열의 알파벳 요소가 같은지 확인하라.
# 공백은 무시하고, 대 소문자도 무시한다.

def anagram(str1, str2):
	# 각 문자열을 소문자로 바꾸고, 공백을 없앤다.
    str1 = str1.lower().replace(' ', '')
    str2 = str2.lower().replace(' ', '')
    
    # 만약 두 문자열의 길이가 다르다면 False 
    if len(str1) != len(str2):
        return False
        
	# 첫 번째 문자열의 요소 별 갯수를 확인할 dictionary 선언
    freqCnt1 = {}

	# 만약 freqCnt1에 첫 번째 문자열 요소가 이미 key에 있다면, value 값을 하나 더 더해주고
    # 아니라면 key를 새로 배정하고, value에 1을 넣어라.	
    for i in str1:
      if i in freqCnt1:
        freqCnt1[i] += 1
      else:
        freqCnt1[i] = 1

	# 첫번째 문자열 요소 갯수 잘 세었는지 확인하는 용도
    print(freqCnt1)

	# 두 번째 문자열의 요소가 freqCnt1의 key에 있다면, value 값을 하나씩 빼주고
    # 만약 요소가 존재하지 않는다면 False
    for i in str2:
      if i in freqCnt1:
        freqCnt1[i] -= 1
      else:
        return False
    # 첫 번째 문자열의 요소별 갯수가 모두 0인지 확인 출력
    print(freqCnt1)
	
    # 위 결과 어디에도 속하지 않는다면 True
	return True
    
anagram('Tom Marvolo Riddle', 'I am Lord Voldemort')
anagram('cinema', 'icemen')

다중 포인터 패턴

인덱스 혹은 위치에 해당하는 포인터 혹은 값을 만든 다음, 특정 조건에 따라 중간 지점에서부터 시작, 끝 혹은 중간의 어느 지점까지 이동 시키는 것으로, 최소한의 공간복잡성을 가능하게 하는 효율적인 문제 풀이 방식이다.

# sumZero ver1
# 주어진 순서대로 정렬된 배열 내에서 더해서 0이 되는 짝을 찾아라.

def sumZero(arr):
	# 포인터 left와 right을 정의한다.
	left = 0
	right = len(arr) - 1
	
    # 포인터 left가 right보다 작은 경우 while 루프를 돌린다.
    while(left < right):
    
    	# 배열[left]와 배열[right]의 더한 값을 sum이라고 선언
        sum = arr[left] + arr[right]
        
        # 만약 sum이 0이면, 배열[left]와 배열[right]를 return
        if sum == 0:
          return [arr[left], arr[right]]
          
		# 만약 sum이 양수라면, right를 왼쪽으로 한 칸 옮긴다.
        elif (sum > 0):
          right -= 1
        # 만약 sum이 음수라면, left를 오른쪽으로 한 칸 옮긴다.
        else:
          left += 1
  	# sum이 0이 되기 전에 left와 right의 크기가 전복되거나
    # 빈 배열일 경우 출력할 메세지
	return 'Undefined'
  
  
sumZero([-4, -3, -2, -1, 0, 1, 2, 3, 10])
sumZero([-4, -3, 0, 1, 2, 10])
# CntUnqVal ver1
# 주어진 순서대로 정렬된 배열에서 요소의 종류가 몇 개인지 출력하라.

def CntUnqVal(arr):
	# 만약 빈 배열이 주어질 경우, 0을 출력
	if len(arr) == 0:
    	return 0
	# 포인터 i 와 j 를 선언
	i = 0
	j = 1
	
    # 포인터 j가 주어진 배열의 수보다 적은 경우에는 while 루프를 돌린다.
	while(j < len(arr)):
    	# i와 j의 변화를 확인하기 위한 용도
		print(i, j)
        
        # 만약 배열[i]의 값과 배열[j]의 값이 동일할 경우, j 포인터를 한 칸 오른쪽으로 옮긴다.
        if arr[i] == arr[j]:
          j += 1
      	# 아닐경우, i를 한 칸 옮기고, 배열[i]의 값에 배열[j]값을 둔다.
        # j 포인터를 한 칸 오른쪽으로 옮긴다.
        else:
          i += 1
          arr[i] = arr[j]
          j += 1
          
    # 변형된 배열 확인 용도    
    print(arr)
    
    # 배열에서 유일한 값들의 갯수를 출력
    # 배열[i]에 배열[i]와 배열[j]가 다를 때, 배열[j]을 넣었으므로,
    # 요소가 순서대로 종류별로 배치된다.
    # 인덱스는 0부터 시작하므로 1을 더한 값을 출력한다.
    return i + 1

CntUnqVal([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13])

 

기준점 간 이동 배열 패턴

배열 혹은 숫자를 이동할 수 있는 윈도우를 만든다. 조건에 따라 윈도우는 증가하거나 닫는다. 배열이나 문자열의 하위 집합을 찾는 경우에 매우 유용하다. 윈도우란, 두 기준점 간 사이의 배열을 말하는데, 두 기준점이 계속해서 이동하므로, 이 알고리즘을 sliding window 라고 부른다.

# MaxSubSum ver1
# 주어진 배열에 주어진 숫자만큼 연속된 숫자의 합이 가장 큰 것을 출력하시오

def MaxSubSum(arr, num):
    # 최대합과 임시합을 0으로 선언
    maxsum = 0
    tmpsum = 0

    # 만약 주어진 숫자가 배열 길이보다 길다면 'Undefined'을 출력
    if num > len(arr):
        return 'Undefined'

    # 최대합을 배열의 0부터 num-1까지의 합으로 선언
    for i in range(num):
        maxsum += arr[i]
    
    # 임시합 최대합으로 선언
    tmpsum = maxsum

    # 원래의 하위 배열의 첫 번째 요소를 빼고 그 다음 하위 배열의 마지막 요소를 더해준다.
    # 원래의 하위 배열의 합과 그 다음 하위 배열의 합 중 더 큰 것을 maxsum에 선언
    for i in range(num, len(arr)):
        tmpsum = tmpsum - arr[i - num] + arr[i]
        maxsum = max(maxsum, tmpsum)

    return maxsum

MaxSubSum([2, 6, 9, 2, 1, 8, 5, 6, 3], 3)
# MaxSubSum ver2
# 주어진 배열에 주어진 숫자만큼 연속된 숫자의 합이 가장 큰 것을 출력하시오

def MaxSubSum(arr, num):

    # 만약 주어진 숫자가 배열 길이보다 길다면 'Undefined'을 출력
    if num > len(arr):
        return 'Undefined'

    # 최대합을 배열의 0부터 num-1까지의 합으로 선언
    # 임시합 최대합으로 선언
    maxsum = sum(arr[:num])
    tmpsum = maxsum

    # 원래의 하위 배열의 첫 번째 요소를 빼고 그 다음 하위 배열의 마지막 요소를 더해준다.
    # 원래의 하위 배열의 합과 그 다음 하위 배열의 합 중 더 큰 것을 maxsum에 선언
    for i in range(num, len(arr)):
        tmpsum = tmpsum - arr[i - num] + arr[i]
        maxsum = max(maxsum, tmpsum)

    return maxsum

MaxSubSum([2, 6, 9, 2, 1, 8, 5, 6, 3], 3)

 

분할과 정복 패턴

아주 큰 배열이나 문자 데이터 더 작은 덩어리로 나누고, 또 다시 작은 덩어리로 나누는 작업을 한다. 시간 복잡도를 크게 줄이는데 활용할 수 있다.

# search
# 주어진 순서대로 정렬된 배열에서 주어진 어떤 값이 어느 위치에 있는지 출력하는 것
import math

def search(arr, val):
    # min을 0으로 선언
    min = 0
    # max를 배열 길이 - 1 로 선언
    max = len(arr) - 1

    # min이 max보다 작거나 같을 때까지 while 루프 돌림
    while(min <= max):
        # mid에 min과 max의 정수 중간값을 선정.
        mid = math.floor((min + max) / 2)
        # curElm는 배열의 mid 위치의 값으로 선언
        curElm = arr[mid]

        # 만약 배열[mid]가 주어진 val 보다 작다면, min을 mid 보다 1 더 크게 선언
        if curElm < val:
            min = mid + 1

        # 만약 배열[mid]가 주어진 val 보다 크다면, max를 mid 보다 1 더 작게 선언
        elif curElm > val:
            max = mid - 1
        # 만약 배열[mid]가 주어진 val과 같다면 mid, 배열의 위치를 return
        else:
            return mid

    # 배열에 그 값이 없다면 -1을 return
    return -1
    
search([1, 2, 3, 5, 6, 8, 9, 12, 15, 16, 29], 15)
반응형
저작자표시 비영리 동일조건 (새창열림)

'내 생각 > 강의' 카테고리의 다른 글

[EBS_위대한 수업] [정치학] 조지프 나이, 누가 진정한 리더인가_4강 리더십의 기술(하)  (0) 2023.06.24
[EBS_위대한 수업] [정치학] 조지프 나이, 누가 진정한 리더인가_3강 리더십의 기술(상)  (0) 2023.06.23
[EBS_위대한 수업] [정치학] 조지프 나이, 누가 진정한 리더인가_2강 권력의 주인  (0) 2023.06.22
[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 4  (0) 2023.06.22
[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 3  (0) 2023.06.21
'내 생각/강의' Related Articles more
Comments