heaven X world

문제 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 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 해결 과정 따로 네이밍이 있는 만큼 유명한 알고리즘 문제인 듯 하다. 결론적으로 혼자 힘으로 풀 수 없었다. 알파벳 별로 배열을 만들어서 푸려고도 해보고 한 글자씩 대조해 보며 일치하면 두 인덱스 모두 1씩 증가시킨 후 탐색하려고도 해봤지만 이는 이미 탐색한 부분을 중복 탐색해 결과를 바꾸는 등 다른 오류를 야기해냈다. [ LCS 알고리즘 ] 간만에 백준 싸이트에서 dp 문제 푸는 중에 알게되었다. LCS 알고리..

문제 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..

트리(tree)는 자료 간의 부모-자식 관계(상하 관계)를 표현하는 자료 구조이다. 모든 원소의 자식 원소가 2개 이하로 이루어진 트리를 이진 트리(binary tree)라 하고, 또 이 중 부모보다 큰 원소를 왼쪽 자식 원소로, 부모보다 작은 원소를 오른쪽 자식원소로 배열하는 트리를 이진 탐색 트리(binary search tree)라 한다. 이진 탐색 트리는 일반적인 이진 트리보다 검색이 더 용이하다. 트리의 층(level)은 맨 위의 부모 노드와 맨 아래의 자식 노드 사이의 최대의 거리를 의미하는데, 자료를 탐색하는 데에는 트리의 층 개수의 원소를 탐색하는 시간 만큼 걸린다. 이 때문에 최대한 층이 적은 트리인 균형 이진 탐색 트리(balanced binary search)로 만들어야 탐색 시간이 ..

자료 구조의 가장 기초적인 형태는 배열(array)이다. 배열의 각 원소의 크기는 일정하다. 이러한 성질 덕분에 원소의 주소를 (원소 번호) * (원소 크기)로 쉽게 구할 수 있다. 다만, 이러한 성질은 데이터의 추가/삭제가 용이하지 않다는 점과 함께 배열의 단점이 되기도 한다. 연결 리스트(linked list)는 배열의 이러한 단점을 보완하는 자료 구조로, 각 원소에 다른 원소를 가리키는 부분이 추가된 형태이다. 이 중 단일 연결 리스트(singly linked list)는 다음 원소의 주소를 붙여놓은 형태이고, 이중 연결 리스트(doubly linked list)는 다음 자료와 이전 자료의 주소를 붙여 놓은 형태이다. 환형 연결 리스트(circularly linked list)는 연결 리스트의 마지..