본문 바로가기
728x90

코딩테스트205

4강 다이나믹 프로그래밍 1 - 연습 와 나 이거만 하고 자려고 했는데 이거 63쪽짜리야 pdf 와와 미쳤나봐 와와 나 자고싶은데 와와 그래도 내가 강의를 듣고 와볼게 하나 둘 셋 얍 듣고 온 후기 : DP는 점화식 싸움이고 이번강의 문제 짱많고 하기싫고 지금 새벽 4시인거 너무 서럽고 나 내일 9시에 일어날거고... 일단 들었으니까 자고 내일 9시에 일어나서 마저하고 수강신청할거야 뿌에엥 ㅠㅠ ---------------------------------------------------------------------------------------------------------------------------------- 기존 1, 2, 3 더하기 문제에서 n의 범위만 커짐 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.. 2020. 8. 25.
4강 다이나믹 프로그래밍 1 - 합분해까지 좀 더 어려운 DP 문제랄까...☆ 집에서 맨날 코딩만 하니까 뭔가 좋고 싫어..ㅋㅋㅋㅋㅋ 양갱이랑 또 맥주마시러 가고싶당 우리 집앞에 맥주집 짱마싯는데 코로나 확진자 동선이 약간 가까워서 사리는중 ㅜㅅㅜ +) ㅋㅋㅋㅋㅋㅋㅋ에어팟 2세대 사버렸닼ㅋㅋㅋ 쿠팡으로 결제하면 결제화면 안나오고 바로 결제되서 항상 기분이 엥..?함 알바와 공부 둘 다 열심히 해야겠다 이제... 이번달 돈 진짜 짱마니썼어.. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 이는 영어로 LIS(Longest Increasing Subsequence)라고 한다. 이 문제는 이전 문제와 달리 점화식을 먼저 구하지 않고 표로 먼저 구한 뒤 문제를 풀어보자. A[i]는 실제 수열의 숫자고, D[i]는 A[i]를 마.. 2020. 8. 24.
4강 다이나믹 프로그래밍 1 - 이친수까지 이전 강의에선 쉽게 해결이 가능한 1차원 다이나믹 문제들이었다면 이번엔 약간 생각이 필요한 문제들이다. 이번엔 문제의 변수가 추가된 2차원 다이나믹 문제들을 풀어보자 카드 N개를 구매해야 한다. 이 때 카드팩은 총 N가지 종류가 존재한다. i번째 카드팩에는 i개의 카드가 들어있고, 가격은 P[i]원이다. 이 때 카드 N개를 구매하는 비용의 최댓값을 구하는 문제이다. 그러면 점화식 D[N]을 우선 카드 N개를 구매하는 비용의 최댓값으로 두자. 이도 전에 푼 문제처럼 마지막 카드팩에 집중하여 작은 문제로 쪼갠다. 근데 마지막 카드팩에 카드가 몇 개있는지 알 수 없다. 그래서 마지막 카드팩에 카드가 i개 있다고 가정한다. 그러면 그 전에 N-i개의 카드를 구해야 한다. 그래서 점화식 D[N] = max(D[N.. 2020. 8. 22.
4강 다이나믹 프로그래밍 1 - 1, 2, 3 더하기까지 DP는 문제를 풀면서 이해하는게 좋다고 한다. 이번 강의에서는 비교적 쉽게 할 수 있는 다이나믹 프로그래밍 문제들이다. 다이나믹 프로그래밍 문제를 풀 때 기본은 점화식을 세우는 것인데, 이 문제들은 문제에서 나온 내용 그대로를 점화식으로 옮기면 되거나, 작은 문제를 만드는 방법이 문제에 나와있어 쉽게 풀 수 있다! 정수 X를 1로 만들어 주는 연산을 하는 문제다. 대애박 하기싫어,,,,ㅎ_ㅎ 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 이 문제를 해결하려면 우선 큰 문제인 X를 1로 만드는 것을 작은 문제로 쪼개서 생각해줘야 한다. 저 3가지 방법에서 3으로 나누는게 가장 빨리 1이 되.. 2020. 8. 22.
4강 다이나믹 프로그래밍 1 - 다이나믹 프로그래밍 소개 이번 강의에선 다이나믹 프로그래밍을 소개하고 어떤 방식이 있는지를 배웠다. 다음시간부터 문제를 풀어보기로 하고 우선 오늘 배운것을 정리해보도록 하겠다. ------------------------------------------------------------------------------------------------------------------------------- -다이나믹 프로그래밍 다이나믹 프로그래밍은 동적 계획법이라고도 부른다. 큰 문제를 작은 문제로 나눠서 푸는 알고리즘으로 여기서 크기는 문제의 크기를 말한다. 다이나믹 프로그래밍은 2가지로 나눌 수 있다. 첫번째는 DP, 두번째는 분할정복이다. 이 두 개의 공통점은 큰 문제를 작은 문제로 나누어서 푼다는 것이다. 차이점은 DP는 작.. 2020. 8. 21.
3강 수학 1 - 참고 -진법 변환 10진수 N을 B진법으로 바꾸려면 N이 0이 될때까지 나머지를 계속해서 구하면 된다. 난 나머지를 모두 string배열로 변환해서 저장하고 숫자 나머지들은 스택에 넣은 후, 나머지 연산 끝나면 스택에서 차례대로 pop하면서 string배열 인덱스로 나머지를 문자열로 만들어서 출력하려고 했다. 여기서 0을 생각 못해서 한번 틀리고, 인덱스가 헷갈려서 두번 틀렸다....에고 창피해/// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include #include using namespace std; string arr[36]; int main() {.. 2020. 8. 20.
728x90

티스토리툴바