티스토리 뷰
프롤로그
연구실에 출근한 지 벌써 2개월이 되어간다.
회사에서 근 7년간 회로 설계만 하다가, 익숙지 않은 알고리즘을 봐야 하니 막막하기 그지없었다.
어디서부터 시작해야 하나 고민하던 찰나에
괜찮은 사람들을 만나서 데일리 코딩 습관 기르기라는 주제로 스터디를 진행하게 되었다.
github도 제대로 사용해본 적 없는 찐코알못이기에
1주 차부터 멘붕 of 멘붕의 연속이었지만, 그래도 발도장 꾸준히 찍다 보면 조금은 익숙해지겠지라는 생각으로
오늘도 코딩이라는 미지의 세계에 발을 내딛는다.
이 글은 이제 막 코딩에 입문하는 분들을 위해 작성되었으며,
H/W 개발자의 무한 삽질 파티를 감상하시면서 나도 할 수 있다는 용기를 드리는 것에 목적을 두었다.
Leetcode가 뭔가요?
이 쪽 세계에는 다양한 코딩 연습/코딩 테스트 준비 사이트가 있다.
백준, 프로그래머스, 정올, 코딩도장 같은 국내 사이트부터,
Leetcode, Codeforces, HackerRank와 같은 해외 사이트까지
인터넷 검색창에 "코딩 테스트"를 입력하면, 굉장히 많은 사이트가 있음을 알 수 있다.
이 중에서도 나는 Leetcode를 통해 알고리즘 문제 풀이를 연습 중인데,
스터디원들의 가장 많은 추천이 있기도 했고, IDE(통합 개발 환경)을 플랫폼에서 제공을 하기 때문에
코딩한 결과를 바로 확인할 수 있는 것이 좋아서이기도 했다.
예전에도 국내 문제 풀이 사이트를 기웃거려본 적이 있었는데, 정답만 올려야 하는 시스템이
뭔가 답답해서(?) 금방 포기하게 되곤 했었다.
Leetcode는 2022년 4월 기준으로 2253문제를 가지고 있으며,
기본 기능은 무료이나 프리미엄 결제를 하면 추가 기능이 개방된다.
결제를 하면 무엇보다 Solution을 볼 수 있다는 게 가장 좋은 점이며,
1년에 대략 159 달러라는 다소 비싼 금액이지만 코딩 테스트를 준비하는 분들은 많이들 업그레이드해서 쓰는 것 같았다.
습관의 힘
스터디 이끔이님께서 첫 모임 때 하신 말씀이 기억에 남는다.
행동은 습관을 만들고
습관은 가치관을 만들고
가치관은 운명을 바꾼다.
주말 제외하고, 부담 없이 하루에 한 문제씩 푸는 것으로 그라운드 룰을 정했으며,
주 1회 Zoom으로 만나서, 각자 풀이 방식에 대해 설명하는 형태로 스터디를 진행하기로 했다.
자료구조를 비롯한 기본적인 알고리즘을 쭉 훑고 지나가게끔 스케줄을 작성해주셨다.
스터디가 완료되는 11주 후에 분명 나는 성장해 있을 것이라 믿는다.
Array & Linked List에 대한 컨셉
Array는 컴퓨터 공학 전공자가 아니더라도, 굉장히 익숙한 개념일 것이다.
H/W 개발자의 관점에서 보면, array는 메모리에 저장되는 공간이라고 봐도 무방한데,
index를 통해서 값을 참조하는 것은 메모리의 address를 통해 저장 공간에 접근하는 것과 같다.
Linked list는 말 그대로, 각 요소가 꼬리에 꼬리를 물고 연결된 자료구조이다.
리스트 내의 각 요소는 노드라고 부르며, 데이터를 삽입하고 싶으면 노드를 만들어 꼬리에 붙이면 된다.
배열에 비해 데이터의 추가/삭제가 용이하지만,
순차적으로 탐색하지 않으면 특정 위치의 노드에 접근할 수 없기 때문에
탐색 속도가 늦다는 단점이 있다.
이번 주는 이러한 Array와 Linked list를 활용한 Leetcode 문제 5개를 풀어보았다.
- 160. Insertion of Two Linked Lists - Easy 🍭
- 1268. Search Suggestions System - Medium ⛅
- 82. Remove Duplicates from Sorted List Ⅱ - Medium ⛅
- 890. Find and Replace Pattern - Medium ⛅
- 336. Palindrome Pairs - Hard 🔥
Leetcode의 문제는 easy, medium, hard로 나누어지는데,
주어진 문제 중에 hard 난이도는 코드는 작성했으나
Time limit over라는 오류 메시지를 받았다.
다른 문제 접근을 통해 시간 복잡도를 줄여야 했지만, 도저히 생각이 나지 않아 포기...
160. Insertion of Two Linked Lists - Easy 🍭
1. 문제 정의
: 2개의 head를 갖는 링크드 리스트의 교차점을 찾아서 값을 반환하라.
2. 아이디어 스케치
(1) 두 head로부터 시작해서 각 node의 끝까지 주소를 각 배열에 담아둔다.
(2) 끝에서부터 각 배열의 값을 비교하여 다음 값이 달라지는 시점의 주소를 갖는 노드 값 반환
3. 내가 작성한 날 것 그대로의 코드 - O(M+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
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
# comparison using id(ListNode)
# Sequential search => Time Limit Exceeded
pA = headA
pB = headB
adrA = []
adrB = []
while True:
adrA.append(id(pA))
if (pA.next == None): break
pA = pA.next
while True:
adrB.append(id(pB))
if (pB.next == None): break
pB = pB.next
adrA.reverse()
adrB.reverse()
flagLongA = len(adrA) > len(adrB)
order = (lambda x, y: len(adrA) if (flagLongA) else len(adrB))(adrA, adrB)
lenShort = len(adrB) if (flagLongA) else len(adrA)
for i in range(order):
if (adrA[i] != adrB[i]) or (i == (lenShort-1)):
order = (order - i) if (adrA[i] != adrB[i]) else order - i - 1
pLong = headA if (flagLongA) else headB
print('(i,order) =',i, order)
break
for i in range(order):
pLong = pLong.next
return pLong
|
cs |
4. 더 좋은 코드 - O(M+N)/O(1)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
pA = headA
pB = headB
while not pA==pB:
pA = pA.next if pA!=None else headB
pB = pB.next if pB!=None else headA
return pA
|
cs |
5. 복기 및 배운 점
: 스터디원께서 풀이한 코드를 보고 현타가 씨게 왔다.
아이디어의 착안점은 같았지만, 구현의 방법이 훨씬 깔끔했고
tail의 포인터를 다른 head로 연결한다는 생각은 나로선 상상조차 못 했다.
이렇게 구현하면, 결국 교차되는 지점의 head가 만나게 되고 원하는 값을 쉽게 반환할 수 있다.
1268. Search Suggestions System - Medium ⛅
1. 문제 정의
: 주어진 단어의 prefix를 한 글자씩 늘려가며, prefix가 일치하는 최대 3개까지의 리스트를 반환
|
1
2
3
4
5
6
7
8
|
Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"], # searchWord = "m"
["mobile","moneypot","monitor"], # searchWord = "mo"
["mouse","mousepad"], # searchWord = "mou"
["mouse","mousepad"], # searchWord = "mous"
["mouse","mousepad"] # searchWord = "mouse"
]
|
cs |
2. 아이디어 스케치
: searchWord를 ["m", "mo", "mou", "mous", "mouse"]와 같이 리스트에 담고,
products의 앞 글자부터 searchWord 리스트에 담긴 targetWord의 글자 수 길이만큼 비교
3. 내가 작성한 날 것 그대로의 코드 - O(M*N)/O(M*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
|
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
maxLen = 3
targetWord = ''
targetList = []
targetResult = []
finalResult = []
# products sorted lexicographically
sortedList = products.copy()
sortedList.sort()
for words in searchWord:
targetWord = targetWord + words
targetList.append(targetWord)
for target in targetList:
for cmpWord in sortedList:
if (target == (cmpWord[0:len(target)])):
targetResult.append(cmpWord)
if (len(targetResult) == maxLen):
break
print(targetResult)
finalResult.append(targetResult.copy())
targetResult.clear()
return finalResult
|
cs |
4. 복기 및 배운 점
: 이 문제는 한 번에 통과한 문제로, 생각보다 어렵지 않았다.
82. Remove Duplicates from Sorted List Ⅱ - Medium ⛅
1. 문제 정의
: 링크드 리스트의 중복된 값을 갖는 노드를 제거하라.
ex) Input = [1, 2, 3, 3, 4, 4, 5]
Output = [1, 2, 5]
2. 아이디어 스케치
(1) 1차적인 컨셉
(2) 2차 컨셉 - 인접 노드의 차이 값을 list로 갖고 있는다.
Pnxt를 순차적으로 움직여서 중복된 값을 찾으면
P값이 해당 중복 값의 다음 node를 가리키도록 연결한다.
3. 내가 작성한 날 것 그대로의 코드 - O(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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
detect = 0
headChange = 0
cycle = 0
if(head == None):
return None
elif(head.next == None):
return head
pList = head
pListNxt = head.next
diffInfo = []
# make list of difference beetween pList and pListNxt
while(True):
if(pList.val == pListNxt.val):
diffInfo.append(1)
else:
diffInfo.append(0)
if(pListNxt.next == None):
diffInfo.append(0)
cycle += 1
break
pList = pList.next
pListNxt = pListNxt.next
cycle += 1
# remove duplication
pList = head
pListNxt = head
for i in range(cycle):
if(detect == 0):
if(diffInfo[i:i+2] == [0,0]): # Not duplicated
pList = pList.next
pListNxt = pListNxt.next
else: # Duplicated
detect = 1
pListNxt = pListNxt.next
if(i==0) and (diffInfo[0]==1): headChange = 1
else: # detect == 1
if(diffInfo[i:i+2] == [0,0]): # Not duplicated
pListNxt = pListNxt.next
pList.next = pListNxt
if(headChange == 1):
head = pList.next
pList = head
else:
pList = pList.next
detect = 0
headChange = 0
else: # Duplicated
pListNxt = pListNxt.next
if((i == (cycle-1)) and (detect == 1)): # last sequence
if(headChange == 1):
head = None
else:
pList.next = None
return head
|
cs |
4. 더 좋은 코드 - 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
|
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def deleteDuplicates(self, head):
pHeadTmp = ListNode(-1, head)
pHeadNxt = pHeadTmp
while head:
if (head.next and head.next.val == head.val):
while (head.next and head.next.val == head.val):
head = head.next
pHeadNxt.next = head.next
else:
pHeadNxt = pHeadNxt.next
head = head.next
return pHeadTmp.next
|
cs |
5. 복기 및 배운 점
: head 앞에 임의의 head를 추가해서 가장 앞부터 중복이 나오는 코너 케이스를 제거한다는 생각은
스터디를 하지 않았으면, 절대 생각해내지 못했을 것 같다.
이 부분을 간단하게 구현함에 따라, 코드가 훨씬 간결해지는 것을 확인할 수 있었다.
역시 Simple is best다. 👍
890. Find and Replace Pattern - Medium ⛅
1. 문제 정의
: 동일한 문자열 구성을 갖는 패턴을 찾아 리스트로 반환한다.
ex) Input: words = ["abc", "deq", "mee", "aqq", ccc"], pattern = "abb"
Output: ["mee", "aqq"]
2. 아이디어 스케치
: 각 글자 간의 동일성을 판단하여, 0과 1로 인코딩한다.
찾고자 하는 pattern 값의 binary 코드와 주어진 리스트의 코드를 비교하여 동일 패턴을 찾는다.
ex) abbc = 111011 (a!=b, a !=b, a!= c, b==b, b!=c, b!=c) # 값이 같으면 0, 다르면 1
3. 내가 작성한 날 것 그대로의 코드 - O(M*N)/O(M+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
|
class Solution:
def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
#pattern encoding
tokens = [token for token in list(pattern)]
lenTokens = len(tokens)
codePattern = 0
cycle = 0
for i in range(lenTokens-1):
for j in range(len(tokens)-1):
if (tokens[0] != tokens[j+1]):
codePattern += 0x1 << cycle
else:
codePattern += 0x0 << cycle
cycle += 1
tokens.pop(0)
#words encoding
ansList = []
for word in words:
divWord = [token for token in list(word)]
codeWord = 0
cycle = 0
for i in range(lenTokens-1):
for j in range(len(divWord)-1):
if (divWord[0] != divWord[j+1]):
codeWord += 0x1 << cycle
else:
codeWord += 0x0 << cycle
cycle += 1
divWord.pop(0)
if(codePattern == codeWord):
ansList.append(word)
return ansList
|
cs |
4. 복기 및 배운 점
스터디원 분께서 mapping을 통해 이 문제를 풀었다고 하셨는데, 잘 이해가 가지 않아 내용을 첨부하지는 않았다.
336. Palindrome Pairs - Hard 🔥
1. 문제 정의
: Palindrome이란, 회문으로 읽는 방향에 상관없이 동일한 문장이다.
ex) 기러기, 수박이박수
주어진 단어 리스트의 두 조합으로 palindrome이 형성되는 경우, 해당 단어의 인덱스 쌍을 리스트로 반환하라.
2. 아이디어 스케치
: Brute force(완전 탐색) 알고리즘을 사용하여, 무식하게 짰더니 역시나 Time over의 결과를 받았다.
Dictionary 자료구조를 사용하여 문제에 접근하려 했지만, 구체적인 아이디어가 떠오르지 않았다.
3. 내가 작성한 날 것 그대로의 코드 - Time over
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
idxList = []
for i in range(len(words)):
for j in range(len(words)):
if(i!=j):
#Wrong trial - time over
concatWord = words[i] + words[j]
#if(concatWord == concatWord[::-1]):
if(concatWord == ''.join(reversed(concatWord))):
idxList.append([i,j])
""" Wrong trial2 - time over
concatWord = list(words[i] + words[j])
for idx in range(int(len(concatWord)/2) + 1):
if(concatWord[idx] != concatWord[len(concatWord)-1-idx]):
break
elif(idx == (int(len(concatWord)/2))):
idxList.append([i,j])
"""
return idxList
|
cs |
4. 더 좋은 코드
: To be updated
5. 복기 및 배운 점
: 이 문제는 Time limit over라는 결과를 받았고, 해결하지 못했다.
다음 스터디 때, 스터디 이끔이께서 풀었던 문제를 다시 공유하겠다고 하셔서 추후 업데이트 예정.
* 본 포스팅에서 설명한 '더 좋은 코드'는 스터디원께서 발표한 내용을 기반으로, 다시 작성한 코드임을 알립니다.
느낀 점과 소회
생각해보니 학부 때, 자료구조 배운 지가 벌써 10년도 넘었다.
나름 CS 관련 수업도 많이 들었기 때문에 이런 점이 나름의 차별화 포인트라 생각하고 있었으나
대학원에 진학하게 되면서, 이러한 생각은 산산이 깨져버리고 말았다.
연구실에서 느낀 것은 많은 EE 분야의 학생들이
알고리즘을 분석하거나 코딩하는 능력도 출중하다는 사실.
그리고 내가 대학을 다닐 때와 다르게,
딥러닝 관련 수업이나 접할 기회가 많아서인지
대부분 많은 인공지능 지식을 미리 습득하고 대학원에 진학한다.
나는 회사에서 온실 안의 화초처럼 고인물이 되어가고 있던 건 아닐는지.
회사 내 존재하는 3가지 인간의 군상
1. 무난하게 자신에게 주어진 업무만 하는 사람
2. 일당백의 업무 능력을 보여주는 소위 말하는 에이스
3. 어떻게 지금까지 안 잘리고 있는지 신기한 월급 루팡
그들도 처음부터 루팡은 아녔을 수도 있다. 아마도 자연스럽게 도태되어 가는 과정이 있지 않았을까?
나는 루팡이 되지 않기 위해 다시 한번 몸부림 칠 기회를 받은 것일지도 모른다.
'Algorithm' 카테고리의 다른 글
| [LeetCode] H/W 개발자의 Sorting 문제 풀이 (0) | 2022.05.21 |
|---|---|
| [LeetCode] H/W 개발자의 Tree 문제 풀이 (0) | 2022.05.16 |
| [LeetCode] H/W 개발자의 Stack & Queue 문제 풀이 (0) | 2022.05.03 |