[TIL] 99클럽 코테 스터디 1일차 TIL + 소수판별, 최빈값 구하기

📝 알고리즘 스터디를 시작했다!

최근 알고리즘 + 코딩테스트 준비를 하면서, 꾸준히 해야 감도 늘고, 프로그래밍적 사고가 가능해지는 것 같았다. 혼자서 하다 보니 문제 유형도 덜 다양하고, 무엇보다 '꾸준히'가 어려웠다. 그래서 알고리즘 스터디를 시작했다. LMS 내에서 체계적으로 스터디를 진행하는 과정이 깔끔하고 Level이 오르는 것과 캘린더를 보면서 더욱 동기가 부여된다. 필수는 아니지만 TIL 제출이 있어서 꾸준히 해보려고 한다!

 

파이썬/자바/그 외의 언어도 가능하고, 비기너/미들러/챌린저 로 레벨도 나뉜다. 나는 자료구조는 알지만 다양한 알고리즘을 접하는 단계(?)로 신청했다. 오늘은 정기 모임도 있었다. 보너스 문제를 하나 더 주고, 문제 풀이 시간을 주었다. 자바 풀이와 함께 들었는데, 확실히 파이썬의 구현이 좀 더 간단했다. 하지만 동시에 간단함에 속아 그 내부 구현에 대한 이해를 놓칠까 걱정되기도 한다. 아무튼 첫날인데 좋았다! 알고리즘을 혼자서만 하다가 같이 풀고 생각을 공유하는 과정이 재밌다.

 

 

🌼 오늘의 문제 - 백준 1929. 소수 구하기

아주 놀라운 점. 2년 전에 일주일 정도 알고리즘 공부를 했었는데, 그 당시 풀었던 문제였다. 그리고 그 때보다 훨씬 짧은 문제 풀이를 제출했다... 만? 소수 판별의 아이디어를 얻는데 시간이 걸렸고, 검색을 좀 했다. 하하. 오늘 스터디 정기 모임에서 먼저 문제를 분석하는 것이 좋다고 했다. 나는 그동안 문제를 후다닥 보고, 풀이를 구하는데 먼저 앞서있었다. 그래서 문제 분석부터 해봤다.

 

이번 문제는 입력이 1,000,000까지 가능하기 때문에 시간 복잡도 고려가 매우 중요하다. 반복되는 연산을 최소화해야한다. 일단 처음으로 제출한 내 풀이는 아래와 같다.

import math

m, n = map(int, input().split())
result = [True] * (n + 1)

result[0] = False
result[1] = False

for i in range(2, int(math.sqrt(n)) + 1):
    if result[i]:
        j = 2
        while i * j <= n:
            result[i * j] = False
            j += 1

for i in range(m, n + 1):
    if result[i]:
        print(i)

 

기본적인 아이디어는 '에라토스테네스의 체' 풀이 방식이다. '에라토스테네스의 체'는 숫자 중에서 소수만 거르고 나머지는 제거한다는 개념이다. 2부터 시작해서 2의 배수를 제거하고, 3의 배수를 제거하고, 5의 배수를 제거하고, 반복한다.

 

내 풀이에서 소수를 구해야 하는 범위 n까지 배열을 만들고, 2부터 배수들을 제거해 나가는 방식이다. 여기서 확인은 제곱근 값까지만 하면 되는데, 어차피 두 수를 곱해서 어떤 수가 될 때 둘 중의 하나는 무조건 제곱근 값보다 작거나 같기 때문이다. (-> 물론 이 부분을 문제에 적용하면서 구현할 때 약간 헷갈렸다. i의 값이 제곱근 값까지 된다는 점이 살짝 어색하게 느껴졌다. 하지만, 뒤에 j를 활용해 곱하는 값을 활용하는 것이기 때문에 헷갈리지 말자!)

 

여기서 풀이를 내긴 했지만 의문이 생겼던 부분은 1. j를 2부터 계산한다는 점과 2. m(범위의 최솟값)이 클 때에도 배열을 0부터 만들어야 할까? 이 두 가지이다. 2번 의문은 상황에 따라 다르지만 m이 아주 크다면 '세그먼트 체'를 활용할 수 있고, 일반적으로 '에라토스테네스의 체'처럼 처음부터 만드는 방식이 간단하다고 한다.

 

1번 의문을 해결하는 방법은 아래와 같다! 일단 while을 for로 변경해서 반복문의 범위를 명확하게 작성했다. 그리고 기존에는 뒤에 곱하는 값인 j를 2부터 모두 확인하기 때문에, 앞서 확인한 값을 한 번 더 확인하는 경우가 생겼다. 하지만 이번에는 명확하게 i x i부터 확인을 시작해서, 확인하지 못한 값부터 계산하도록 했다. (좀 더 파이썬스러워지고, 가독성이 좋아졌다.)

for i in range(2, int(math.sqrt(n)) + 1):
    if result[i]:
    	""" 🐧 기존 코드 """
        # j = 2
        # while i * j <= n:
        #     result[i * j] = False
        #     j += 1
        
        """ 🐧 변경된 코드 """
        for j in range(i * i, n + 1, i):
            result[j] = False

 

 

🌼 보너스 문제 - LeetCode 347. Top K Frequent Elements

스터디에서 보너스 문제로 나왔다. 이 문제는 주어진 배열에서 가장 빈번하게 나타나는 k개의 요소를 반환하는 문제다. 시간 복잡도가 O(nlogn)보다 좋아야 한다. 이 문제는 1. 정렬, 2. 우선순위큐 방법으로 풀 수 있다. 하지만 일단 가장 먼저 Couter로 개수를 세는 아이디어가 생각나서 풀이했다. 굳이 따지자면 정렬에 가깝다고 해야 할까. 이 방법은 O(nlogk)의 방법이다.

from collections import Counter

def solution(nums, k):
    counter = Counter(nums)
    most_commons = counter.most_common(k)
    answer = [i[0] for i in most_commons]
    print(answer)

위 방법은 파이썬의 Counter 기능을 적극 활용한 방법이다. .most_common 메서드는 가장 빈번한 값들 중에서 (파라미터 값) k개만큼 return 한다. 그리고 내부는 [(key, value)] 형태이기 때문에 key 값을 활용했다. 흠.. 흠.. 이 코드가 개인적으로는 가독성이 좋아 보이지 않았다. 그래서 아래와 같이 num과 freq(빈도)를 명시해서 사용했다.

from collections import Counter

def solution(nums, k):
    counter = Counter(nums)
    most_commons = counter.most_common(k)
    """ 🐧 기존 코드 """
    # answer = [i[0] for i in most_commons]
    """ 🐧 변경 코드 """
    answer = [num for num, freq in most_commons]
    print(answer)

 

💡 추가 방법: 배열의 요소의 개수가 k와 같다면? / .most_common()이 아닌 heapq를 활용해 보자.

빈도를 계산하고 return 하는데 시간 복잡도가 O(nlogk)이지만, 만약 배열의 요소의 개수가 k와 같다면 그대로 반환하면 되므로 O(1) 만큼의 시간 복잡도를 가진다.

 

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]: 
        # 🐧 추가 코드 - O(1) time
        # 배열의 요수의 개수가 k개라면, 그대로 반환
        if k == len(nums):
            return nums
        
        # O(n) time
        counter = Counter(nums)

        # 🐧 추가 코드 - O(nlogk) time
        # 우선순위큐(heap 자료구조 사용)에서 가장 빈번한 k개 반환
        answer = heapq.nlargest(k, counter.keys(), key=counter.get) 
        return answer

 

 

🍀 오늘의 회고

알고리즘 스터디에서 문제 풀이를 공유하고, 어떤 분이 나의 풀이를 공유해도 되는지 물어보셨다. 'Counter'를 생각해내지 못했다고 하셨는데, 나도 알고리즘을 오래 하지 않았지만 덕분에 적극적으로 다양한 풀이 방법을 알고 이해하는 것이 중요하다고 느꼈다. 그리고 문제 풀이를 들으면서 해설해 주는 분께서 파이썬은 '람다'를 잘 활용하면 좋다고 하셨는데,, 나는 그동안 람다를 흐린 눈으로 지나쳐 왔던 것 같다. 내가 먼저 생각해 내기 어려워서일까? 이번 기회로 직면해 보기로 했다.

 

컴피 앱 디자인 변경사항이 많다. 일정이 계속 밀리고 있지만, 또 동시에 사용자를 우선으로 고려하여 기능과 기획 상세가 발맞춰 변경되는 것이 좋아 보인다. 물론 다양한 의견이 오가며 논의하는 과정이 많지만, 이 또한 더 나은 기능을 위한 논의라고 느껴진다. 내일부터는 프로젝트 개발도 와구와구 해야겠다. 마디 앱의 새로운 위젯이 생겼다. 잠금화면의 위젯인데, 기존에 있는 기능을 다양한 방식으로 제공하는 과정이 재밌다! 얼른 배포해야지.

 

UIKit 개발의 감이 점점 떨어지는 것 같다. 현재 진행 중인 프로젝트는 대부분 SwiftUI라서 틈틈이 화면을 UIKit으로 개발하는 공부를 해야겠다. 감기에 걸려서 오전/낮에는 쉬었다. 일교차가 커지고 너무 추워져서 그런 것 같다. 건강이 최고다!

 

내일 할 일!

- 알고리즘 오늘의 문제 풀이

- 13주차 주간 회고 작성

- 컴피 내비게이션 바 개발 마무리

- 마디 잠금화면 위젯 기능 배포

- 4월 계획 세우기

- TIL 작성하기