오늘 할일
1. LeetCode
2. DevOps공부 계획 수립 및 세모봉 검토
3. 주유할인카드 발급
4. 토익?
5. 인공지능 개론 과제(boston 집값 feature selection, 붓꽃에서 sepal length를 예측하는 regression으로 변경, KNN붓꼴)
6. 창엔 업무
오늘 한일
1. LeetCode
- Reverse Linked List은 연결리스트를 역순정렬하는 문제이다.
하지만 이전의 문제에서도 그렇듯, 자바에서의 컬렉션 대입 시 발생하는 얕은 복사에 대한 이해가 부족하여 우선 전략을 수립하기로 했다.
가장 쉬운 방식은 size를 구한 뒤 size에 맞게 원소를 새로 생성하는 방식이다. 다만 이 방법은 (1+n)/2만큼의 순회가 발생한다.
또다른 방식은 stack에 list원솔르 넣고 pop하며 연결시키는 것이다. 이는 2n만큼의 순회가 발생한다.
가장 좋은 방법은 n의 순회로 끝나는 것이다.
n순회로 끝내는 방법은 새로 head를 만들어 앞에서부터 집어넣는 것이다. 이는 공간복잡도 2n이 발생한다.
n번위 순회, 공간복잡도 n이 발생하게하는 방법은 실시간으로 순회하여 next값을 바꾸어 역순으로 연결해주는 것이다.
역순으로 바꾸어주는 코드는 간단하다.
iter.next=prev;
다만 이 경우 iter.next에 더이상 접근이 불가능하다는 단점이 있다. 이를 저장하는 새로운 변수를 둬보자.
next_prev=iter
next_iter=iter.next
iter.next=prev
prev=next_prev
iter=next_iter
이때 이전과 마찬가지로 iter.next=prev;시 iter이 2->1->2->1->...처럼 cycle이 생긴 것을 확인할 수 있었다. 이를 해결하고자 초기의 prev.next값을 null로 초기화하였다. 또 종료조건을 iter.next!=null로 하고 iter을 반환하는 것은 iter의 next 포인터 설정에서 null값을 참조하는 경우가 발생하는 듯 하여 종료조건을 iter!=null로 변경한 후 prev값을 리턴시켰다.
- Maximum Twin Sum of a Linked List은 나도 아직 모르겠다.
