지금의 기록이 미래의 자산이 된다.

• [Algorithm] 프로그래밍 문제 접근법 - 문제 해결

  2023-03-17

  devFancy

  AlgorithmSkill
  • 절차
    • 시나리오
    • 문제
    • 어떤 언어를 사용할 것인가
    • 소통이 핵심이다.
  • 문제 해결
    • 기본 단계
    • 문제를 풀다가 막히는 경우
  • Reference

  이 글의 코드와 정보들은 책을 공부하며 정리한 내용을 토대로 작성하였습니다.

  절차

  • 코딩 문제에서 가장 중요한 것은 지원자의 코딩 실력이 어느 정도 되는지를 가늠하는 것이다.

  • 면접관은 지원자가 작성한 코드와 지원자의 대답을 바탕으로 채용 추천 여부를 결정하기 때문에 면접에서 가장 중요한 것이 바로 코딩 문제라고 할 수 있다.

  시나리오

  • 코딩 문제는 면접관과 일대일로 진행하는 것이 일반적이다.

  • 컴퓨터 혹은 종이와 펜을 주고 코드를 작성할 수도 있다.

  • 보통은 함수나 메서드를 만드는 경우가 많지만 클래스를 정의하거나 연관된 코드 모듈을 만드는 경우도 가끔 있다.

  문제

  • 면접관이 물어보는 문제에는 특별한 요구 조건이 주어진다.

  • 비교적 짧은 시간안에 풀어야 하므로 변별력을 위해 적당히 복잡한 문제가 출제된다.

  • 따라서 실전에 직접 적용할 수 있는 코드를 만드는 문제가 나올 가능성은 희박하다.

  • 대신 특별한 트릭이나 언어에서 자주 쓰이지 않는 기능들을 필요로 하는 것들이 많다.

  • 가장 흔히 쓰이는 방법이나 이상적인 자료구조를 못 쓰게 하는 경우도 종종있다. 예를 들어 “비교 연산자를 전혀 사용하지 않고 두 정수가 같은지 판단하는 함수를 만드시오” 와 같은 문제가 나올 수도 있다.

  • 만약 그런 제약 조건이 없을 때 문제를 풀 방법을 설명한 다음에 주어진 대로 문제를 풀도록 하자.

  어떤 언어를 사용할 것인가

  • 일반적인 프로그래밍 또는 개발 업무에 지원한다면 자바, 파이썬, 자바스크립트, C#, C++ 같은 주류 언어를 제대로 쓸 수 있는 정도면 충분하다.

  • 면접을 하러 가기 전에 자신이 사용할 언어의 사용법 및 문법을 제대로 숙지해야만 한다.

  소통이 핵심이다.

  • 면접관 입장에서 지원자가 만든 코드 중에 직접 본인의 눈으로 확인해볼 수 있는 코드는 면접 시에 작성한 코드뿐이다.

  • 따라서 면접 시에 최고의 코드를 만들 수 있어야 한다. 자신이 사용할 언어를 가다듬고 가능하면 가장 좋은 코드를 만들자.

  • 프로그래밍 문제는 코딩 실력과 문제 해결 능력을 동시에 평가할 수 있도록 만들어진다.

  • 면접관이 정말로 원하는 것은 지원자가 문제를 푸는 각 단계들을 어떻게 진행하는지를 보는 것이다.

  • 이런 면접에서 문제를 풀 때는 지원자와 면접관이 계속해서 의견을 주고받게 되며, 문제를 풀다가 막히면 면접관이 힌트를 제시하면서 정답을 맞출 수 있도록 도와준다.

  • 지원자가 힌트를 받은 다음에 자신의 능력으로 문제를 풀어나가는 동안 보여주는 사고력과 문제 해결력 또한 매우 중요하다.

  • 각 단계를 차근차근히 밝아나가면서 각 단계를 해결하는 사고 과정을 정리해서 대답해야 한다.

  • 중요한 것은 어떤 프로그래밍 퍼즐의 정답을 외워서 말하는 것이 아니라 그 밑에 깔려 있는 개념을 제대로 이해하고 있다는 것을 보여주는 것이기 때문이다.

  • 문제를 푸는 과정에서 자신의 프로그래밍에 대한 지식 전반을 보여주기 위해 문제와 연관된 다른 내용을 언급하고 싶은 경우가 있다.

  • 그런 기회가 있으면 저 이런 지식도 갖고 있어요와 같이 논리적인 사고 능력을 갖추고 있으면서도 컴퓨터에 대한 지식도 출중하고 의사소통에도 능하다는 것을 보여줘야 한다.

  • 문제를 풀 때 항상 무슨 일을 하고 있는지 계속해서 설명하는 습관을 가지자.

  문제 해결

  • 문제를 풀때 우선 문제를 완벽하게 이해하는 것이 중요하다.

  • 몇 가지 구체적인 예를 시도해보고, 문제 해결 과정을 알고리즘으로 일반화하고 제대로 된 알고리즘이 만들었다는 확신이 설때 그 내용을 분명하게 설명하자.

  • 코드 작성은 가장 마지막에 할 일이다.

  기본 단계

  • 면접 문제를 해결하는 가장 좋은 방법은 쳬게적인 접근법이다.

  [1] 문제를 확실히 이해한다.

  • 문제를 이해하지 못하면 주저하지 말고 면접관에게 문제에 대한 질문을 해야 하며, 제대로 이해하기 전에 무작정 풀기 시작하는 일은 금물이다.

  • 진짜 문제가 되는 부분을 찾아내서 그런 부분을 분명히 하기 위한 제대로 된 질문을 던지는 것이 정답으로 가는 데 있어서 핵심이 될 수 있다.

  [2] 일단 문제를 이해하고 나면 간단한 예를 시도해본다.

  • 이렇게 예를 시도하다 보면 문제를 어떻게 풀어야 할지 감을 잡을 수도 있고, 혹시라도 잘못 이해한 부분이 있을 경우 오류를 정정할 수도 있다.

  • 예를 시도하는 것은 체계적이고 논리적인 사고 능력을 보여줄 수 있는 기회가 되기도 한다.

  [3] 문제 풀이에 사용할 알고리즘과 자료구조에 초점을 맞춘다.

  • 이 단계에서는 면접관과의 의사소통이 중요하다.

  • 계속해서 면접관에게 지금 무엇을 하는지 얘기하자. 얘기를 하다 보면 면접의 핵심이라고 할 수 있는 자신의 능력을 보여주는 데도 도움이 되고, 면접관이 힌트를 줄 수도 있다.

  • (1)문제에 대해서 오랫동안 생각해서 한 번에 제대로 된 코드를 짜는 사람과 (2)무턱대고 달려들어서 코딩하면서 계속 에러만 내고 내가 지금 뭘 하고 있는지 파악도 안 되는 사람 가운데 어떤 사람과 일하고 싶은 마음이 생길지 입장 바꿔 생각해보자.

  • 당연히 전자 쪽이 더 나을 것이다.

  [4] 알고리즘과 구현 방법을 알아내고 나면 면접관에게 풀이를 설명한다.

  • 이렇게 하면 지원자가 코딩을 시작하기 전에 면접관이 풀이에 대해 어느 정도 평가해볼 수 있다.

  • 면접관이 긍정 또는 부정적인 의견을 내거나, “안 되는 건 아닌 것 같은데, 분명 더 효율적인 풀이법이 있을 것 같네요” 같은 응답도 나올 수 있다.

  • 어느 쪽이든, 코딩으로 넘어갈지 알고리즘을 다시 살펴봐야 할지에 대해 아주 중요한 정보를 얻을 수 있다는 것은 분명하다.

  [5] 코딩을 할 때도 뭘 하고 있는지 설명한다.

  • 예를 들어, “여기에서는 배열을 전부 0으로 초기화합니다” 같은 식으로 설명을 한다면, 면접관 입장에서 코드를 더 쉽게 따라 갈 수 있다.

  풀이에 대한 코드를 작성하기 전에, 그리고 코드를 작성하는 도중에도 계속해서 설명을 하자. 끊임없이 떠들자.

  [6] 필요하다면 질문을 한다.

  • 레퍼런스에서 찾을 수 있을 법한 내용이라면 면접관한테 질문을 해도 큰 감점 사유가 되진 않는다.

  • 예를 들어, “잘 기억이 안나서 그러는데요, 지역화된 날짜 시각을 출력할 때 어떤 형식 문자열을 쓰는지 알 수 있을까요?” 같은 질문은 별로 해가 되진 않는다.

  [7] 코드를 완성하고 나면 바로 몇 가지 예를 시도해보고 맞는지 확인한다.

  • 자기가 만든 코드가 적어도 자기가 시도해본 예에 대해서 제대로 작동한다는 것을 분명하게 보여줄 수 있다.

  • 그리고 자신의 사고 과정 및 결과를 확인하고 버그를 찾아내고자 하는 업무 자세를 보여줄 수 있는 기회도 된다.

  [8] 모든 오류 및 특수 상황, 특히 경계 조건을 확인한다.

  • 프로그래밍을 하다 보면 오류나 특수 상황을 무시하는 경우가 종종 있다.

  • 모두 작성할 시간 여유가 없다면 적어도 말로 오류 확인이 필요하다는 설명은 해줘야 한다.

  • 오류 및 특수 상황을 제대로 커버하면 면접관에게도 좋은 인상을 남길 수 있고 문제를 올바르게 푸는 데도 도움이 된다.

  문제를 풀다가 막히는 경우

  • 문제를 풀다가 막히는 일은 흔이 일어나는 일이며, 이것 자체도 면접의 중요한 부분이라고 할 수 있다.

  • 만약 문제를 풀다가 갑자기 막히게 됐을 때 포기하거나 좌절하는 것은 최악의 대응책이다.

  • 계속해서 문제에 대한 관심을 가지고 문제를 풀려고 시도하는 모습을 보이자.

  예를 다시 따져본다.

  • 예를 다시 확인하면서 지금 하고 있는 것을 분석해보자. 시도했던 특정 예를 일반적인 경우로 확장시켜보자.

  • 면접관에게 정답을 찾아내기 위한 끈기를 보여줄 수 있는 셈이기 때문에 크게 나쁠 것은 없다.

  다른 자료구조를 시도해본다.

  • 연결 리스트, 배열, 해시 테이블, 이진 검색 트리 같은 다양한 자료구조를 써보자.

  • 올바른 자료구조를 사용하는 것만으로 문제 풀이가 훨씬 수월해지는 일도 흔하다.

  언어에서 그리 많이 쓰이지 않는 기능 또는 고급 기능을 고려해보자.

  • 때때로 그런 기능을 활용하는 것이 문제 풀이의 핵심이 되는 경우도 있다.

  면접에서 다루는 코딩 문제의 답은 대체로 짧은 편이다.

  코드가 30줄을 넘기는 경우도 드문 편이고, 50줄을 넘기는 일은 거의 없다고 봐도 된다.

  코드가 너무 길어지면 엉뚱한 방향으로 가고 있을 수도 있다.

  Reference

  프로그래밍 면접 이렇게 준비한다

  Read All

  ---

• [Programmers] SQL > Join 풀이 모음

  2023-03-15

  devFancy

  Algorithm
  • 구분
  • 조건에 맞는 도서와 저자 리스트 출력하기
  • 그룹별 조건에 맞는 식당 목록 출력하기

  구분

  • 코딩테스트 연습 > SUM, MAX, MIN

  조건에 맞는 도서와 저자 리스트 출력하기

  조건에 맞는 도서와 저자 리스트 출력하기 - 문제 링크

  SELECT 
      BOOK.BOOK_ID,
      AUTHOR.AUTHOR_NAME,
      DATE_FORMAT(BOOK.PUBLISHED_DATE, '%Y-%m-%d') AS PUBLISHED_DATE
  FROM 
      BOOK
  INNER JOIN 
      AUTHOR
  ON 
      BOOK.AUTHOR_ID = AUTHOR.AUTHOR_ID
  WHERE
      BOOK.CATEGORY = '경제'
  ORDER BY 
      BOOK.PUBLISHED_DATE ASC;
  

  그룹별 조건에 맞는 식당 목록 출력하기

  그룹별 조건에 맞는 식당 목록 출력하기 - 문제 링크

  Read All

  ---

• [Programmers] 92341. 주차 요금 계산

  2023-03-12

  devFancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(2023.03.12)
    • 문제 풀이 - Answer Code1

  문제 링크

  성능 요약

  • 메모리: 73.8 MB, 시간: 0.44 ms

  구분

  • 코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT

  Answer Code1(2023.03.12)

  /*
      기본 시간 : 180분
      기본 요금 : 5000(원)
      단위 시간 : 10(분)
      단위 요금 : 600(원)
   */
  /*
      fees[0] = 기본 시간(분)
      fees[1] = 기본 요금(원)
      fees[2] = 단위 시간(분)
      fees[3] = 단위 요금(원)
   */
  /*
      `records`의 각 원소는 "시각 차량번호 내역" 형식의 문자열(공백으로 구분)
      시각은 `HH:MM` 형식의 길이가 5인 문자열
      차량번호는 자동차를 구분하기 위한, `0` ~ `9`로 구성된 길이 4인 문자열
      내역은 `IN` 또는 `OUT`의 길이가 2 또는 3인 문자열
      `records`의 원소들은 시각을 기준으로 오름차순으로 정렬됨
      `records`는 하루 동안의 입/출차된 기록만 담고 있음. 
      마지막 시각(23:59)에 입차되는 경우는 입력으로 주어지지 않음.
   */
  
  import java.util.*;
  
  class Solution {
    public int[] solution(int[] fees, String[] records) {
  
      int std_time = fees[0];
      int std_pay = fees[1];
      int per_time = fees[2];
      int per_pay = fees[3];
  
      //key: 차량번호, value: 입장 시간
      Map<Integer, Integer> map = new HashMap<>();
      //key: 차량번호, value: 주차 요금
      Map<Integer, Integer> result = new TreeMap<>();
      // 주차기록 처리하기
      for (String data : records) {
        String[] temp = data.split(" ");
        int time = cal_time(temp[0]);
        int car_num = Integer.parseInt(temp[1]);
        String state = temp[2];
        if (state.equals("OUT")) {
          int start = map.get(car_num);
          int use_time = time - start;
          if (result.containsKey(car_num)) {
            int a = result.get(car_num);
            use_time += a;
          }
          result.put(car_num, use_time);
          map.remove(car_num);
          continue;
        }
        map.put(car_num, time);
      }
  
      // 아직 안나간 차량 처리
      for (int num : map.keySet()) {
        Integer d = map.get(num);
        d = d == null ? 0 : d;
  
        int start = d.intValue();
        int use_time = 1439 - start;
  
        Integer e = result.get(num);
        e = e == null ? 0 : e;
  
        int total = e.intValue();
  
        result.put(num, total + use_time);
      }
  
      // 출력하기
      int[] answer = new int[result.size()];
      int i = 0;
      for (int data : result.keySet()) {
        int time = result.get(data);
  
        if (time <= std_time) {
          time = std_pay;
        } else {
          time = std_pay + (int) Math.ceil((double) (time - std_time) / per_time) * per_pay;
        }
        answer[i] = time;
        i++;
      }
  
      return answer;
    }
  
    public int cal_time(String time) {
      String[] temp = time.split(":");
      int hour = Integer.parseInt(temp[0]) * 60;
      int min = Integer.parseInt(temp[1]);
      return hour + min;
    }
  }
  

  문제 풀이 - Answer Code1

  문제 풀이에 도움을 주신 류창님께 감사의 말씀 전합니다.

  출력 결과 : 차량 번호가 적은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return 한다.

  목표 : 차량 기록을 모두 처리한 이후에 각 차량마다 주차요금을 구하는 문제 (차량 번호를 기준으로 오름차순한다)

  

  • [1] 기본 시간, 기본 요금, 단위 시간, 단위 요금을 보기 쉽게 분리하였다.

    • 그런 다음, 2개의 Map을 준비했다.

    • 차량 번호를 오름차순으로 정렬해야하기 때문에 TreeMap으로 설정했다.

  Read All

  ---

• [Programmers] 138476. 귤 고르기

  2023-03-08

  devFancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(2023.03.08)
  • 문제 풀이 - Answer Code1
  • Reference

  문제 링크

  성능 요약

  • 메모리: 98.7 MB, 시간: 46.69 ms

  구분

  • 코딩테스트 연습 > 구현

  Answer Code1(2023.03.08)

  
  import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  import java.util.Collections;
  
  class Solution {
      
      public int solution(int k, int[] tangerine) {
          int answer = 0;
          Map<Integer, Integer> map = new HashMap<>();
          
          
          // 크기별로 몇 개 있는지 map에 저장함
          for (int tan : tangerine) {
              map.put(tan, map.getOrDefault(tan, 0)+1);
          }
  
          // 개수(value)가 많은 순으로 정렬
          List<Integer> list = new ArrayList<>(map.values());
          Collections.sort(list, Collections.reverseOrder());
  
          // 개수가 많은 순부터 사용
          for (Integer a : list) {
              if(k < 1) 
                  return answer;
              k -= a;
              answer++;
          }
  
          return answer;
      }
  }
  

  문제 풀이 - Answer Code1

  • 귤의 크기(key)와 개수(value)를 Map에 저정한 다음, 개수가 많은 순부터 사용하여 k개를 채우면 되는 문제였다.

  • HashMap()의 getOrDefault(key, defaultValue)는 지정된 key의 값(객체)을 반환한다. key가 없으면 지정된 defaultValue로 지정된 객체를 반환한다.

  Reference

  • 귤 고르기 - 풀이
  Read All

  ---

• [Programmers] 12924. 숫자의 표현

  2023-03-07

  devFancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(2023.03.07)
  • Review

  문제 링크

  성능 요약

  • 메모리: 51.6 MB, 시간: 1.21 ms

  구분

  • 코딩테스트 연습 > 연습문제

  Answer Code1(2023.03.07)

  class Solution {
      public int solution(int n) {
           int answer = 0;
            
            for(int i = 1; i <= n; i++) {
                int sum = 0;
                for(int j = i; j <= n; j++) {
                    sum += j;
                    
                    if(sum == n) {
                        answer++;
                        break;
                    } else if(sum > n) {
                        break;
                    }
                }
            }      
            return answer;
      }
  }
  

  Review

  • 연속한 자연수들로 표현 하는 방법을 어떻게 풀이할지 생각하다가 이중 for문으로 구현했다.
  Read All

  ---