오늘 할일

• 채용공고 읽기

• 알고리즘 문제 풀기

• 기술면접 준비

오늘 한 것 & 배운 내용

알고리즘 문제 풀이

• 이항 계수 간단정리
  • 이항 계수는 (a+b)n 의 꼴의 다항식을 전개했을 때, akbn-k(0<= k <=n인 정수)의 계수를 의미하며 n! / k!(n-k)! 와 같다
    • 즉 조합의 정의와 같아 서로 다른 n개에서 k개를 뽑는 경우의 수를 구하는 것 과 같은 원리로 답을 찾으면 된다
      • 순열은 뽑은 것을 나열하는 경우의수까지 생각한 것이고 조합은 나열하는 경우의 수는 생각하지 않고 뽑은 것만 보는 경우이다
        • 뽑은 것을 모두나열한것 까지 생각하면 단순히 n!이겠지만 뽑는것만 생각하면 중복된 것들을 제거해줘야 되기 때문에 n! / k!(n-k)! 가 된다
  • 완전히 이해 하진 못했지만 어느정도 공식을 이해한 것 같아서 다음을 기약하고 문제풀이에 들어갔다
  • 참고자료
    • 순열과 조합
      • https://widekey6.tistory.com/105
      • https://suhak.tistory.com/2

이항 계수1

• 내풀이
  • 위에서 이항계수의 공식을 배웠기 때문에 그대로 공식을 적용에서 풀고자 하였다
  • 먼저 팩토리를 구해야 하는데 for문을 돌리려다가 뭔가 다른 방법이 있어서 검색해 보았다
    • 검색 결과 재귀함수를 통해 팩토리얼을 구하는것을 배워서 static메소드로 만들어주었다
      • 팩토리얼 : https://suhak.tistory.com/2
    • 재귀함수로 푸는경우는 n이 10보다 작거나 같기 때문에 가능하지만 너무커지면 속도면에서 문제가 생길것 같다
  • 만든 fact메소드를 활용해서 n! / k!(n!-k!)의 결과를 출력하도록 하였다
    • n=k인 경우 0으로 나누는 에러가 발생해서 fact메소드의 0이 입력되면 1이 return되도록 수정하였다
      • 문제를 풀기위해서 이렇게 임의로 해둔건데 실제로 조합의 성질중 k가 0이거나 n=k 인경우 1이라는 성질이있어서 이렇게 풀수 있엇던것 같다..
  • 간단하게 풀어보았지만 문제는 공식과 팩토리얼 방식 모두 검색을 통해서 알고 푼거기 때문에 만약 실제 코딩테스트에서 기억이 안나면 문제를 못풀거같다..
    • 쉽게 배운것들은 쉽게 잊혀진다.. 이제 이것들을 어떻게 안잊으면서 내걸로 만드는지가 관건이 될것 같다
• 다른사람풀이- https://st-lab.tistory.com/159
  • 수학적으로 이항계수를 이해하고 팩토리얼을 이용해푸는 방법, 조합의 성질을 이용해 재귀를 이용해 푸는방법, 마지막으로 2번에 동적계획법을 이용해 푸는 방법을 소개해주셨다..
    • 이렇게 수학적으로 이해하면서 풀어가면 나중에 공식이 기억이 안나서 헤매는 일은 절대 없을 것 같다
    • 동적계획법은 아직 익숙하진 않지만 그래도 계속 익숙해져야 되는 개념이기 때문에 소개해주신방법이 도움이 되었다
      • 위에서는 재귀함수를 통해 반복되는 연산을 줄이기 위해 이미 한번 연산한 값은 배열에 저장하여 해당 값을 활용하여 연산횟수를 줄인 것을 동적계획법을 적용했다고 이야기하고 있다
• 다시 정리해보면 이항계수 문제를 통해 굉장히 배운게 많은 문제였다..
  • 문제 하나를 풀더라도 이렇게 제대로 알고 풀려고 노력하면 훨씬 얻는게 많을 수 있다는 것을 배운 기회였다

2차원 배열의 합

• 내풀이

  • 정직하게 입력값을 받아서 다차원 배열을 만들고 지정해진 범위만큼 2중배열을 돌려서 누적합을 구했다
    • 이렇게 구하니 성능이 많이 떨어졌는데 성능을 높여보려고 고민했으나 뚜렷한 해결방법을 찾지는 못했다

• 다른사람 풀이

  • 동적계획법을 이용해 계산식을 줄여주는 방식으로 풀어야 연산속도를 증가시킬 수 있었다

    • 동적계획법은 하나의 문제를 여러개의 하위문제로 나누어 푼다음 그것 그해결책을 기록하여 해당 해결책들을 결합하여 문제를 푸는 방식이다
      • 이렇게 하면 기하급수적으로 늘어나는 하위문제들의 계산 횟수를 줄일수 있다는 장점이 있다
      • 동적계획법 : https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

  • 해당 문제에서 dp[i][j]를 0,0.에서 i,j까지의 합을 저장해 놓은 것이라고 가정한다

    • 입력값을 위에 정의에 맞게 dp[][]에 넣는다

      for (int i = 1; i <= N; i++) { st = new StringTokenizer(br.readLine());for (int j = 1; j <= M; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + Integer.parseInt(st.nextToken()); } }

    • 그럼 i,j ~ x, y의 범위를 구하기 위해서는 dp[x][y]에서 dp[i-1][j]과 dp[i][j-1]을 빼준뒤에 dp[i-1][j-1]이 중복해서 빠졌으니 더해주면 해당 범위에 덧셈을 구할 수 있다

  • 동적 계획법을 이용한 풀이

    • https://ksh-code.tistory.com/304
    • https://something-handal.tistory.com/2

• 동적 계획법이 아직 익숙하진 않지만 하나의 값을 구하기 위해 계산과정을 기록하고(그 기록과정 자체도 하위수식들을 활용하여 계산식을 줄인다) 마지막 답은 해당 결과를 수식으로 활용하여 계산식을 확실히 줄여주는게 목표라는 것을 이해한 것 같다

  • 일단 문제를 어떻게 하위문제로 나누어 기록해야 되는지 정리해나가는 과정들을 집중해서 연습해봐야 될 것 같다

내일 할일

• 채용공고 읽기 & 지원하기

• 알고리즘 문제 풀기

• 기술면접 준비