Today I Learned

오늘 할일
1. LeetCode
2. DevOps공부 계획 수립 및 세모봉 검토
3. 주유할인카드 발급
4. 토익 매일 LC RC
5. 영상처리 과제
6. 창엔 업무
7. 알고리즘 과제
8. 소프트웨어 공학 과제 소스1 & 소스2
9. 인공지능, 알고리즘 교재 구매
10. GATE 사전 조사

오늘 한일
1. LeetCode

• 2130. Maximum Twin Sum of a Linked List는 연결리스트에서 i, n-i꼴의 쌍둥이?원소의 합의 최댓값을 리턴하는 문제이다.
        이를 위해서는 우선 가장 간단한 방법으로 size를 알아내며 각 원소를 stack에 push한다. 그 뒤 다시 처음부터 원소와, stack pop과의 합 중 최댓값을 비교하면 된다. 다만 이를 위해서는 size/2번째에서 알아서 멈춰야 한다. 생각보다 간단해 보이기에 바로 시도해보자.
        

만약 효율성을 높이고 싶다면 어떻게 하면 좋을까?
우선 현재의 코드는 불필요한 코드마저 stack에 push한다는 단점이 있다. 생각해보니, n회의 순회를 하며 size를 구하는 과정에서 stack이 아닌 리스트에 넣어
일반 배열을 다루듯이 i, n-i로 접근하면 어떻까?

시간복잡도가 좋아졌다. 다만 공간복잡도는 나빠졌다.

그럼, 어떻게해야 별도의 API사용 없이 리팩토링이 가능할까?
혹시나 해서 주솟값을 확인해보았는데 연속성이 없다.

가장 좋은 것은 1회의 순회로 최댓값을 구하는 것인데.. 어떻게하면 가능할까? 공간복잡도도 고려하려면 api없이 해야한다.
생각이 나지 않아 api없이 하는 가장 간단하고 이상적인 방법으로 해보겠다. n회의 순회로 전체 사이즈를 구하고, 매 원소마다 next를 타고 적절한 위치의 값을 가져오겠다. api사용이 없기에 생각보다 빠를 수도 있겠다는 생각이 문득 들었다.

public int pairSum(ListNode head) {
        int size=1;
        ListNode iter=head;
        while(iter.next!=null){
            iter=iter.next;
            size++;
        }

        int max=0;
        iter=head;
        ListNode iter2;
        int val;
        for(int i=0; i<size/2; i++){
            iter2=iter.next;
            for(int j=i+1; j<size-1-i; j++){
                iter2=iter2.next;
            }
            val=iter.val+iter2.val;
            if(val>max)
                max=val;
            iter=iter.next;
        }
        
        return max;
    }

그 결과 TLE가 발생하였다.

어떻게 해야 빠른 접근이 가능할지 생각이 안나 다른 사람들의 제출안을 확인해보니 내가 10ms를 기록했던 방법과 같았다. 다만 List가 아닌 Array를 사용하였다.
해당 아이디어로 접근해보자.

public int pairSum(ListNode head) {
        int size=1;
        ListNode iter;
        for(iter=head; iter.next!=null; iter=iter.next)
            size++;

        int[] array=new int[size];
        int i=0;
        for(iter=head; iter.next!=null; iter=iter.next, i++)
            array[i]=iter.val;
        array[i]=iter.val;

        int val, max=0;
        for(i=0; i<size; i++){
            val=array[i]+array[size-1-i];
            if(val>max)
                max=val;
        }

        return max;
    }

이유는 배열과 List의 속도차이인 듯 하다. ArrayList는 API이기에 원소의 저장이 연속적이지 않는 반면, 일반 배열은 원소의 주소가 연속적으로 저장되기에 보다 빠른 접근이 가능해서인 듯 하다. 고로 size를 알 수 있다면 List보다는 배열을 지향하는 편이 시간복잡도 관점에서 좋다는 점을 알 수 잇었다.
리스트는 삽입과 삭제가 용이하고, 배열은 인덱스를 이용한 검색이 용이하다. 기본적으로 사용할 수 있는 ArrayList는 LinkedList보다 순차적으로 삭제, 삽입하는 과정에서 보다 좋은 성능을 보인다. 검색은 웬만하면 배열을 사용하는 것으로 하자.

2. DevOps공부 계획 수립 및 세모봉 검토
방학 때 검토했던 K-mooc강의 창의 N-Tree기간에 강의만이라도 시청

• Cloud(클라우드) 인프라 관리 및 실무 기초 (2022) Part.1 베이그런트, 도커, 트랜드 및 성능진단
• 클라우드 인프라 아키텍처 양성과정
• 오픈소스를 활용한 DevOps 환경 이해

세모봉은 혼자 생각해봤을 때, 기관과의 연동 이전에 1365, vms등 여러 봉사기관의 실시간 데이터를 크롤링하여 지도에 종합적으로 표시하는 것 구현해보기. 해당 기능 구현 이후 위의 devops지식으로 인프라 구축하기.

3. 토익
정해진 시간을 내기가 정말 쉽지 않다.. 두시간의 시간을 내기에 수요일 영상처리 끝나고 2시~4시가 그나마 가장 적절해 보이니 시험지를 미리 준비해가야할 듯 하다. 하지만 그마저도 힘들어보이기 때문에, 가천대학교 전자도서관 해커스의 매일 LC RC풀기를 강의 쉬는시간에 진행하는 것으로 하겠다.