TIL 11일차 - Algorithm & 자료구조

실시간 강의를 시작으로 녹화강의로 공부했다.

 

알고리즘을 짤 때, 시공간 복잡도를 신경써서 최적화해서 짜야 할 것 같다는 생각이 들었다.

BIG-O(빅오)표기법을 많이 사용할 것 같은데, 'for문 한번당 O(N)이고, 두번 쓰면 O(N^2)이다' 정도는 알아두면 좋을 것 같다.

 

알고리즘은 설명으로 들었을때는 이해가 가고 쉬워보였는데, 실제로 해보면 너무나 어려웠다.

알고리즘 코드카타를 통해 매일 문제를 풀게될 것인데, 1레벨 3개 푸는것도 정말 어려웠다.

---

2번문제

 

정수를 담고 있는 배열 arr의 평균값을 return하는 함수, solution을 완성해보세요.

• arr은 길이 1 이상, 100 이하인 배열입니다.
• arr의 원소는 -10,000 이상 10,000 이하인 정수입니다.

이걸 풀 때, 

def solution(arr):

    answer = sum(arr)/len(arr)

    return (answer)

이렇게 풀었는데, 내 생각엔 이렇게 풀기를 원하지 않았을 것 같다. 결과는 잘나왔지만, 안되는 예가 있을거라고 생각한다.

솔직히  '길이'나 '-10000이상 10000이하' 라는 조건을 파이썬에서 어떻게 만들어야하는지 전혀 모르겠다.

---

3번 문제

• 자릿수 더하기

문제 설명

자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요.
예를들어 N = 123이면 1 + 2 + 3 = 6을 return 하면 됩니다.

제한사항

• N의 범위 : 100,000,000 이하의 자연수

이거는

def solution(n):

    answer=0

    for i in str(n):

        answer += int(i)

    return (answer)

이렇게 풀었다. 솔직히 빈 백지상태에서는 아예 건들지도 못했고, 구글링을 해서 참고해서 제출했다..

str로 자연수를 '문자' 형태로 만들어서 for in 으로 각각의 자릿수를 다시 int로 숫자화시켜서 더해줬다.

아마 이것 또한 원했던 풀이는 아니였을 것이라 예상한다.

이 또한 100,000,000 이하의 자연수라는 조건은 어떻게 적용해야 하는지 모르겠다.

---

연결리스트 짜는 것도 중요하다고 했는데, 혼자 짜보다가 포기하고 따라하면서 짜봤다.

연결리스트에는 Node가 있고, Node는 '데이터'랑 연결하는'next'가 있다.

class ListNode:

    def __init__(self, value=0, next=None):

        self.value = value

        self.next = next

여기까진 이해가 됬다. 첫 번째 Node를 만든것 같은데,

1. None 대신 Null 이라고 써도 되는지 궁금함.

class LinkedList:

    def __init__(self):

        self.head = None

    def append(self, value):

        if not self.head:

            self.head = ListNode(value, None)

            return

        node = self.head

 

        while node.next:

            node = node.next

        node.next = ListNode(value, None)

return 만 써도 되는건줄도 몰랐음. return(~~~~) 뭐 내용이 있어야하는거 아닌가??

head가 없으면 헤드를 추가한다.는 말 같고,

node.next를 while로 무한반복해서 생성한다.

 

근데 아무리 봐도 혼자 백지상태에서는 못 만들 것 같다.

특히나 실전에서 적용시키려고 내용을 바꾸면 더 헷갈리겠다 싶다.