33일차 TIL 210419

1. 1:1 이슈쉐어링을 올렸다

  • 주말내내 자료구조-알고리즘 문제를 붙잡고 있었음에도 불구하고 결국 문제를 해결하지 못했다.
  • 프리과정에서 풀었던 알고리즘( 지금 생각해보니 그것은 알고리즘 문제가 아니었다 ) 이 재밌어서 그럼 나는 백엔드가 맞는걸까..? 라고 큰 착각을 했더랬다.
  • 이슈쉐어링 답변은 아래와 같았다.
    • 자료구조/ 알고리즘 스프린트는 정말 어려운 과정이다.
    • 레퍼런스를 보는건 괜찮다. 알고리즘 로직이 의마하는 바를 레퍼런스에 주석을 나만의 언어로 달아보자.
    • 내가 이해하고있는 정도를 잘 파악하고 이해한 것에 대한 기록을 꼭 해두기
    • 자료구조 알고리즘은 과정 수료 후에도 계속 가지고가야할 숙제이다. 이해가 안된다면 우선 웹개발 코스일정을 따라가라
    • 추후 제공되는 토이 문제에 집중하라

2. 알고리즘 (알아두면 쓸데있을지도 모르는 신비한 개념)

  • 효율적인 알고리즘이란 ? 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화 한 알고리즘 구성하기
  • BIG-O : 최악의 경우 입력값의 증가에 따라 시간 복잡도가 얼마나 증가하는지 표기하는 방법
  • 실제 알고리즘의 러닝타임이 아니라 데이터가 늘어남에 따라 처리시간 증가율을 예측하기 위해 만들어진 표기법이다.

3. Greedy Algorithm

  • 문제 푸는 방법론, 현재 상황에서 가장 좋아보이는 답을 선택하는 방법
  • 문제를 해결하는 과정에서 그 순간순간마다 최적이라 생각되는 해답을 찾으며 이를 토대로 최종 문제의 해답에 도달하는 문제해결방식
  • 하지만 항상 최적의 결과를 보장하지 못한다.
  • 아래 두가지 조건이 성립해야 최적의 해를 구할 수 있다.
    1. 탐욕적 선택 속성(greedy choice property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
    2. 최적 부분 구조(optimal substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

4. Dynamic Programming ( 동적계획법 )

  • 모든 경우의 수를 따져본 후 이를 조합해 최적의 해법을 찾는 방식
  • 아래 조건에 해당하는 경우 가능하다.
    1. 큰 문제를 작은 문제로 나눌 수 있고, 이 문제들은 중복된다. 큰문제로부터 나누어진 작은 문제를 해결할 때 여러번 반복해서 사용될 수 있어야 한다.
    2. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 같다.

5. 다른 사람의 코드로 도움을 받아 해결한 코플릿 문제 해석

Q: 훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 target 을 훔칠 수 있는 방법의 수를 리턴하세요.

function ocean(target, type) {
//만들어야 할 target +1 크기만큼의 배열을 만들어 0으로 채운다. +1을 하는 이유는 0번째 인덱스가 필요하기 때문
  let arrSum = new Array(target + 1).fill(0) 
  //초기값은 1로 설정하는데, 이유는 arrSum[j-el] 에서 j-el 이 0이 되는 경우가 있기 때문이다. 
  arrSum[0] = 1;
  //각 요소만큼 바깥 반복문, 만들고싶은 금액만큼 안쪽 반복문 돌리기
  type.forEach(el =>{
   for(let j=el; j<target+1; j++){
   //아래 코드는 이번 문제의 핵심이라고 할 수 있는데, 이는 arrSum의 경우의 수에서 el 만큼 더한것이 수가 같기 때문이다.
      arrSum[j] += arrSum[j-el]
    } 
  })
  return arrSum[target]
}

Updated: