아이고 내 두야

오늘은 어제 정리해둔 웹파일을 간단히 복습 한 뒤, 자료구조, 알고리즘 강의를 하루종일 봤다.

어제 다 하지 못한 2주차의 숙제풀이에서 아침 시간을 많이 뺏겼다.
총 3문제였는데, 한문제가 내 발목을 잡았었다.

첫번째 문제는, linked list의 끝에서 K번째 값구하기 였다.

#첫번째문제_ linked list
[6] -> [7] -> [8]
#k=2라면, 7이나와야한다.

첫번째 문제는 linked list의 특징을 생각해보면 쉽게 풀 수 있었다.

"linked list는 head노드 밖에 없잖아?"

나는 인덱스변수를 만들어서 리스트의 길이를 확인하고, 확인된 길이에서 k를 빼고 구했다.

풀이강의를 보니, 첫번째풀이에선 나랑 똑같았다. 하지만 두번째 풀이는 내가 전혀 생각하지 못한 풀이였다.

"두개의 기준 노드를 잡고, 하나의 노드를 다른 노드보다 k만큼 떨어지게 한다."

진짜 저 말을 듣고, 아니 어떻게 저런생각을 했지? 하는 생각과 나는 역시 아직 한참 모자르다는 생각이 들었다.(혼자 방구석에서 감탄함..)

두번째 문제는, 가게에서 주문가능한 메뉴, 고객이 주문한메뉴를 비교해서 주문이 가능한지 판별하는문제였다.

#두번째 문제_ 나 주문가능?
menus = ["떡볶이", "만두", "오뎅", "사이다", "콜라"]
orders = ["오뎅", "콜라", "만두"]

숙제영상에서는 문제별로 힌트를 주는데, 힌트를 듣기전에 풀었다.

"아니, 이거 왜 이진탐색한 부분에서 나온거지? 이진탐색하려면 정렬도해야하는데..?"

무슨생각인진 몰라도 이진탐색으로 하나풀고, 다른 하나는 "in"을 써서 간편하게 풀었다.

풀이를 보니, 이진탐색이 정렬를할 때 좋은것은 맞지만, 이는 상황에 따라 다르다는 것을 말해주고 싶었다고 한다. 이를 듣고 앞으로 문제를 풀 때 상황에 맞는 방법을 사용할 수 있도록 좀 더 생각해봐야겠다고 느꼈다.

그리고 대망의 마지막 문제, 내 2시간 반을 가져갔다. 문제는 더하거나 뺴거나.

#세번째 문제_ 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.

처음에 보고,

아 이거 완전탐색인가?

하는 생각을 하고, 생각만했다.(아니 어떻게 짜야할지 모르겠어;;)연산자를 가지고 분명 요리하는건데 어떻게 해야할지만 계속 생각하고 적고 지우고 반복하다, 이러다가 오늘 아무것도 못할 것 같아 풀이를 봤다.

아니!! 재귀?! 이게 특정 구조가 반복되는 그런 구조라고?!!!

1차 머리! 탁!
풀이보고 2차 머리 탁!

def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
    if current_index == len(array):  
        if current_sum == target:
            global result_count
            result_count += 1 
        return
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1, current_sum + array[current_index])
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1, current_sum - array[current_index])


get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0)

"닫힌 마음으로 보면 제대로 볼 수가 없더라."

머리를 맞은 나는 이게 뭐라는거라는 생각이 지배되서 코드보고 이해도 못했다.(폼롤러로 스트레칭하고, 과자 한봉지 먹으니깐 이해됬다. 역시 단게최고)

재귀는 오늘 공부하기전에도 오늘 공부를 하면서도 신기하고, 어렵게 느껴진다.(너 내가 꼭 정복하고말겠어..)

이렇게 숙제 3문제를 마치고,

정렬을 공부했다.
정렬은 이 혼자 공부 할 때, 문제집 책에서 간략하게 나온 내용으로 공부를 한 적이 있었다.

오늘 공부한 정렬으로는

앞과 뒤를 비교해가며 정렬하는 "버블정렬"

가장 작은 값을 선택하여 정렬하는 "선택정렬"

전체에서 하나씩 올바른 위치에 "삽입"하는방식의 "삽입정렬

배열의 앞부분과 뒷부분으로 나뉘어 각각 정렬하고 병합하는 "병합정렬"

4종류의 정렬을 공부했다. 분명 과거에 공부할 때는 어렵지않게 쉽게 이해하고 넘어갔던것같은데, 구현해보려하니 머리가 굳었는지, 생각을 코드로 작성하는데 오래걸렸다.(그냥 공부안한 내가 문제)

오늘 정렬을 공부하면서 가장 기억에 남는것은 병합정렬을 공부하면서, 분할 정복을 하는데 재귀를 사용한 것이다.

진짜 재귀는 놀랍다...

정말 알고리즘 공부를하면, 계획대로 된 적이 없는것같다. 문제푸는데 시간이 정말 너무 오래걸려...(내 두뇌야 쫌만 더 힘을내보자..공부도 더 열심히하고 말이야..) 이제 슬슬 슬랙이 활성화 되는데, 능력자분들이 많다. 일주일이 지나면서 TIL, WIL을 작성하는 사람들의 팁? 먼저 작성한 다른사람의 글을 보니, 같은 공부내용인데, 정리하는데 차이가 커보였다.(내자신 눈감아^^. 아니 눈 부릅뜨고 배워. 이 자식아)

내일은 남은 알고리즘 강의를 보고, 1주차 회고록을 작성해야지!