전체 글

[딥러닝] Gradient Descent (경사 하강법)

직관적 의미 비용 함수(cost function) 값을 최소화하는 파라미터를 찾기 위해 cost function의 미분값이 작아지는 방향으로 파라미터를 변경하는 iterative한 방법 gradient descent를 사용하는 이유 함수의 최소, 최댓값을 찾기 위해 미분계수가 0인 지점을 찾을 수 있다. 하지만, 현실에서 마주하는 문제는 비선형 함수처럼 함수 형태가 복잡해 미분계수와 근을 계산하기 어려운 경우가 많고, 컴퓨터 기준으로는 미분계수보다 gradient descent 연산이 더 쉽기 때문이다. gradient descent 의미 기울기 > 0: x값이 커질수록 함수값이 커진다는 의미 기울기 < 0: x값이 커질수록 함수값이 작아진다는 의미 |기울기| 값이 큰 경우: 그래프가 가파르다는 것을 의..

[백준] 18353번 - 병사 배치하기 (python)

문제 병사의 전투력이 내림차순이 되도록 하는 가장 긴 수열을 구한다. 문제 바로가기 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 LIS 알고리즘을 활용하면 쉽게 풀 수 있다. "증가하는" 부분 수열이 아닌, "감소하는" 부분 수열을 만들어야 하기 때문에 reverse()를 사용해 초기 전투력을 뒤집은 후에 계산했다. 이전 LIS 포스팅 [백준] 가장 긴 증가하는 부분 수열 (LIS) 가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subse..

[DP] 가장 긴 증가하는 부분 수열 (LIS)

가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)은 대표적인 다이나믹 프로그래밍 문제이다. {10, 20, 10, 30, 20, 50} 과 같은 수열이 주어졌을 때, 수가 점점 증가하는 수열의 가장 긴 길이를 구한다. 1) Dynamic Programming 풀이법 - O(N^2) 파라미터 설명: n = 수열의 길이 arr = 수열을 이루는 숫자가 담긴 배열 d = arr[i]를 마지막 원소로 가질 때 LIS의 길이 d[i] 값을 1로 초기화한다. 현재 위치(i)보다 이전에 위치한 원소(j)가 작은지 확인한다. (i는 기준이 되는 인덱스, j는 i보다 작은 인덱스) arr[i] > arr[j] 이면, 현재 위치 숫자 중 d의 최댓값..

[백준] 1932번 - 정수 삼각형 (python)

문제 위에서부터 시작해 아래로 내려오며 각 층의 수를 하나씩 선택해 더할 때, 총합이 최대가 되는 경로를 구하여라 문제 바로가기 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 파란색 글씨가 입력으로 들어온 삼각형 모양의 숫자이고, 빨간색 글씨가 각 경우에서 누적합이 최댓값이 되는 경우이다. 코드에서 파란색이 num, 빨간색이 d에 해당한다. 맨 위 꼭짓점은 더할 수 있는 값이 없으므로 자기 자신이다. 왼쪽 변과 오른쪽에 있는 숫자의 경우, 자기 자신에 바로 위에 있는 숫자만 더할 수 있다. 중앙에 있는 숫자의 경우, 자기 자신에 윗줄의 양옆 숫자 중 최댓값을 더한다. → 그..

[백준] 11403번 - 경로 찾기 (python)

문제 가중치 없는 방향 그래프 G가 주어진다. 모든 정점에 대해 i → j로 가는 경로가 있는지 확인해, 모든 노드에서 모든 노드로의 경로 존재 여부를 출력하라. 문제 바로가기 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 모든 노드 → 모든 노드로의 최단 경로를 찾는데 사용되는 알고리즘인 플로이드-와샬 알고리즘을 사용했다. (DFS, BFS를 사용해서도 풀 수 있을 것 같다.) 이 문제에서는 자기 자신으로 가는 경로도 존재하는지 확인하는 점이 기존 플로이드-와샬 알고리즘과 다르다. a → k → b 노드 순서로 노드 k를 경유한다고 볼 때, a..