공부/백준 2020년 1~2월 알고리즘

3번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다. ▲ 다이나믹 프로그래밍 문제풀이 · 가장 긴 증가하는 부분수열 - 영어로 LIS (Longest Increasing Subsequence) - 수열의 길이가 N일때, 부분수열은 2^N개 - D[i] = LIS의 길이, A[i]가 가장 마지막에 있는 수열 - A[i] 바로 앞에 오는 A[j] - 조건1 : A[j]

2번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다. ● 다이나믹 프로그래밍 - 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 두가지 특성을 만족해야 다이나믹 프로그래밍으로 풀 수 있다. 1. Overlapping Subproblem - 문제를 작은 문제로 쪼갤 수 있고, 큰문제와 작은 문제를 같은 방법으로 풀 수 있다. 2. Optimal Substructure - 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다. 각 문제를 한 번만 푼다. 정답을 ..

1번째 수업 복습

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다. ● 알고리즘 - 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태 무엇이 가장 중요할까? 1. 수행시간 - 가장 중요하다 2. 사용한 메모리 - 부족하면 추가하면 된다 3. 코드의 길이 - 중요하지 않다 시간복잡도 - Big O : 최악의 경우에 걸리는 시간 - N이 1억일때 약 1초 정도 걸린다. 메모리 - 보통 가장 많은 공간을 차지하는 것은 배열 - 보통 시간을 지키면 대부분 메모리 ..

1번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다. .....은 오래전부터 잡아놓은 여행이 있는 관계로 못 갈 예정이다.ㅠㅠ 첫시간부터 결석을 한다는 것이 매우 죄송스럽고 비싼 수강료도 아깝지만.. 오래전부터 계획한 여행이어서.. 안 갈수가 없다. 첫시간에는 [알고리즘 및 시간 복잡도] 그리고 [자료구조1]에 대해서 강의할 계획이라고 한다. [알고리즘 및 시간 복잡도]에서는 알고리즘이 무엇인지, 알고리즘 공부는 왜 하는지, 알고리즘 문제를 푸는 목적이 무엇인지에..