티스토리 뷰
프롤로그
"포기는 배추를 셀 때나 하는 말이다."
누구나 살면서 한 번쯤은 들어봤을 법한 문장이다.
어떤 사람에게는 인생의 좌우명일 수도 있고,
좌절에 빠져 있는 누군가에게는 다시 일어설 힘을 주는 말이기도 하다.
하지만 세상만사 모든 일에 항상 적용되는 절대적인 명제가 존재할 리 없다.
오늘 내가 겪었던 어려움은 역설적이게도 '포기'를 하지 못한 게 가장 큰 원인이었다.
어떤 문제를 풀 때든 포기하지 않고 근성 있게 도전하는 자세는 중요하다.
그러나 더 중요한 다른 일이 있음에도 매달리고 있다면,
잘못된 방향으로 최선을 다해 달려가고 있다면,
이러한 상황에서도 포기하지 않는 태도가 옳은 것일까?
처음 스터디를 시작할 때는 하루 한 시간 정도로 예상 소요 시간을 잡았지만,
오늘 같은 경우에는 세 시간이 넘도록 한 문제를 소모적으로 붙잡고 있었다.
당장 해야 할 중요한 일들이 더 많이 남았음에도 말이다.
결국 문제 풀이를 포기하고 다른 사람의 코드를 참고하자,
내가 상상도 못 한 새로운 접근법을 알게 되었고 되려 많은 공부가 되었다.
계속해서 예외 케이스가 나왔던 것은 애초에 방향 설정부터 잘못되었을 수도 있는 것이다.
그럴 땐 나의 무지를 인정하고, 전략적 포기를 감행하는 것이 더 좋은 해법일 수 있다.
Sorting에 대한 컨셉
- Sorting이란?
: 특정 규칙이나 조건대로 요소를 배열하는 것을 말한다.
알고리즘에서 크기에 따라 값을 정렬해야 하는 경우 주로 사용된다.
예를 들어, 오름차순 정렬 알고리즘에 모모, 정연, 다현, 쯔위, 미나, 나연, 지효, 사나, 채영이를 입력으로 넣어주면,
아래와 같은 결과를 얻을 수 있다.
- Sorting의 종류
: 정렬 알고리즘에 대해 잘 정리해둔 블로그를 발견하여, 아래와 같이 내용을 재정리하였다.
(그림 출처: https://hyo-ue4study.tistory.com/68)
1. 선택 정렬(Selection Sort) - O(N^2)
: 선택된 값과 나머지 데이터 중에 값을 비교하여 알맞은 자리를 찾는 알고리즘
2. 삽입 정렬(Insertion Sort) - O(N^2)
: 데이터를 순회하면서 올바른 위치를 찾기까지 이동하면서 자리를 찾는 알고리즘
3. 버블 정렬(Bubble Sort) - O(N^2)
: 인접한 2개의 쌍을 비교하여 순서가 맞지 않으면 서로 교환한다.
이러한 비교-교환하는 과정을 처음부터 끝까지 스캔하여 정렬하는 알고리즘
4. 병합 정렬(Merge Sort) - O(NlogN)
: 데이터를 두 개의 균등한 크기로 분할하고, 각각 정렬한다.
정렬된 두 개의 리스트를 병합하여, 전체 리스트를 정렬한다.
5. 힙 정렬(Heap Sort) - O(NlogN)
: 완전 이진트리 형태로 최대 힙(내림차순), 최소 힙(오름차순)을 구성한다.
루트에 있는 값을 가장 말단 리프로 보내고, 나머지 값들로 반복해서 이 과정을 수행한다.
6. 퀵 정렬(Quick Sort) - O(NlogN)
: Divide and Conquer 방식. 데이터를 임의의 기준(pivot)으로 두 개의 부분 집합으로 나눈다.
한쪽에는 기준 값보다 작은 값들만, 다른 한쪽에는 기준보다 큰 값만 넣는다.
더 이상 나뉘지 않을 때까지 각각의 부분 집합에 대해 위의 과정을 반복한다.
7. 기수 정렬(Radix Sort) - O(dN), d는 자릿수
: 낮은 자릿수부터 먼저 분류하고, 다시 순차적으로 읽어서 높은 자릿수로 분류하는 것을 반복한다.
- Python에서 제공하는 정렬 관련 함수
- sort 함수
: list 내의 원소들을 정렬해주는 기능
기본적으로 오름차순이며, reverse 옵션을 true로 두면 내림차순 정렬이 가능하다.
- sorted 함수
: Python에서 기본적으로 제공하는 내장 함수로, iterable 한 데이터에 한하여 정렬이 가능하다.
리스트를 매개변수로 넘기면 정렬된 리스트를 새롭게 반환한다.
Sort함수와 마찬가지로 reverse 옵션을 true로 두면 내림차순 정렬이 된다.
2160. Minimum Sum of Four Digit Number After Splitting Digits - Easy 🍭
1. 문제 정의
: 4자리의 양의 정수가 주어진다.
이 숫자를 두 개의 정수로 나누어, 나올 수 있는 쌍의 합이 최소일 때의 값을 반환하라.
※ 0이 가장 앞자리에 올 수도 있음을 유의할 것
2. 아이디어 스케치
: 합이 가장 작은 경우는 숫자 2개 쌍으로 10의 자리 숫자가 가장 작을 때로 고정되어 있다.
sort() 함수를 사용하여, 순차적으로 정렬하고 10의 자리와 1의 자리 숫자를 각각 이러한 원리대로 추출하도록 하였다.
3. 내가 작성한 날 것 그대로의 코드 - O(NlogN)/O(N)
|
1
2
3
4
5
6
|
class Solution:
def minimumSum(self, num: int) -> int:
numList = [int(n) for n in str(num)] # space complexity - O(N)
numList.sort() # time complexity - O(NlogN)
return 10*numList[0] + 10*numList[1] + numList[2] + numList[3]
|
cs |
4. 복기 및 배운 점
: "시간 복잡도가 O(1) 일 수도 있지 않을까? "
스터디원 중에 한 분이 의문을 제기하셨는데, 설명을 듣고 나니 꽤 납득이 가는 주장이었다.
이번 문제의 경우 sort 횟수를 나타내는 n의 크기가 worst로 잡아도 4에 불과하므로,
사실상 복잡도가 O(N)이라고 하기보다 O(1)이라고 해야 맞는 게 아니냐는 것.
O(N)과 O(1)을 구분할 때, n의 정의에 필요한 연산의 종류나 input의 크기 등이 고려되어야
하지 않을까라는 좋은 insight를 남겨주었다.
1858. Sorting the Sentence - Easy 🍭
1. 문제 정의
: 최대 9개의 단어로 구성된 영어 문장이 주어졌다.
각 단어에는 1~9까지의 숫자(index)가 붙어있는데, 이 index에 맞춰서 문장을 순서에 맞게 재배열하라.
2. 아이디어 스케치
3. 내가 작성한 날 것 그대로의 코드 - O(N)/O(N)
|
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def sortSentence(self, s: str) -> str:
words = s.split()
sortStc = [0 for x in words] # Space complexity = O(N)
for word in words: # Time complexity = O(N)
wd, idx = word[:-1], word[-1]
sortStc[int(idx)-1] = wd
return ' '.join(s for s in sortStc)
|
cs |
4. 복기 및 배운 점
: 비교적 쉽게 문제를 해결할 수 있었다.
1번과 2번 문제를 당초 예상 시간보다 빠르게 풀면서, 과도한 자신감이 뿜뿜했고,
결과적으로 이 번 코딩 풀이를 전부 못 끝낸 가장 큰 패착이 되었다.
16. 3 Sum Closet - Medium ⛅
1. 문제 정의
: 정수로 된 배열이 주어지고 target 숫자가 주어진다.
배열 내에 존재하는 정수 3개를 합하여, target 값과 가장 가까운 것을 결과로 출력하라.
2. 아이디어 스케치
: 처음에는 3개의 정수를 선택하는 모든 경우의 수만큼의 Sum의 집합을 만든 후, 정렬하여 최소 값을 반환하려 했다.
딱 봐도 brute-force(완전 탐색) 느낌이 난다. 3개로 중첩된 for문을 짜면서부터 냄새가 났다.
당연히 Time limit excceed라는 결과를 얻은 후 계속된 시도 끝에 좌절하다가
결국 Discuss에 올라온 문제를 풀었던 사람들의 아이디어를 참고하여 Two-pointer 알고리즘으로 문제를 해결했다.
간단히 설명하면, 두 개의 포인터를 두어 각각 해당 위치 내에서 탐색을 진행하는 것이다.
나의 코드에서는 for문을 아래 예시의 b만 순차적으로 돌고, a, c는 각각 left와 right의 범위 내에서만 탐색을 진행한다.
3. 내가 작성한 날 것 그대로의 코드 - O(N^2)/O(1)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
minVal = 1000
nums.sort()
for i in range(len(nums)):
l, m, r = 0, i+1, len(nums)-1
while(l<m and m<r): # Time complexity = O(N^2) - for + while
sumVal = sum((nums[l], nums[m], nums[r])) # Space complexity = O(1)
#print(f'num[{l}] = {nums[l]}, num[{m}] = {nums[m]}, num[{r}] = {nums[r]}, sum={sumVal}, min={minVal}')
if(abs(sumVal-target) < abs(minVal)):
minVal = sumVal-target
if(sumVal < target):
l += 1
elif(sumVal > target):
r -= 1
else:
break
return minVal+target
|
cs |
4. 복기 및 배운 점
: 혼자 끙끙대다가 시간을 너무 많이 잡아먹었다.
충분히 고민한 후에는 빠르게 다른 사람들의 코드를 살펴보는 게 시간을 아낄 수 있는 좋은 방법이라고 생각한다.
324. Wiggle Sort Ⅱ - Medium ⛅
1. 문제 정의
: 주어진 정수 배열을 num[0] < num[1] > num[2] < num[3] > ... 의 순으로 재배열하라.
2. 아이디어 스케치
: 여러 방법을 고민하다가, 정방향 정렬과 역방향 정렬을 이용해서 간단히 문제를 풀 수 있을 것 같다는 실마리를 얻었다.
다만 본질을 꿰뚫지 못해서 예외 케이스가 발생했고, 이를 해결하려다가 너무 많은 시간을 잡아먹었다.
결국, Discuss를 참고하여 본질적인 부분을 놓치고 있었다는 것을 깨달았다.
3. 내가 작성한 날 것 그대로의 코드 - O(NlogN)/O(1)
|
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
for i, num in enumerate(sorted(nums)[::-1]):
#print("i, num =",i, num)
nums[(1+2*i) % (len(nums)|1)] = num
print((1+2*i) % (len(nums)|1))
|
cs |
4. 복기 및 배운 점
: 코너 케이스가 계속 발생한다면, 처음으로 돌아가는 용기가 필요하다.
더 간단하게 해결할 수 있는 방법이 없는지 고민해보고, 다른 사람의 접근법에서 힌트를 얻은 후
도전하는 것도 좋은 학습법 중에 하나이다.
'Algorithm' 카테고리의 다른 글
| [LeetCode] H/W 개발자의 Tree 문제 풀이 (0) | 2022.05.16 |
|---|---|
| [LeetCode] H/W 개발자의 Stack & Queue 문제 풀이 (0) | 2022.05.03 |
| [LeetCode] H/W 개발자의 Array & Linked list 문제 풀이 (0) | 2022.04.28 |