오늘 할일

• 스프링 개발 실습
• 알고리즘 문제풀이
• 저녁 프로젝트 모임

오늘 한 것 & 배운 내용

알고리즘 문제 풀이

퇴사

• 문제 해석
  • 총일수 T와 일별로 받을 수 있는 상담의 소요기간(T)와 완료시 얻을수 있는 보상(P)가 주어질때 최대 많이 얻을 수 있는 보상을 출력하라
  • 1<= N <= 15, 1<T <5, 1 < P<1,000
• 풀이 계획
  • 완전 탐색을 통해 나올수 있는 경우의수들을 모두 탐색하여 가장 큰 이득을 출력한다
• 풀이 실패
  • 처음엔 완전탐색으로 접근을 했지만 탐색을 해나가면서 분기점들이 생기기 때문에 다른방법을 사용해야된다는 것은 알겠는데 적절한 방법을 찾지 못하였다
  • 적당한 시간만 투자하고 빠르게 방법을 익혀야되는데 어떻게하면 풀릴 것 같으니 자꾸 무리해서 풀다가 시간낭비를 하는경우가 많이 생긴다..
    • 그래서 이걸 대비해서라도 시간을 정해놓고 푸는게 좋은 방법인 것 같다
      • 실전에서도 어차피 시간을 넘어가면 못푼다.
  • 문제 난이도가 상승하면서 알고리즘 이론이 부족한게 드러나는 시기인것 같다. 필요하다면 다른 강의들을 보충하고 문제풀이를 하는식으로라도 실력을 향상시켜야 될 것 같다
• 다른사람풀이
  • dp를 이용한 풀이와 dfs를 이용한 풀이로 나뉘었는데 dp를 이용한 풀이를 적용해보기로 하였다
    • dp를 이용해서 풀면좋겠는데 점화식을 만드는게 어려워서 결국 풀이를 하지 못하였는데 점화식을 어덯게 만들어나가는지 보고 연습할 필요를 느꼈기 때문이다
    • 점화식을 보는 것 만으로는 부족하고 어떻게 이런 점화식을 만들어내게 됬는지 논리를 더익혀서 체화시키는게 중요할 것 같다
  • 점화식은 dp[i] = max(dp(i+1), dp[i+t[i]] + p[i]) 이다
    • t[i]는 걸리는 시간 p[i]는 pay이다
    • dp[i+t[i]]]는 dp배열에 범위 안에 있어야 되기 대문에 dp[i+t[i]]가 n+1보다 작아야 된다는 조건이 붙는다
    • 이걸 n~ 1까지 반복한 후 dp[1]을 출력하면 된다
    • 참고 : https://yeoeun-ji.tistory.com/50
  • 가장 끝에서 부터 선택 했을때 최대값을 구하다보면 결국 dp[1]에서 선택했을때 가장 큰 값을 도출할 수 있게 되는 것 이다
    • 점화식은 항상 끝에서부터 가장 앞으로 온다는 것을 기억하면서 차곡차곡 쌓아가는 과정을 생각하면 좋을 것 같다

보물

• 문제 해석
  • 배열 A와 배열 B가 주어진다. S는 배열 A의 0~n과 B의 0~n을 곱해서 합한 값이다
  • 배열 A만 재배치한다고 해서 나올 수 있는 S의 최소값을 구하라
• 풀이 계획
  • B의 최대값과 A의 최소값이 곱해지도록 A를 배치하면 좋을 것 같다
  • 어떻게 B의 최대값과 A의 최소값의 배치를 같도록 할까?
    • 방법1
      • A를 오름차순으로 B를 내림차순으로 정렬한다
      • B를 순차적으로 뽑아서 원래 B의 값중에 검색해서 해당 index에 A의 오름차순의 값을 새로운 원래의 A배열로 옮긴다
        • B에 해당 index의 값을 0으로 만든다.
        • B의 마지막 index까지 반복한다
      • S의 값을 구해서 출력한다
    • 방법2
      • 문제를 다시읽어보니 실제로 변화된 배열을 출력하는 것이아닌 가장 작은 값만 출력하면 되니 그냥 배열을 둘다 정렬하여 A의 최소값과 B의 최대값을 곱해주기로 하였다
• 문제풀이 - 풀이링크
  • 방법1을 사용해 진행하다보니 배열을 여러번 생성해야하고 찾는 과정에서 여러번 배열을 탐색해야되서 비효율적이라 방법2를 다시 계획하였다
  • 방법2를 사용하며 카운터 정렬을 사용해볼까 생각했는데 같은 값이 여러개있는 경우 처리가 어려울 것 같아서 그냥 일반 정렬을 사용하기로 하였다
• 다른사람풀이
  • 다른 사람 풀이를 보니 정렬을 구현하여서 풀길래 나도 연습할 겸 퀵정렬을 구현해서 다시 풀어보았다
    • 다신 푼 풀이

보물

• 문제 해석
  • k의 정수가 주어질때 순서대로 합해가다 0이 입력되면 이전에 입력된 값을 합한값에서 빼준다
    • 최종적으로 합한 값을 출력한다
• 풀이 계획
  • 방법1
    • stack을 이용하여 0이 입력됬을때만 pop해준다
    • 마지막에 stack을 순회하여 합을한다
  • 방법2
    • 자료구조를 이용하지 말고 바로 더해주면서 더해준값을 기억하는 변수를 하나두고 0이나왔을 때 변수에 값만 빼준다
• 문제 풀이 - 풀이 링크
  • 방법2가 더 간단한 것 같아서 방법2로 풀려고 했는데 0이 연속으로 나오는 경우 이전값의 이전값을 기억해야 되는 경우가 생기기 때문에 자료구조를 활용할 수 밖에 없어서 방법1로 선회하였다
  • 자료에 넣는것과 더하는 작업을 분리 하지 않고 둘다 동시에 하면서 0인 경우에만 pop해서 sum에서 빼주면서 풀어 나갔다
• 다른 사람 풀이
  • 스택을 직접 구현해서 푸는 방법이 있어서 스택을 구현해서 다시 풀어보았다
    • 풀이 링크
  • 알고리즘 연습이기 때문에 라이브러리 보다는 직접구현을 우선해서 한다는 것을 꾸준히 지켜나가면 좋을 것 같다

덱

• 문제해석

  • 앞에서 구현했던 큐, 스택 문제와 같이 Deque 자료구조를 직접구현해보는 문제이다
    • Deque는 앞뒤로 값을 넣어주거나 뺄 수 있는 자료구조인 것 같다

• 풀이 계획

  • 명령을 입력받아 switch ~case문을 통해 각 명령을 수행하고 그결과들을 출력한다
  • 배열에 맨앞에 값을 넣거나 빼는 것을 어떻게 해야할까?
    • 앞에 값이 들어갈때마다 배열을 복사하여 뒤로 한칸씩 밀어주는 방식으로 풀어나가야 될 것 같다
  • size는 배열의 크기가 고정이기 때문에 따로 관리하면 좋을 것 같다
  • top을 활용하여 뒤로 값이 입력되거나 빠질때 활용하면 좋을 것 같다

• 문제풀이 - 풀이링크

  • 풀이 계획대로 앞의 값이 넣을때나 밸때는 새로운 배열을 만들어 값을 모두 옮긴뒤에 새로운 배열을 기존 변수로 대입하였다
  • top과 size는 같은 역할을 해서 top만 남겨두고 풀었다

내일 할일

• 스프링 개발 실습
• 알고리즘 문제풀이
• 프로젝트 준비