자료구조

정렬

1. 버블 정렬(Bubble Sort)에 대해 설명해주세요.

서로 인접한 두 원소를 비교해서 정렬해가면서 전체를 정렬하는 알고리즘입니다. 0번부터 n-1번까지 모든 인덱스를 비교하며 정렬하기때문에 시간 복잡도는 O(n^2)입니다

2. 선택 정렬(Selection Sort)에 대해 설명해주세요.

앞에서부터 선택한 인덱스의 값과 그 이후의 배열에서 최솟값을 비교하여 더 작은 값을 앞에 놓는 과정을 반복해가면서 전체를 정렬하는 알고리즘으로 최솟값을 찾는 과정을 약 n번 수행하게되므로 시간복잡도는 O(n^2)입니다

3. 삽입 정렬(Injection Sort)에 대해 설명해주세요.

삽입 정렬은 두번째 인덱스의 값부터 그 앞에 존재하는 정렬된 원소들과 비교 후 해당 값을 삽입할 위치를 찾아 삽입하면서 정렬해나가는 알고리즘으로 시간복잡도는 O(n^2)이며 대부분의 요소들이 이미 정렬되어있는 경우 최대 O(n)까지 향상될 수 있습니다

스터디 문제 풀기

링크드 리스트 사용법

node=ListNode() 리스트노드 객체 생성 ⭐⭐⭐
node.val 노드 값 출력
node.next 노드 다음 값 출력
https://velog.io/@yeseolee/python-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8Linked-List-feat.LeetCode

2. Add Two Numbers

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        l3=ListNode()
        cur=l3
        plus=0
        while l1 or l2:
            if l1==None:
                sumoftwo=l2.val+plus
                l2=l2.next
            elif l2==None:
                sumoftwo=l1.val+plus
                l1=l1.next
            else:
                sumoftwo=l1.val+l2.val+plus
                l1=l1.next
                l2=l2.next
            if sumoftwo>=10:
                plus=sumoftwo//10
            else:
                plus=0
            sumoftwo%=10
            cur.next=ListNode(sumoftwo)
            cur=cur.next
        if plus:
            cur.next=ListNode(plus)
        return l3.next        

거꾸로 저장된 두 수를 더하고 다시 거꾸로 저장 후 리턴하는 문제다
원래 파이썬의 리스트를 사용할 수 있으면 정말 쉬운 문젠데 링크드 리스트를 직접 사용해 본 건 처음이라서 진짜 너무 헷갈렸다.. 진짜 🫠

거꾸로 저장된 두 수를 더해서 다시 거꾸로 저장한다는 건 결국 각 리스트의 같은 인덱스에 저장된 요소끼리 더하고, 10보다 커지면 다음 인덱스 요소에 더한 값//10을 더해주면 된다(여기선 각 자리가 다 한자리수라서 1을 더해준다고 해도 된다)

l1과 l2는 이미 링크드리스트로 구현이 되어있으므로 신경쓰지 않아도 된다
첫번째, 두번째 줄에서 l3를 링크드리스트로 정의해주고 l3를 cur에 넣어준다. l3는 헤드라고 볼 수 있다. 헤드에는 value가 임의로 설정되고(0) 리스트노드 특성상 다음 값을 가리키는 포인터next를 가지고 있기때문에 리턴할 때도 l3.next를 리턴하면 본인 데이터를 제외한 다음 값들을 쭉 내놓는다 재귀랑 닮았다 https://stackoverflow.com/questions/73452860/why-return-node-next-will-return-the-whole-linked-list

plus는 덧셈에서 10을 넘어갈 때 더해줄 숫자를 저장하는 변수이다. 일단 첫번째 덧셈에서는 더해줄 숫자가 없으므로 0으로 초기화해놓는다.

그 다음 while문에서 l1이나 l2모두 빈 리스트가 될 때까지 아래 로직을 수행하는데 둘중 하나가 빈 리스트일 수 있으므로 조건문으로 나눠준다.
만약 l1== None이라면 해당 리스트는 끝난 것이므로 더이상 더할 값이 없어서 제외하고 합(sumoftwo)을 계산하고 l2값은 사용했으므로 다음 노드로 넘겨준다.
elif문은 l2가 비어있는 경우로 위와 동일하다.
else문은 l1,l2의 노드가 모두 비어있지 않아 값을 가지고 있을 때이다.

더한 값sumoftwo가 10이상이라면 plus는 해당 값을 10으로 나눈 몫(여기선 1로 고정)이되고 10미만이라면 plus값은 없다
sumoftwo에는 10으로 나눈 나머지가 들어가고
cur.next에는 해당 값을 넣어준 리스트노드가 들어가고 cur에 cur.next를 넣어줌으로써 다음 cur.next에 새로운 값이 들어갈 수 있도록 한다(자리를 비워줌)

마지막으로 l1과 l2모두 끝난 경우 None or None이 되어 while문을 탈출하게 되고 이 경우에도 plus값이 있을 수 있으므로 cur.next에 리스트 노드를 생성해 plus값을 넣어준다

리코드 특이점 👻

typing을 임포트해서 쓰는 건지 python3를 그냥 vscode에 붙여넣으면 밑줄이 장난아니다.. python이랑 python3랑 뭐가 다르지?? python은 버전 3이하임 근데 그래도 쓸데없이 클래스 만들어놓는거 좀 별로임.. 굳이?

2. Add Two Numbers 다른 사람 풀이

이건 나랑 푼 방식이 좀 다름

def linked_list_print(l):
    if l is None: 
        return ''
    return linked_list_print(l.next)
    
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        p1 = l1
        p2 = l2
        carry=0
        head = cur = ListNode(0) # 초기화
        # cur 변수를 선언하여 트래버스 작업을 지원하고 노드를 새 목록에 추가합니다.
        # head 변수를 목록의 머리글로 선언합니다.
        
        # Step 2 : 실제 계산하는 부분
        while p1 or p2 or carry:            
            currentval = carry  #첨에 0으로 초기화
            currentval += 0 if p1 is None else p1.val
            currentval += 0 if p2 is None else p2.val
            if currentval >= 10 :
                currentval -=10
                carry = 1
            else:
                carry = 0
            
            # Step 3 : 현재값을 추가한다. 현재값은 항상 1 이상이여야 한다.
            cur.next = ListNode(currentval)  #cur에 linkedlist(ListNode)이용해서 연결한다.
            cur = cur.next
            
            # Step 4 : Add base cases for iterating linked listed
            if p1 is None and p2 is None:
                break
            elif p1 is None:
                p2=p2.next
            elif p2 is None:
                p1=p1.next
            else:
                p1=p1.next
                p2=p2.next
        
        return head.next

# step 5: l1, l2 리스트 노드로 엮어주기

#l1=ListNode(2)
#l1.next=ListNode(4)
#l1.next.next = ListNode(3)
#print(linked_list_print(l1))

#l2=ListNode(5)
#l2.next=ListNode(6)
#l2.next.next = ListNode(4)
#print(linked_list_print(l2))

# Step 6: l3로 덧셈값 인쇄.
#add linked lists

s = Solution() 
l3 = s.addTwoNumbers(l1,l2)
print(linked_list_print(l3))

Solution()객체 s를 만들어서 s의 addTwoNumbers메소드에 l1, l2인자를 넣어서 l3 변수에 넣어준다

l3변수를 프린트하는 함수에 넣는다

무튼 currentval를 먼저 carry로 초기화 후 거기에 추가적으로 더해주는 로직이 좋은 것 같다

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        curr = dummy
        carry = 0
        while l1 or l2 or carry:
            val = carry
            if l1:
                val += l1.val
                l1 = l1.next
            if l2:
                val += l2.val
                l2 = l2.next
            carry, val = divmod(val, 10)
            curr.next = ListNode(val)
            curr = curr.next
        return dummy.next

이건 나랑 비슷한 것 같은데 완전 다른 코드 지금 보니까 위에 있는 코드랑도 비슷한 것 같다

carry가 plus랑 같은 역할을 하는데 여기도 위에서랑 마찬가지로 carry로 이후에 sumoftwo역할을 하는 val을 초기화해준다
l1리스트 값이 있다면(None이 아니라면) 값을 뽑아서 val에 더해주고 다음 노드로 이동시켜준다 l2도 마찬가지로 값을 뽑아서 val에 더해주고 노드를 이동시켜준다

이 if문을 사용해서 차례대로 값을 더해주는 로직이 위랑 동일하고 괜찮은 것같다

carry에는 val을 10으로 나눈 값이 들어가고 val에는 나머지가 들어간다 이 모듈도 좀 괜찮은듯

curr.next에 val값을 담은 리스트 노드를 넣어주고 curr에는 curr.next를 넣어줘서 다음 노드를 비워둔다

내장함수 divmod( )

인자를 받아서 첫번째 인자를 두번째 인자로 나눈 몫, 나머지를 출력해준다

+외국인들은 carry라는 변수 이름을 많이 사용하는듯..?