Today I Learned

오늘 할일
1. LeetCode
2. 인프라 강의
3. 세모봉 개발
4. 매일 토익
5. 소웨공 공부

오늘 한일
1. LeetCode

• 굉장히 오래걸리고 있는 Path Sum III을 디버깅 중이다. 코드 구조를 queue로 바꾸어봤는데도 동일한 부분에서 오류가 발생한다.

class Solution {
    private int hit_count=0;
    private int target_sum;
    private Queue<TreeNode> queue=new LinkedList<>();

    private void DFS(TreeNode node, int current_sum){
        if(node==null){
            return;
        }
        if(node.left!=null)
            queue.add(node.left);
        if(node.right!=null)
            queue.add(node.right);
        
        current_sum+=node.val;
        if(current_sum==target_sum)
            this.hit_count++;
        
        DFS(node.left, current_sum);
        DFS(node.right, current_sum);//분리필요. node.val=3, current_sum=0인 경우  2개 발생
    }

    public int pathSum(TreeNode root, int targetSum) {
        this.target_sum=targetSum;
        this.DFS(root, 0);
        while(!queue.isEmpty()){
            this.DFS(queue.remove(), 0);
        }
        return this.hit_count;
    }
}

여러 상태를 출력하여 체크해본 결과 1,2,3,4,5 이진트리에서 노드 3이 두번 체크되고 있는 것을 확인할 수 있었다.

이 과정에서 DFS의 순회 방식에서 문제가 있음을 발견, 코드를 전부 지우고 처음부터 시작하며 모든 node의 val값을 출력하게끔하여 본래의 순환을 먼저 확인하였다. 기존의 과정은 DFS과정에서 left와 right에서 새로 탐색하는 결과도 포함하기 위해 DFS를 4번 호출하였는데 이가 화근이었다. 기본적인 DFS순회를 건들기보다 DFS순회를 그대로 활용하며 어떻게 처리해야할지를 고안했다. 그 결과 DFS함수를 두개 만들어서 처리해보았다. 첫 DFS는 순회를 진행하며 모든 노드를 Queue에 넣는다. 두번쨰 DFS는 Quque의 값을 빼어 일반 DFS를 진행한다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int hit_count=0;
    private int target_sum;
    private Queue<TreeNode> queue=new LinkedList();

    private void DFS(TreeNode node, long current_sum){
        if(node==null)
            return;
        if(node.left!=null)
            queue.add(node.left);
        if(node.right!=null)
            queue.add(node.right);
        
        current_sum+=node.val;
        if(current_sum==this.target_sum)
            this.hit_count++;

        DFS(node.left, current_sum);
        DFS(node.right, current_sum);
    }
    private void DFS2(TreeNode node, int current_sum){
        if(node==null)
            return;

        current_sum+=node.val;
        if(current_sum==this.target_sum)
            this.hit_count++;
        
        DFS2(node.left, current_sum);
        DFS2(node.right, current_sum);
    }

    public int pathSum(TreeNode root, int targetSum) {
        this.target_sum=targetSum;
        this.DFS(root, 0);
        while(!queue.isEmpty()){
            this.DFS2(queue.remove(), 0);
        }

        return this.hit_count;
    }
}

그 결과 상당한 발전이 있었다. 새롭게 맞이한 테스트케이스를 보면 큰수의 연산으로 오버플로우를 일으키는 방식의 케이스이다. 이 케이스는 잘못되었는데, 문제에 기재된 node값의 제한이 0~1000이기 때문이다.

타입을 long으로 바꾸어 해결하였다.

2. 매일 토익

• LC 2/5
  
• envelope 봉투_He's reaching inside an envelope.
• Hmm... we should probably adjust our menu prices. We're actually about 20 percent cheaper than our nearest competitor. I don't think our customers would mind an increase. 일반적으로 가격 상승 선지에 대해 increase같은 단어를 그대로 사용하기보다 조정하다같은 표현으로 사용하니, 영 단어를 생각하며 듣기보다 한글 의미와 문맥을 생각하며 듣는 게 좋을 듯. 또 위 예시의 don't mind처럼 부정부정을 띄워서 사용하니 can't 같은 부정문을 우선 잘 캐치하자.
• RC1 1/3
  
• 쉬운 문법이더라도 단수, 복수에 주의하자.
• transcript 성적증명서, accompany동반되다_For your job application to be accepted, a graduate transcript must accompany your letter of introduction, resume, and reference letters. 해당 지문에서는 같이 제출해야한다 의미로 사용됨.

• RC2 1/4
• addition 증원인력_You would be a great addition to your team.

3. 인프라 강의

• 오픈소스를 이용한 DevOps