9월 6일 알고리즘 대회 풀이
$$100 + 90 + 65 + 0 = 255$$점, 학내 $$rk7$$. 링크
T1
분류: 가볍게 풀 수 있는 문제 (노란색 난이도)
문제의 핵심은 반전 연산의 특성이다. 두 위치가 서로 다르다면, 그 중 하나만 바꾸는 것이 아니라, 인접한 두 위치가 서로 순서가 잘못되어 있을 때에만 동시에 교환하는 것이 최적임을 알 수 있다. 따라서 단순한 그리디 시뮬레이션으로 해결 가능하며, 시간 복잡도 ...
5월 29일 13:16에 게시됨
동적 계획법 연습: 공통 부분 수열 및 하위 수열 문제 분석
최장 공통 부분 수열 (Longest Common Subsequence)
이전 문제와의 주요 차이점은 부분 수열 내 원소가 연속적이지 않아도 된다는 점입니다. 이로 인해 dp[i][j] 값은 왼쪽과 위쪽에서 올라오는 두 가지 경로를 고려해야 합니다.
class Solution {
public:
int longestCommonSubsequence(string& first, string& second) {
vector<vector<int>> ...
5월 22일 21:40에 게시됨