9-18[알고리즘] 복습 - 링크드 리스트 구현 심화, 이진탐색, 재귀함수, 정렬 등

TIL

이해 안 되었던 부분들을 다시 복습하면서 이해하며 학습하는 시간을 갖는 중

 

복습하는 강의자료에 있는 자료구조를 직접 만들어보는 코드나 만들 때 확인하는 순서에 집중

이런 내용을 최근 수행한 코딩테스트에서 겪어보니 더욱 와닿음

 

링크드 리스트 구현 업데이트

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

    def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        node = self.get_node(index - 1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
        else:
            node = self.get_node(index - 1)
            node.next = node.next.next


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0, 3)
linked_list.delete_node(1)
linked_list.print_all()

기본적으로 알고리즘 문제를 풀이할 때는 for문을 많이 사용하고 while문을 많이 사용하지 않고 있는데 수업 중 강사님은 while문을 많이 사용하면서 뭔가 task의 종료나 필요한 값을 얻어 내었을 때는 return을 이용하여 원하는 결괏값을 빠르게 반환하는 방식으로 문제 풀이를 수행하는 것을 생각하면서 학습

 

문제풀이의 확실한 정답은 없다고 생각하여도 이런 방법이 있다는 것을 느끼면서 복습

 

DFS알고리즘에 사용하는 재귀 함수에 대한 개념 등은 이미 학습을 하였지만 리마인드 하는 시간을 갖고 있으며 내장 함수로 그냥 사용하던 것도 실제 코드로 구현 연습

 

factorial 함수 재귀적 구현

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)

 

 

자료구조에 대한 기본 학습 복습 

 

* 프로그래머스 문제풀이 잠시 보류 

풀이 스타일이 너무 즉흥적이어서 알고리즘 관련 복습 후 문제풀이 시 풀이 구조를 모듈화 하여 풀이하려 계획 중