티스토리 뷰
프롤로그
두 번째 알고리즘 스터디를 진행했다.
모집 정원이 무려 20명이었는데, 대략 5~6분 정도가 드랍했다며 모임 이끌이님이 아쉬워하셨다.
드랍의 원인을 추정해 보면, 다양한 이유가 있겠지만
뭐, 대부분은 바빠졌거나(갑자기?) 당초 기대한 본인의 예상과 방향이 달랐거나 등이 아니었을까 싶다.
지금 대략 6개월 동안 진행하고 있는 머신러닝/딥러닝 스터디도 1회 진행하고 절반 정도의 인원이 드랍했었다.
매몰비용 때문인지는 몰라도 중간에 나가는 사람들은 거의 없고, 빠질 사람들은 1회 차 진행 이후에 대부분 정리된다.
진짜 바쁜 일이 생겼으면 어쩔 수 없지만, 단순히 어려움을 느꼈거나
본인이 스터디를 참여하기에 실력이 부족해서라고 생각해서라면 조금 아쉬운 결정이다.
내가 좋아하는 책 중에 그릿(GRIT)이라는 책이 있다.
아마 살면서 한 번쯤은 들어봤을 것 같지만, 장기적인 목표를 이루기 위한 인내와 열정에 관한 내용이다.
세계적인 스포츠 스타인 마이클 조던도 그의 커리어 중에 9000번의 슛을 실패했고, 300번의 경기에서 졌다.
비틀즈는 무명 시절 3년간, 함부르크의 작은 클럽에서 하루 8시간 이상씩 공연을 했다.
무명이었던 그들은 음악의 장르 구분 없이 흑인 음악에 이르기까지 다양한 장르의 곡을 불러야 했고,
이는 그들이 명곡을 만드는데, 좋은 자양분이 되었다.
성공한 사람들이 말하는 진부한 이야기 중에
'꾸준하게, 실패하더라도 다시, 그냥 해라'라는 말을 나는 정말 좋아한다.
조금은 어렵다고 느껴질 때, 혹은 하기 싫은 유혹에 빠질 때엔
그냥 해라.
유명 브랜드의 슬로건처럼
Just do it
Stack & Queue에 대한 컨셉
- Stack이란?
: LIFO(Last Input First Output)으로, 후입선출이라고 불린다.
아랫돌을 빼서 윗돌을 괼 수 없듯이, 먼저 쌓아둔 값을 나중에 넣은 값보다 먼저 뺄 수 없다.
이 자료구조는 포토샵이나 문서 작성 프로그램에서 undo(ctrl + z)를 생각하면 이해하기 쉽다.
가장 최근에 실행한 결과로 복원해주는 것이 stack에 담긴 저장된 상태로 되돌려 주는 것이라고 보면 된다.
- Queue란?
: FIFO(First Input First Output)으로, 선입선출이라고 불린다.
H/W에서 버퍼를 구현할 때 많이 사용된다. 앞 단에서 데이터가 계속해서 들어온다고 가정할 때,
뒷 단에서 이전 작업을 처리하는 동안 잠시 데이터의 입력을 hold 할 필요가 있을 때,
FIFO 구조의 데이터 버퍼를 사용하게 된다.
225. Implement_Stack_using_Queues - Easy 🍭
1. 문제 정의
: 오직 2개의 queue를 사용하여, stack을 구현하라.
여기서 사용되는 stack은 일반적인 것으로, push, pop, top, empty의 기본 기능만을 갖는다.
2. 아이디어 스케치
: queue 하나는 항상 마지막에 들어온 값 1개로 유지하고,
이전 값들은 다른 queue에 쌓아두었다가,
pop 명령이 실행되면 첫 번째 queue에 값을 밀어 넣는다.
3. 내가 작성한 날 것 그대로의 코드 - O(N)/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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
from queue import Queue
class MyStack:
def __init__(self):
self.q1 = Queue()
self.q2 = Queue()
def push(self, x: int) -> None:
if(self.q1.qsize() == 1):
self.q2.put(self.q1.get())
self.q1.put(x)
def pop(self) -> int:
if(not self.q1.empty()):
p = self.q1.get()
else:
p = None
# fill in the q1
while(not self.q2.empty()):
self.q1.put(self.q2.get())
# move from q1 to q1 except one
while((self.q1.qsize() != 1) and (not self.q1.empty())):
self.q2.put(self.q1.get())
return p
def top(self) -> int:
if (not self.q1.empty()):
tmp = self.q1.get()
self.q1.put(tmp)
return tmp
else:
return None
def empty(self) -> bool:
if (self.q1.empty() and self.q2.empty()):
return True
else:
return False
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
|
cs |
4. 복기 및 배운 점
이번 문제는 비교적 쉽게 해결할 수 있었다.
232. Implement_Queue_using_Stacks - Easy 🍭
1. 문제 정의
: 오직 2개의 stack을 사용하여, queue를 구현하라.
여기서 사용되는 queue는 일반적인 것으로, push, pop, peek, empty의 기본 기능만을 갖는다.
2. 아이디어 스케치
: 첫 번째 stack에 들어오는 값을 쌓고, pop 명령이 들어오면 두 번째 stack으로 하나의 값을 남기고 전부 옮겨둔다.
가장 아래에 있던 값을 pop으로 내보내고, 다시 두 번째 stack에 옮겨뒀던 값들을 첫 번째 stack에 쌓는다.
3. 내가 작성한 날 것 그대로의 코드 - O(N)/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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
from collections import deque
class MyQueue:
def __init__(self):
self.st0 = deque()
self.st1 = deque()
def push(self, x: int) -> None:
self.st0.append(x)
def pop(self) -> int:
if(len(self.st0)<2):
pop = self.st0.pop()
else:
while(len(self.st0) > 1):
self.st1.append(self.st0.pop())
pop = self.st0.pop()
while(len(self.st1) > 0):
self.st0.append(self.st1.pop())
return pop
def peek(self) -> int:
if(len(self.st0)<2):
peek = self.st0.pop()
self.st0.append(peek)
else:
while(len(self.st0) > 1):
self.st1.append(self.st0.pop())
peek = self.st0.pop()
self.st0.append(peek)
while(len(self.st1) > 0):
self.st0.append(self.st1.pop())
return peek
def empty(self) -> bool:
if(len(self.st0) == 0):
return True
else:
return False
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
|
cs |
4. 복기 및 배운 점
Simple is best.
처음에 방향을 잘못 잡아서 삽질을 꽤 많이 했다.
뭔가 구현이 복잡할 때엔, 이게 맞는 방향인 지 돌아볼 필요가 있다.
더 쉬운 방법이 없는지 충분히 모색한 후에 코딩해도 늦지 않다.
코너 케이스가 계속 생겨서 아예 새롭게 발상을 전환했더니, 구현이 쉬운 방향으로 접근해서 해결했다.
1823. Find the Winner of the Circular Game - Medium ⛅
1. 문제 정의
: n명의 참가자가 원탁에 시계 방향으로 둘러앉는다.
주어진 정수 k만큼의 step으로 시계 방향으로 돌면서 탈락자를 선정한다.
최후의 남겨진 1명을 승자로 반환한다.
2. 아이디어 스케치
: 원형 linked list 혹은 원형 queue를 구현하여
주어진 k만큼 순환하고 하나 씩 값을 제거해 나간다.
최종적으로 원소가 1개 남으면, 이 값을 반환한다.
3. 내가 작성한 날 것 그대로의 코드 - O(N)/O(N)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
from collections import deque
class Solution:
def findTheWinner(self, n: int, k: int) -> int:
circle = [i+1 for i in range(n)]
queue = deque(circle)
queue.reverse()
while(len(queue) > 1):
queue.rotate(k-1)
queue.pop()
return queue.pop()
|
cs |
4. 복기 및 배운 점
이번 문제는 비교적 쉽게 해결할 수 있었다.
17. Letter Combinations of a Phone Number - Medium ⛅
1. 문제 정의
: 2~9까지의 전화기 버튼에 문자가 mapping 되어 있다.
주어진 digits으로 만들 수 있는 문자 쌍을 list로 반환하라.
2. 아이디어 스케치
: 먼저 각 숫자에 mapping 된 알파벳을 dictionary 구조에 담는다.
digits이 들어오면, 해당 크기만큼의 queue를 생성하여 앞서 생성한 dictionary의 key에 해당하는 value 값을 담는다.
ex) digits = 23
2 - [a, b, c], 3 - [d, e, f]
각 queue를 자리 수에 해당하는 만큼 순환시키면서 모든 경우의 수를 찾는다.
낮은 자릿수의 길이만큼의 누적곱으로 나누어 떨어지는 경우에 queue를 1 step 순환시킨다.
3. 내가 작성한 날 것 그대로의 코드 - O(4^NM*N)/O(N)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
from collections import deque
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# Data structure - dictionary
dic = {'2' : ['a', 'b', 'c'],
'3' : ['d', 'e', 'f'],
'4' : ['g', 'h', 'i'],
'5' : ['j', 'k', 'l'],
'6' : ['m', 'n', 'o'],
'7' : ['p', 'q', 'r', 's'],
'8' : ['t', 'u', 'v'],
'9' : ['w', 'x', 'y', 'z']
}
q0 = deque()
q1 = deque()
q2 = deque()
q3 = deque()
qList = [q0, q1, q2, q3]
# Initial insert queue
digitList = list(digits)
length = len(digitList)
for i in range(length):
for word in dic[digitList[i]]:
qList[i].append(word)
cycle = 1
for i in range(length):
cycle *= len(qList[i])
output = []
# corner case - Input : ""
if(length == 0):
return None
for i in range(cycle):
str_d = ''
divisor = 1
for j in range(length):
if (j != 0):
divisor *= len(qList[length-j])
#print('[j={0} divisor={1}'.format(j, divisor))
if ((i % divisor == 0) and (i != 0)):
qList[length-j-1].rotate()
str_d += qList[length-j-1][0]
output.append(str_d[::-1])
return output
|
cs |
4. 더 좋은 코드
: 스터디원께서 재귀로 이 문제를 구현해서 풀었다.
코드의 간결함 속에서 숨겨진 내공이 느껴졌다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
def digger(self, digits):
if len(digits)==1:
return list(self.dtol[digits])
else:
letterList = self.digger(digits[:-1])
curList = self.dtol[digits[-1]]
outList = list()
for cL in curList:
outList+=["".join([x,cL]) for x in letterList]
return outList
def letterCombinations(self, digits: str) -> List[str]:
self.dtol = {'2' : 'abc',
'3' : 'def',
'4' : 'ghi',
'5' : 'jkl',
'6' : 'mno',
'7' : 'pqrs',
'8' : 'tuv',
'9' : 'wxyz'}
return self.digger(digits)
|
cs |
5. 복기 및 배운 점
: 이 문제는 스터디원에게 내가 푼 방식에 대해 공유했었던 것이다.
처음에 시간 복잡도를 for문이 중첩되어 있어, O(MN)이라고 생각했으나,
스터디원 중에 한 분이 O(4^N)이라고 생각하는 이유를 논리적으로 설명해 주셔서 수정하였다.
347. Top K Frequent Elements - Medium ⛅
1. 문제 정의
: 주어진 리스트에서 k번째까지 빈도가 높은 순으로 숫자 리스트를 반환하라.
ex) nums = [1, 1, 1, 2, 2, 3], k = 2
output = [1, 2]
2. 아이디어 스케치
(1) 순차적으로 정렬
(2) 딕셔너리에 해당 숫자를 key로 두고, 개수를 value로 담는다.
(3) 딕셔너리의 value 값을 기준으로 정렬
(4) 주어진 k만큼 루프를 돌아, key값의 리스트 생성
3. 내가 작성한 날 것 그대로의 코드 - O(KlogN)/O(N)
|
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 topKFrequent(self, nums: List[int], k: int) -> List[int]:
nums.sort()
nums.append('')
dic = {}
cnt = 1
output = []
#numPrev = nums[0]+1
for i in range(len(nums)-1):
if (nums[i] == nums[i+1]):
cnt += 1
else:
dic[nums[i]] = cnt
cnt = 1
dic = dic.items()
dic = sorted(dic, key=lambda x: x[1], reverse=True)
for num in range(k):
output.append(dic[num][0])
return output
|
cs |
4. 복기 및 배운 점
: Python에서 제공하는 sort 함수를 사용했다.
이 함수는 merge sort와 heap sort를 기반으로 작성된 것이라고 알고 있는데,
소스 코드를 보면서, 어떤 식으로 구현되었는지 나중에 꼭 살펴봐야겠다.
'Algorithm' 카테고리의 다른 글
| [LeetCode] H/W 개발자의 Sorting 문제 풀이 (0) | 2022.05.21 |
|---|---|
| [LeetCode] H/W 개발자의 Tree 문제 풀이 (0) | 2022.05.16 |
| [LeetCode] H/W 개발자의 Array & Linked list 문제 풀이 (0) | 2022.04.28 |