본문 바로가기
728x90

코딩테스트/알고리즘 기초 강의20

1강 브루트 포스 - 브루트 포스 알고리즘 강의 1의 마지막 도전문제는 강의 2 다 듣고 찬찬히 생각하며 풀어보려 한다. ----------------------------------------------------------------------------------------------------------------------------- -브루트 포스 브루트 포스란 모든 경우의 수를 다 해보는 알고리즘이다. 이 알고리즘은 모든 문제를 풀 수 있는 방법은 아니고 방법의 개수가 많지 않은 경우에만 사용하는 방법이다. 가능한 방법의 수를 모두 구한 후 방법의 수를 모두 했을 때 시간복잡도를 구해서 너무 오래걸리지 않으면 이 방법으로 해결할 수 있다. 여기서 시간복잡도를 구했을 때 1억보다 작으면 작다고 생각하면 된다. 브루트 포스로 문.. 2020. 8. 27.
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.
728x90

티스토리툴바