Cooper's devlog

Good

[ 코드리뷰를 받다]

 오후에 코드 리뷰를 받았다. 우선적으로 미션을 마무리 짓지 못한 상태로 코드 리뷰를 받아 아쉬웠다. 그리고 공감할 수도 있겠지만 '어제의 나 ≠오늘의 나'. 어제 작성했던 코드가 기억이 나질 않는다. 내가 어떻게 짰지....? 라는 고민을 하고 있었다. 그래도 다행인건 말을 하다 보면 하나, 둘씩 기억이 난다. 참 아이러니하다.

 코드 리뷰 중 인상 깊었던 것은 K의 코드였다. 나중에 꼭 참고하고 싶었던 내용은 크게 두 가지다.

• Iterable을 LinkedList interface에 extends 받았다. → 이렇게 implement 받으면 foreach문을 사용해서 탐색할 수 있다.
• LinkedList Inteface를 선언했다. → 클래스간 결합도는 낮추고, 표준화가 가능하다.

Iterable이 존재하는 것은 들어는 봤지만 사용해보지 못한 Interface 였다. 나중에 한번 공부해봐야겠다는 생각을 했다.

그리고 코드를 구현하면서 DoublyLinkedList를 composition으로 해서 VideoList를 구현했다. extends(상속)을 이용해 구현하면 상위 코드 변경 시, 하위 클래스의 로직이 틀어질 수도 있는 위험성이 있기 떄문에 composition으로 구현했다. 그런데 우선적인 개념을 잊고 있었다. is-a, has-a 관계를 신경쓰고 있지 않았다. 오늘 저녁에 is-a, has-a 관계에 관해 다시 한번 학습해봐야겠다.

Bad

[미숙한 시간관리]

 기존 공부하는 방식은 체크리스트를 두고 하나씩 지워나가며 학습했다. 하지만 체크 리스트의 규모가 커지는 경우 시간을 많이 할애하고 다른 일을 마치지 못하는 불상사가 발생한다. 그리고 마스터즈 코스를 하며 미션을 우선적으로 하다보니 개발서적을 못읽고 있었기 때문에 개선할 방법이 필요했다. 가장 괜찮았던 방법이 시간을 의무적으로 뺴놓고 나머지 시간은 원하는대로 학습하는 것이었다. 주로 저녁 10시 ~ 자기 전, 오전 8 ~ 9시 30분 이런식으로 별도로 시간을 할애해야 읽는 것이었다. 예전부터 생각은 하고 있었지만 이전의 방식이 편해서 이전 것을 고집했다. 하지만 더욱 효율적인 방식을 위해 그룹원들이 이야기 해준 방식을 참고해서 시간할애를 해봐야겠다. 

TIL

1. Iterable 학습

2. is-a, has-a 학습

3. 운영체제 공부

4. 미션3 테스트코드 작성해보기(JUnit 연습)

[빅오 표기법]

빅오 표기법이란?

• 임의의 아주 큰 N에 대해서 성능의 상한선을 보장해주는 역할. (최소 이 정도 속도는 보장한다!)
• 시간 복잡도(실행시간) + 공간 복잡도(실행공간)으로 이루어져 있다.
• 주어진 함수에서 가장 빨리 증가하는 항만 남긴 채 나머지를 다 버리는 표기법

시간 복잡도가 높다?

• 시간 복잡도가 높다 : 입력의 크기가 증가할수록 알고리즘 수행 시간이 더 빠르게 증가(수행 시간 느려짐)
• 시간 복잡도가 낮다 : 입력이 크기가 증가할수록 더욱 효율적으로 알고리즘 수행 (수행 시간이 빨라짐)
• (하지만 입력의 크기가 매우 작을 경우, 큰 의미를 못가지는 경우가 있음)

자주 사용되는 시간 복잡도

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) < O(n^n)

알고리즘 문제에서 가장 많이 나오는 시간 복잡도 정리

• O(1) : 입력데이터의 크기에 상관없이 수행속도가 일정하다. → Hash
• O(log n) : 연산이 수행될 때마다 탐색할 데이터가 절반으로 줄어드는 경우 → ex) 퀵소트, 이진탐색
• O(n) :  n에 크기만큼 정비례해서 수행속도가 증가 → 반복문 순회(for, while)
• O(n^2) : n의 크기에 따라 제곱에 비례해서 수행속도가 증가 → 이중 반복문(이중 for문)

[연속 배열과 링크드 리스트의 차이]

배열(Array)

• 0으로 시작하는 index값으로 즉각적으로 참조할 수 있는 형태의 자료구조
• 장점 : 자료에 대한 접근이 엄청나게 빠르다.
• 단점 : 메모리 공간 활용에 제약이 있다. (배열의 최대 크기를 변경할 수 없다.)

연결리스트(linked list)

• 여러개의 노드(Node)가 연결된 형태의 자료구조
• 장점 : 메모리 공간 활용이 효율적이다.( 자료를 삽입, 삭제가 용이하다)
• 단점 : 배열과 비교했을 때, 자료에 접근하는 시간 소요가 길다.
• 종류 
  • 단일 연결 리스트 : 각 노드에 대한 자료 공간 + 한 개의 포인터 공간(다음 노드)
  • 이중 연결 리스트 : 각 노드에 대한 자료 공간 + 두 개의 포인터 공간(이전 + 다음)
  • 원형 연결 리스트 : 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만듦

내 코드의 시간 복잡도

1. Add : O(n)

• DoublyLinkedList로 구현했다.
  • Index <= (size / 2) 일 때, head부터 순차적으로 탐색한다.
  • Index > (size / 2)일 때, tail부터 순차적으로 탐색한다.
  • O(n/2)이지만 2는 버리므로, O(n)

2. Delete : O(n)

• Index를 head부터 순차적으로 탐색하기 때문에 O(n)

3.Search : O(n)

• Index에 따라서 순차적으로 탐색해 해당 데이터와 일치 여부 확인
• O(2n) → O(n)

Java Collection

• Collection FrameWork는 Iterable inteface를 상속받아 사용한다.(foreach문 사용 가능)
• Collection FrameWork: 데이터를 저장하는 클래스들을 표준화한 설계
• 데이터, 자료구조인 컬렉션과 이를 구현하는 클래스르 정의하는 인터페이스를 가지고 있음
• 하단 : 실제 코드에서 상속받고 있는 사진

주요 인터페이스의 특징

1. List : 순서가 있는 데이터의 집합 (데이터의 중복을 허용한다.)
   • Vector, ArrayList, LinkedList, Stack, Queue
2. Set : 순서가 없는 데이터의 집합으로, 데이터 중복을 허용하지 않음.
   • HashSet, TreeSet
3. Map : 키와 값의 한 쌍으로 이루어지는 데이터의 집합으로, 순서가 없음. 
   • HashMap, TreeMap, HashTable, Properties

LinkedList로 Queue 구현하기

Queue는 FIFO(First In First Out)형태의 자료구조 입니다. (흔히, 선입선출 구조라고도 합니다.)

흔히 현실세계에서 접할 수 있는 형태은 은행업무, 마트에서 계산 등을 예시로 들 수 있습니다.

큐는 단일 연결 리스트(Sigle LinkedLIst)만으로도 구현이 가능합니다.

1. Offer : 값 추가 메서드

• LinkedList의 addLast는 가장 뒤에 노드를 추가하는 메서드입니다.
• Queue의 FIFO 구조이기 떄문에 가장 마지막 노드에 노드를 추가해야 합니다.
• 그러므로 LinkedList의 addLast과 같은 작동 로직을 구현하면 Offer를 사용할 수 있습니다.
• (temp = temp.next)형태로 값을 순회해서 가장 마지막에 있는 노드 발견 시, 제거하도록 합니다.

2. Poll: 값 삭제 메서드

•  LinkedList의 poll() 메서드는 가장 먼저 들어온 값을 제거해야 합니다.
• 가장 먼저 들어온 노드를 제거해야 합니다.
• 그러므로 LinkedLIst의 removeFirst와 같은 로직을 이용해서 구현하면 Poll를 구현할 수 있습니다.
• (head.next = head로 설정해서 값을 제거하도록 한다.)

3. Peek : 값 확인 메서드

• Queue의 peek()메서드는 가장 앞에 위치한 값을 확인하는 메서드입니다.
• 그래서 가장 앞에 노드(head)의 데이터를 확인하도록 합니다.

LinkedList로 Deque 구현하기

Deque는 Double-Ended Queue의 줄임말로 큐의 양쪽에서 삽입과 삭제가 모두 발생할 수 있는 큐 형태라고 생각하시면 편합니다. 흔한 예시를 들자면 어렸을 때 즐겨먹던 멘토스(mentos)를 예시로 들 수 있습니다. 굳이 한쪽에서 빼먹을 필요없이 양쪽에서 모두 뽑을 수 있는 형태를 띄고 있기 때문입니다

Deque의 경우 양쪽에서 삽입과 삭제가 이루어져야 하기 때문에 DoublyLinkedList를 사용하는 것이 유용합니다. 😆

1. addFirst : 앞 부분(head)에 노드를 추가하는 메서드

• 가장 앞부분을 참조하고 있는 head노드 앞에 새로운 노드를 추가하도록 합니다.
• 새로운 노드를 생성합니다.
• head의 이전 노드로 새로운 노드를 참조합니다.(head.prev = newNode)
• 새로운 노드의 다음노드로 head노드를 참조합니다.(newNode.next = head)

2. addLast: 뒷 부분(tail)에 노드를 추가하는 메서드

• Queue에서의 Offer와 같은 로직으로 처리합니다.(윗부분에 있어요.)

3. removeFirst : 앞 부분(head)에 노드를 제거하는메서드

• Queue에서의 poll()와 같은 로직으로 처리합니다.(윗부분에 있어요.)

4. removeLast: 뒷 부분(tail)에 노드를 제거하는 메서드

• tail Node를 tail의 이전 노드로 설정한다. (tail = tail.prev)
• 현재 tail의 다음노드 참조를 제거한다.(tail.next = null)