프로그래밍 썸네일형 리스트형 [BOJ] 1406. 에디터 (python) https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어.. 더보기 [BOJ] 11653. 소인수분해 (python) https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 풀이 없겠지만 혹시 블로그 애독자를 위해 꾸준히 알고리즘 풀기..! 1. 소인수분해를 위해 2부터 나눠본다. ( 2 -> 3 -> 4 -> 5 순으로!) 2. 나누어 떨어진다면, 해당 값을 출력하고 현재 값을 나누어준다! 3. 초기 값이 1이 될 떄까지 계쏙해서 나누.. 더보기 [C] 재귀함수를 만드는 Global 변수 vs argument C로 코딩을 하다가, 문득 문제를 만났다!! 짜고자 하는 함수는, tree의 중위순회한 결과 (작은 값부터 오름차순으로)를 arr에 담아주는 함수이다. 함수는 짧으니 아래를 보며 이해하자! int i = 0; int inorder_array(node_t *n, key_t *arr) { if (n) { inorder_array(n -> left, arr); // printf("%d \n %d \n", n -> key, i); arr[i++] = n -> key; inorder_array(n -> right, arr); } return 0; } 이렇게 짤 경우, int i = 0 이라고 i라는 global 변수를 선언했다. 그래서 함수 내부에서 i 값을 증가시키고, arr[i]에 중위순회의 값을 넣어주는 방.. 더보기 RB Tree 삽입 Red-Black Tree의 삽입 RB의 삽입에 대해 알아보자. 색 변환과 rotate를 제외하면 Binary Search Tree의 삽입과 같다. (BST를 이해하고 오자!) 위 그림과 같이 insert 하려는 node를 X, X의 부모를 P, 부모의 부모는 G, 부모의 형제인 삼촌노드는 U로 표현하자. 그리고 BST의 insert 과정이 끝났다고 생각하자. (즉, x가 어디에 위치할지 찾고 삽입한 것이다!) X는 항상 빨간색이다! X가 루트인 경우 X노드가 루트라면, RB의 특성 1을 유지하기 위해 BLACK으로 변경해준다. X가 루트가 아닌 경우 부모가 검은색인 경우 X는 항상 RED이므로 부모가 BLACK이면 삽입해도 RB가 깨지지 않는다!! (5가지 특성이 모두 지켜진다.) 때문에 검은색인 경우.. 더보기 이진 탐색 트리(Binary Search Tree) C로 구현하기 #include #include typedef struct _Node { int value; struct _Node *left_child; struct _Node *right_child; }Node; Node* search(Node *root, int x); Node* insert(Node *root, int x); Node* find_min(Node *root); Node* delete(Node *root, int x); int count = 0; int main() { Node *root; int N; int i, input; root = NULL; scanf("%d", &N); for (i = 0; i < N; i++) { scanf("%d", &input); root = insert(root, i.. 더보기 RB Tree [레드 블랙 트리] https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC 레드-블랙 트리 - 위키백과, 우리 모두의 백과사전 레드-블랙 트리(Red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스(Leo J. Guibas)와 로버트 ko.wikipedia.org Red-Black Tree Red-Black Tree(이하 rb)는 이진 트리의 한 종류이다. 그 중에서도 balanced search tree의 하나이다. rb는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 O.. 더보기 [BOJ]2579. 계단오르기 (python) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있.. 더보기 Rabin-Karp String Matching Algorithm, 라빈-카프 알고리즘 https://www.youtube.com/watch?v=qQ8vS2btsxI 이 영상을 참고했다! 라빈-카프 알고리즘은 String을 비교하여 긴 문자열에 짧은 문자열이 포함되어 있는지 확인하는 알고리즘이다. brute force 방법으로, 문자열을 한칸씩 이동하며 모두 비교하는 방법부터 보이어-무어, KMP등 여러가지 방법을 공부했다. 라빈-카프의 핵심은, Hash function이다. 각 문자열의 값을 이렇게 할당한다고 했을 때, 'AAA' 의 값을 1 + 1 + 1 = 3으로 정의한다. 이렇게 해당 문자열의 값을 return해주는 함수가 hash 함수이다. (예시는 단순한 해시함수이다!) 'AAAAAAB' 안에 'AAB'가 존재하는지 확인하기 위해서, 'AAB'를 hash 함수에 넣고, 4라는 값.. 더보기 이전 1 2 3 4 5 다음
