MingyuPark

이번에는 강의 내용 정리보다는 Chapter 4. 딥러닝, 그것이 알고 싶다. 파트를 읽고 느낀 점에 대한 설명을 해보려고 한다. (강의 내용 정리도 좋지만, AI DEEP DIVE 강의 구매를 고민하고 있는 사람이 있다면 이런 글도 도움이 될 것 같다.) MLP를 구성할 때 linear activation만 이용하면 안 되는 이유를 설명해주는 장면이다. 가장 큰 장점은 행렬, 벡터에 대한 기초가 없는 사람이라면 이 과정을 행렬, 백터로 표현하는 과정에서부터 좌절을 할 수도 있을 것 같다. (물론 나는 선형대수학에 대한 기초가 있었기 때문에 크게 어려움이 있지는 않았지만) 아무튼, 이런 과정을 직관적으로 설명해준다. W 행렬이 왜 이렇게 구성되는지, bias 벡터는 어떻게 표현되는지 등등. (입문자들에게..

문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 아이디어 가장 위층부터 아래층에 있는 두 수 중 하나를 선택해서 가장 아래층으로 가는 경로 중에서 합이 가장 큰 경우를 구하는 문제다. 문제 예제에서 최적의 경로부터 보면 다음과 같다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 쉽게 생각하면, 가장 위층부터 시작해서 아래층으로 내려가면서 합을 구해보면 된다. 5층의 경우 양쪽으로 갈 수 있기 때문에 4층에 더해주면 다음과 같이 10, 15가 된다. 또한 각 층의 가장 왼쪽은 그 윗층의 가장 왼쪽값만 더..

문제 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 아이디어 A에서 B로 가는 Bottom-up 방식보다는 B에서 A로 가는 Top-down 방식이 더 편하다. 왜냐하면, A에서 B로 갈 때는 2를 곱하는 연산, 1을 수의 가장 오른쪽에 추가하는 연산이 모두 가능하기 때문에 모든 조합을 고려하면서 가야한다. (적고 보니 bfs로 가능하려나,, 고민해봐야겠다.) 반대로 B에서 A로 갈 때는 매 step마다 한 가지의 경우밖에 없다. 예제 입력 1을 예로 들어보자. A = 2, B = 162이다. → 1. Bottom up 2 → 4도 가능하고, 2→21도 가능하다. 2..

문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 아이디어 투 포인터 기법을 이용하면 된다. 수열의 길이가 최대 10만 개이기 때문에, for loop를 이용해서 하나하나 계산할 경우 최대 10^10번의 계산을 해야 한다. 이 경우 투 포인터 알고리즘을 이용할 수 있다. 문제에 주어진 설명을 빌려서 말하자면 양 끝에서 포인터를 좁혀가면서 조건에 맞는 모든 경우를 찾는 문제이다. 하지만 ..

문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 아이디어 진실을 아는 사람들의 번호를 n_know_lst 라는 리스트에 저장한다. 이 때, 처음에는 진실을 아는 사람이라고 했지만, 다른 말로 하면 거짓말을 칠 수 없는 사람들이기도 하다. 왜 이렇게 표현했냐면, n_know_lst에 속하는 사람과 같은 파티에 있었던 사람에게는 거짓말을 칠 수 없게 되는 것이다. 즉, 모든 파티를 순회하면서 n_know_lst 의 정보를 이용해서, n_know_lst에..

문제 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 아이디어1 - DP Pypy3에서는 성공했고, Python에서는 시간 초과가 발생한 방법이다. 아이디어는 다음과 같다. 자연수 n에 대하여, n을 최소 개수의 제곱수 합으로 표현했을 때 그 개수를 f(n)이라고 하자. 이 때, n보다 작은 모든 제곱수 k에 대해 m = n - k 라고 하면, f(n)은 f(m)의 최솟값 + 1이 된다. (제곱수를 더한다는 ..