[항해99]99클럽 코테 스터디 10일차 TIL + 동적계획법

 

 

벌써 TIL을 올린지 10일차네요 시간 진짜 빠릅니다... 10일이나 됐는데 실력이 좀 오른 것 같은지요? 눈에 보이진 않지만 10일 동안 매일 코테를 풀었다는 사실이 가장 뿌듯하네요ㅎㅎ 알고리즘에 대한 공부도 하고 있어 원하는 결과를 얻을 수 있길...

 

1.  오늘의 학습 키워드 : 동적 계획법(Dynamic Programming)

DP라고 줄여말하는 다이나믹 프로그래밍은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다.

알고리즘 설계 / 알고리즘 설계 기법이 있는데요

알고리즘 기법은 문제를 해결하기 위해 사용되는 절차적인 방법 또는 계획입니다. ex) 정렬 알고리즘, 검색 알고리즘, 그래프 탐색 알고리즘 등

알고리즘 설계 기법은 문제 해결을 위해 알고리즘을 설계하는 방법이나 접근 방식입니다. 설계 기법은 알고리즘을 개발하고 구현하는 데 사용되는 전략, 원칙들을 포함합니다. ex) 분할 정복, 동적 계획법, 탐욕적 알고리즘, 백트래킹 등

 

2.  오늘의 문제 :  Counting Bits

https://leetcode.com/problems/counting-bits/submissions/

DP로 푸는 문제인데.. 비트 계산법을 잘모르겠어서 내장 함수를 사용했습니다. 근데 그러면 안되고 규칙을 찾아보고 푸는 방법이 바로 동적 계획법이라네요~

3.  풀이 

- 처음 코드

import java.util.*;
class Solution {
    public int[] countBits(int n) {
        int[] arr = new int[n+1];
        for(int i=0; i<=n; i++){
            arr[i] = Integer.bitCount(i);
        }
        return arr;
    }
}

 

3.  회고 

DP는 정말 수학적으로 규칙을 찾아내 해결 방법을 찾는 똑똑한 방법인 것 같습니다... 내장함수를 사용해 문제를 푼 것은 그렇게 접근한 것은 아니지만 동적 계획법에 대한 공부를 더 한 후 다시 풀어보려고 합니다. 

 

참고 사이트

https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL

동적계획법(Dynamic Programming)