[백준] 18870 - 좌표 압축
문제 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. www.acmicpc.net 해결 과정 처음에는 원래의 배열과 솔트한 배열을 작은 숫자부터 비교해 가며 정답 배열에 순서값을 넣은 후 정답 배열을 출력하는 방법을 이용했다. #include #include int main() { int n; scanf("%d", &n); int num[n], sorted[n], ans[n], cur = 0; for (int i = 0;..
[백준] 9251 - LCS
문제 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 해결 과정 따로 네이밍이 있는 만큼 유명한 알고리즘 문제인 듯 하다. 결론적으로 혼자 힘으로 풀 수 없었다. 알파벳 별로 배열을 만들어서 푸려고도 해보고 한 글자씩 대조해 보며 일치하면 두 인덱스 모두 1씩 증가시킨 후 탐색하려고도 해봤지만 이는 이미 탐색한 부분을 중복 탐색해 결과를 바꾸는 등 다른 오류를 야기해냈다. [ LCS 알고리즘 ] 간만에 백준 싸이트에서 dp 문제 푸는 중에 알게되었다. LCS 알고리..
[백준] 1463 - 1로 만들기
문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 해결 과정 단계별로 풀어보기 중 동적 계획법(Dynamic Programming)에 나온 문제라서 우선 동적 계획법을 시도했다. 당시에는 구하고자 하는 수에서 부터 1로 계산해가는 방식을 사용하려고 했는데 구현 과정에서 막혔다. BFS를 이용해서 처음 n에 도달하면 탐색을 종료하는 방법을 떠올리고 시도해 보았지만 BFS를 구현한 적이 없어서 실력 부족으로 역시 실패했다. 결국 생각을 바꿔 동적 계획법으로 1부터 n까지 계산해가며 쌓아올리는 방식으로 구현해냈다. 아래는 성공한 결과물이다. #include inline int min(int a, int b) {return a..