[TIL_Carrotww] 10 - 22/09/13

📝Carrotww의 코딩 기록장

🧲 Linked_list 완벽 이해

🔍 잡설

• 예전에 알고리즘 문제로 처음 Linked_list를 처음 접했을 때는 완전히 이해가 가지 않아 어렴풋이 이해하고 넘겼었던 기억이 있지만 각잡고 공부하니 눈 감고 짤 수 있을정도로 이해하였다.

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

class Linked_list:
    def __init__(self, data):
        self.head = Node(data)
    
    def append(self, data):
        if self.head is None:
            self.head = Node(data)
            return
        
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)
    
    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next
    
    def get_node(self, index):
        cnt = 0
        node = self.head
        while cnt < index:
            node = node.next
            cnt += 1
        
        return node
    
    def add_node(self, index, value):
        input_node = Node(value)
        if index == 0:
            input_node.next = self.head
            self.head = input_node
            return
        
        current_node = self.get_node(index - 1)
        current_next_node = current_node.next
        input_node.next = current_next_node
        current_node.next = input_node
    
    def del_node(self, index):
        if index == 0:
            self.head = self.head.next
            return
        current_node = self.get_node(index - 1)
        current_node.next = current_node.next.next

🔍 TIP

• 클래스에 대한 완벽한 이해를 한 후 Linked List를 접하니 완벽히 이해가 되었다.

🧲 알고리즘

🔗 Programmers 타겟 넘버 Level2

🔍 재귀로 풀 수 있고 BFS, DFS 로 풀 수 있는 문제이다.

• 마지막 방법이 내 풀이고 위 둘 풀이는 이뻐 보이는 다른 분들의 풀이를 참고하여 풀어보았다.

💡 Tree 형태로 초기 result list 를 초기화 하여 값을 더한 temp 리스트를 추가해주어 나온 tree 형태에서 target 의 개수를 찾아 return 해주는 함수이다.

def plus_or_minus(numbers, target):
    result = [0]
    for num in numbers:
        temp = []
        for re in result:
            temp.append(re + num)
            temp.append(re - num)
        result = temp
    return result.count(target)

💡 재귀로 풀었으며 프로그래머스 답안 맨 첫번째 있는 기가막힌 풀이이다.

def pm2(numbers, target):
    # Recursive_version
    if not numbers and target == 0:
        return 1
    elif not numbers:
        return 0
    else:
        return pm2(numbers[:-1], target-numbers[-1]) + pm2(numbers[:-1], target+numbers[-1])

💡 나는 pop() 을 하는것이 무조건 빠를 것 같아 stack 구조를 쓰는 생각의 틀 안에서 벗어나지 못하여 갈피를 못잡았었지만 배운 것을 활용하여 위와 비슷하게 풀어보았다.

def pm3(numbers, target):
    # Recursive_version
    if not numbers and target == 0:
        return 1
    elif not numbers:
        return 0
    else:
        temp_list = copy.deepcopy(numbers)
        temp = temp_list.pop()
        return pm3(temp_list, target-temp) + pm3(temp_list, target+temp)

🧲 느낀점

🔍 재귀 즉 BFS, DFS 가 익숙하지 않다.
알고리즘 문제에 가장 많이 나오는 형태인 만큼 더 많이 연습해야겠다.