[1주차] 항해99 심화트랙 - 기본 자료구조 학습 회고

항해99

심화트랙 선택

항해99 본 과정이 시작됐다. 본 과정은 정규트랙과 심화트랙 두 개로 나뉘어 있었고, 둘 중 하나를 선택해서 진행할 수 있었다. 나는 개발 경험도 있었고, 자료구조 및 알고리즘에 시간을 더 투자하고 싶어서 심화트랙을 선택했다. 앞으로 약 3주간 팀을 이뤄 자료구조 및 알고리즘을 공부할 예정이다. 문제는 백준, 리트코드의 문제를 하루에 4~5개 정도 풀게 되었다. 커리큘럼이 Python으로 진행되었는데, 문법이 익숙하지 않아 문제를 풀 때 많이 찾아가면서 풀게 됐다. 문제를 풀면서 느꼈던 점을 중심으로 적어보려고 한다.

 

---

 

시간 복잡도

[Leetcode] 15. 세 수의 합 - https://leetcode.com/problems/3sum/

LeetCode - The World's Leading Online Programming Learning Platform

# 예시 데이터
# 세 수의 합이 0이 되는 수 찾기
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:

        answer = []
        nums.sort()
        for i in range(len(nums) - 2):
            lt = i + 1
            rt = len(nums) - 1

            # 중복 제거
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            while lt < rt:
                sum = nums[i] + nums[lt] + nums[rt]
                if sum < 0:
                    lt += 1
                elif sum > 0:
                    rt -= 1
                
                else:
                    answer.append([nums[i], nums[lt], nums[rt]])

                    # 중복 제거
                    while lt < rt and nums[lt] == nums[lt + 1]:
                        lt += 1
                    while lt < rt and nums[rt] == nums[rt - 1]:
                        rt -= 1

                    lt += 1
                    rt -= 1
        
        return answer

난 처음에 단순히 3중 for문으로 순회하여 3개의 수의 합이 0인 경우를 찾으려고 했다. 3중 for문으로 풀 경우 시간복잡도는 O(n^3)으로 당연히 시간 초과로 통과하지 못했다. 어떻게 풀어야 할지 고민하다가 투 포인터(Two pointer) 알고리즘을 적용하게 됐다. for 문으로 첫 번째 수부터 차례로 값을 선택하고, 이후 리스트에 투 포인터를 적용했다.

 

sum = for문으로 선택된 값 + left값 + right값으로 하였고, sum > 0 일 경우 left += 1, sum < 0 일 경우 right -= 1 로 포인터를 이동하며 순회한다. 포인터를 이동하며 세 수의 합이 0이 되면 answer 리스트에 세 수를 추가하는 방법으로 풀었다.

 

투 포인터 알고리즘을 적용하니 통과가 됐다. 이 문제는 시간 복잡도에 대한 이해와 그에 대한 알고리즘 지식이 있어야 풀 수 있는 문제였다. 시간 복잡도를 줄일 수 있는 알고리즘에 대한 지식이 부족했다. 이 문제를 통해 알고리즘을 설계하고 분석할 때, 시간 측면에서 효율성을 고려하는 것이 매우 중요하다는 것을 몸으로 느껴볼 수 있었고, 또 다른 문제를 통해 시간 복잡도에 대한 이해를 높이고 시간 복잡도를 낮출 수 있는 알고리즘 방법을 공부해야 할 것 같다.

 

---

 

스택 (Stack)

[Leetcode] 739. 일일 온도 - https://leetcode.com/problems/daily-temperatures/description/

LeetCode - The World's Leading Online Programming Learning Platform

# 예시 데이터
# 온도 리스트가 주어지고, 자신보다 따뜻한 날이 되는 일수 구하기
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)
        stack = []
        for idx, temperature in enumerate(temperatures):
            if not stack:
                stack.append(idx)
            else:
                while stack and temperatures[] < temperature:
                    pop_index = stack.pop()
                    answer[pop_index] = idx - pop_index
                stack.append(idx)

        return answer

난 처음 이 문제를 보고 어떻게 풀어야 할지 전혀 감을 잡지 못해서 못 풀었다. 기술 매니저님께서 이 문제에 대한 힌트를 주셨는데, 스택을 활용해 보라고 하셨다. 온도 리스트를 순회하며 스택에 넣으면서, 스택 최상위(top)에 있는 온도보다 높은 온도가 들어올 경우 pop을 하며 풀어보라고 하셨다. 

 

스택 그림을 그려보며 풀어보니 이해가 갔다. 아래는 Example 1 을 예시로 한 그림이다.

Example 1

 

스택에 아무것도 없으면 73의 인덱스 번호인 0을 집어넣는다. 다음으로 74의 인덱스 번호를 집어넣는데, 스택top을 확인해서 74보다 낮은 온도가 있을 경우 pop을 하고 74의 인덱스(1)에서 73의 인덱스(0)를 빼준 수(1 - 0) 가 일수 이다. 생각해야 할 점은 스택을 pop 하고 일수를 구한 다음, 다음 스택 top 값이 또 낮은 온도가 있을 경우 계속해줘야 한다는 점이다.

 

이 방법을 temperatures 리스트의 각 온도에 적용하면서 끝까지 반복하면 answer 리스트에 일수가 모두 입력되고 answer 리스트를 return 하면 정답이다.  이해가 안 가는 사람은 직접 그림을 그려보며 천천히 생각해보면 정답을 찾을 수 있을 것이다.

 

나는 이 문제가 스택으로 풀 수 있을거라곤 생각도 못했다. 이 문제는 나에게 스택으로 알고리즘 문제를 해결하는 새로운 시각을 제공해 주었고, 다양한 상황에서 유용하게 활용될 수 있을 것 같다는 생각이 들었다. 스택의 활용 방법을 느껴본 좋은 문제였다.

 

---

 

해시 테이블 (Hash Table)

[Baekjoon] 1920. 수 찾기 - https://www.acmicpc.net/problem/1920

1920번: 수 찾기

# 예시 입력
# N_list에 M_list 각각의 숫자가 포함되면 1출력, 포함되지 않으면 0출력
5		
4 1 5 2 3 # N_list
5		
1 3 7 9 5 # M_list

from sys import stdin

N = int(stdin.readline())
N_set = set(map(int, stdin.readline().split()))

M = int(stdin.readline())
M_list = list(map(int, stdin.readline().split()))

for M_num in M_list:
    if M_num in N_set:
        print(1)
    else:
        print(0)

Python에서는 Set, Dictionary 를 통해 해시 자료구조를 제공한다. 이 문제에서는 Set을 활용했다. N_list 를 Set에 담아 중복을 제거한 뒤, M_list의 숫자를 꺼내 하나씩 비교하며 N_set에 포함되어 있는지, 아닌지를 체크하였다.

 

만약 비교하는 대상인 N_list를 Set이 아닌 List를 활용하면 이 문제는 시간초과로 틀리게 된다. 해시 자료구조의 장점인 빠른 탐색을 활용해야하는 문제이다. List는 값이 포함되어 있는지 확인하기 위해서는 전체 값을 순회하면서 찾아야 하므로 O(N)이라는 시간복잡도를 가지게 되고, Set은 내부적으로 해시 함수와 버킷(bucket)을 사용하여 O(1) 이라는 시간복잡도를 가지게 된다.

 

참고로 이렇게 포함 여부만 체크하는 경우는 Set을 활용하면 되지만, index 접근이 필요한 경우는 Set을 활용할 수 없다. Set은 index 접근이 불가능하다. index 접근의 경우는 List를 사용해야 한다. List의 index 접근 시간복잡도는 O(1)이다.

 

자료구조에 대한 정확한 이해를 바탕으로 잘 활용하게 된다면, 효율적이고 빠른 데이터 접근을 할 수 있다는 것을 다시 한 번 느끼게 되었다. 자료구조를 이해하고 있다면 난이도는 아주 쉬운 편이지만, 우리에게 자료구조를 공부해야하는 이유를 알려주는 좋은 문제인 것 같다.

 

---

 

글을 마치며

팀 단위로 알고리즘, 자료구조 스터디를 진행해 봤다. 우리 팀은 각자 문제를 풀고, 푼 문제를 발표하면서 공부를 진행했다. 혼자 공부하는 것보다 다른 팀원분의 코드를 보며 내가 생각하지 못한 방법으로 구현한 것을 보고 생각의 범위를 넓힐 수 있는 좋은 기회였다. 다른 팀원분도 내 코드를 보며 생각의 범위를 넓히는데 도움이 됐으면 좋겠다!

 

문제를 보고 어떤 자료구조, 알고리즘을 적용할지 떠올리는게 제일 어려운 것 같다. 많은 문제를 풀어보면서 적용하는 연습이 더 필요할 것 같다. 또한 아직 자료구조와 시간복잡도, 공간복잡도에 대한 지식이 많이 부족한 것 같다. 상황별로 어떤 자료구조를 사용하면 좋을지 더욱 연습하고 공부해서 효율적인 코드를 작성할 줄 아는 개발자가 되기 위해 노력해야겠다.