TIL_20230512

TIL

TIL_20230512

번잔중 2023. 5. 12. 23:53

오늘 할 일

LeetCode 데일리 문제 풀기
~~Heart - 게시판 글 수정 및 삭제 이미지 처리 로직 작성하기~~ → SKCT 준비

오늘 배운 것

LeetCode 데일리 문제 풀기

오늘의 문제: 2140. Solving Questions With Brainpower(https://leetcode.com/problems/solving-questions-with-brainpower/)
난이도: Medium
문제 조건
- 0으로 시작하는 2차원 배열 questions가 주어지고, questions[i] = [pointsi, brainpoweri]이다.
- 배열은 문제를 순서대로 처리하고(예: 0번 문제부터 시작) 각 문제를 풀지 건너뛸지 결정해야 하는 시험 문제를 설명한다. i번째 문제를 푸는 것은 당신에게 포인트를 줄 것이지만 당신은 다음 브레인 파워 문제를 각각 풀 수 없을 것이다. 질문 i를 건너뛰면 다음 질문에 대한 결정을 내릴 수 있다.
  - 예를 들어 questions = [[3, 2], [4, 3], [4, 4], [2, 5]]이 주어졌다고 가정한다.
    1. 만약 0번째 문제를 풀었다면 당신은 3 포인트를 얻게되지만 1번과 2번 문제를 풀 수 없다.
    2. 대신 0번째 문제를 건너뛰고 1번 문제를 풀었다면 4 포인트를 얻게 되지만 2번과 3번 문제를 풀 수 없다.
- 시험에서 얻을 수 있는 최대 점수를 반환해라.
문제 해결 과정
- 시간복잡도 상으로는 O(N)까지 허용된다. for문 하나 정도는 가능하지만 그 이상은 어렵다.
- dp로 풀었을 경우, 스킵하는 경우를 따져보고 최대값을 찾아볼 수 있을 것 같다!
- 또 답봄 ^^
- 이 문제는 questions의 길이 + 1의 dp를 새로 생성해준다. dp의 마지막부터 맨 처음까지 순차적으로 돌면 dp[0]이 최댓값(정답)이 되며 스킵하는 경우와 스킵하지 않는 경우를 dp에서 모두 체크해줄 수 있다.
- Example1을 기준으로 설명한다.
  - dp[n + 1]은 dp[5]이므로 dp의 공간은 총 5개이다. [0, 0, 0, 0, 0]에서 questions의 맨 마지막 point가 2일 때, 해당 문제를 skip하면 0, solve하면 2가 되어야 한다. 대신 정답을 저장할 때는 index - 1의 위치에 저장해야 한다. 그 이유는 dp의 마지막은 모두 skip한 경우를 따져주는 것이기 때문이다.
  - 그 다음으로 인덱스를 하나 빼주면 point가 4이고, 해당 문제를 skip하면 그대로 2가 되고, solve하면 4가 된다.
  - 그렇게 순차적으로 dp를 채워가면 최종적으로 배열 dp = [5, 4, 4, 2, 0]이 된다. 즉 dp의 첫 번째 값이 항상 최대값이 된다.
- 여기서 nextQuestion = Math.min(n, i + brainPower + 1)인 이유는 다음 문제를 푸는데 소요되는 brainPower를 고려해야 하기 때문이다. 만약 i번째 문제를 solve한다면 그 다음 brainPower개의 문제를 skip해야 하기 때문이다. 그렇기 때문에 i번째 문제를 푼 경우 i + brainPower + 1이 풀 수 있는 다음문제가 된다.

SKCT 준비

코딩테스트 대비 용도로 이분 탐색 문제와 dfs 문제를 하나씩 풀었습니다.
이분 탐색 문제 - 입국심사(Programmers)
- l은 0, r에는 최악의 경우, 시간이 가장 오래걸리는 심사관이 n명을 모두 맡아서 수속하는 경우로 초기화한다.
- m은 l과 r의 중간값이고, sum은 심사대 별로 주어진 m 시간동안 몇 명을 심사할 수 있는지 모두 더한다.
- sum이 n보다 작다면 n명의 사람을 모두 심사할 수 없다는 의미이므로 l = m + 1, sum이 n 이상이라면 n보다 작은 경우가 존재할 수 있기 때문에 r = m - 1로 바꾸고, answer에 m 시간을 우선 저장한다. 만약 n과 같은 경우라면 while문을 빠져나올 수 있다.

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        Arrays.sort(times);
        
        long l = 0;
        long r = times[times.length - 1] * (long) n;
        
        while (l <= r) {
            long m = (l + r) / 2;
            long sum = 0;
            for (int i = 0; i < times.length; i++) {
                sum += m / times[i];
            }
            if (sum < n) {
                l = m + 1;
            } else {
                r = m - 1;
                answer = m;
            }
        }
        
        return answer;
    }
}

dfs 문제 - 타겟 넘버(Programmers)
- 우선 반환타입이 없는 dfs 메소드로 정답을 구하기 위해 class 변수(static)로 answer를 선언한다.
- dfs 메소드의 매개변수
  1. nums는 전체 배열의 길이를 반환
  2. depth는 노드의 깊이를 체크
  3. target은 찾아야 하는 숫자
  4. sum은 현재까지의 합
- dfs 함수 로직
  1. depth가 nums의 길이와 같아지는 순간 재귀함수의 종료 조건이 된다. 이 때, sum이 target과 같은 값이라면 answer를 하나 증가시킨다.
  2. depth가 아직 nums의 길이보다 작을 때, depth를 하나 증가시키고 sum에 +와 - 연산을 모두 수행한다.

class Solution {
    static int answer = 0;
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, target, 0);
        return answer;
    }
    
    private void dfs(int[] nums, int depth, int target, int sum) {
        if (depth == nums.length) {
            if (sum == target) {
                answer++;
            }
        }
            
        else {
            dfs(nums, depth + 1, target, sum + nums[depth]);
            dfs(nums, depth + 1, target, sum - nums[depth]);
        }
    }
}

SKCT 인적성 문제 - 유튜브로 문제 유형을 간단하게 익혀봤습니다.
실행역량(15분)
- 보통 답은 구렁이 담 넘어가듯 능글 맞음 + 문제에 대한 해결 방안인 보기이다.
- 목표
  - 문제를 100% 다 풀기
  - 오답은 체크하지 않기
  - 정답이 여러 개면 아무거나 찍기 → 다 푸는 것이 목표이기 때문!
- 문제 정리 - 내용을 아래 세 가지 기준으로 정리하자
  - 나는 누구인가? (신입 / 중간관리자 / 팀장) → 의사결정에 차이가 생긴다.
  - 문제 상황이 무엇인가? → 논리적 + 능동적인 답안을 골라야하기 때문
  - 제약 조건이 무엇인가? → 문제가 발생했지만 특정 조건이 달려서 나오기 때문에 정리해야 한다.
- 대표 오답 유형
  - 나 혼자 해결한다
  - 적절한 해결이 아닌 것 → 회사에서 문제가 발생하면 해결하는 것이 중요, 회피나 다른 조치는 오답이다.
  - 극단적인 보기
  - 회사 외부에 알리는 것 → 회사 일은 회사 내부 채널을 통해 해결해야 한다.
- 문제 읽는 방법
  - 맨 뒤에서부터 읽는다. → 당신이 ~라면 어떻게 할 것인가? 나 자신과 일치시키자.
  - 문제를 읽으면서 문제를 정리해본다.
  - 예시 1번
    1. 나는 누구인가 → 대리(일을 어느정도 하지만 중간관리자는 아닌)
    2. 문제 상황이 무엇인가? → 역량 부족으로 후배가 자신을 뒷담화 한다.
    3. 제약 조건이 무엇인가? → 없음
  - 예시 2번
    1. 나는 누구인가 → 신입(의사결정 하지마라!!!)
    2. 문제 상황이 무엇인가? → 주요 업무를 맡지 못함 + 낮은 평가
    3. 제약 조건이 무엇인가? → 없음
  - 예시 3번
    1. 나는 누구인가 → 과장(일 능숙 / 주도적 / 사원과 팀장의 다리 역할 - 중간관리자)
    2. 문제 상황이 무엇인가? → 사원이 팀 자료를 삭제해서 회의 자료가 없음
    3. 제약 조건이 무엇인가? → 회의 때까지 자료 준비 불가능
- 심층역량(60분) - 인성검사
  - 일관성
  - 극단적 보기는 X

느낀점

리트코드를 풀다보니 제가 못 푸는 문제들 유형이 많이 보이긴 하네요. dp나 dfs 문제를 상당히 싫어했는데, 그래도 요즘은 어떻게 코드를 보고나면 이해가 되긴 합니다. 혼자 힘으로 할 수 있을 때까지 더 열심히...
SKCT가 내일입니다. 아직 큰 회사에 갈 준비가 안된 사람이라고 생각하지만 시도는 해볼 수 있으니까요! 해보겠습니다.
해 봐야지예

내일 할 일

LeetCode 데일리 문제 풀기
SKCT 응시
운동하기 - 웨이트 트레이닝