[Algorithm] 에디터 문제 풀이

문제https://www.acmicpc.net/problem/1406한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.이 편집기가 지원하는 명령어는 다음과 같다.L커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)D커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)B커서 왼쪽에 ..

• format_list_bulleted Algorithm
• · 2024. 12. 22.
• textsms

[Algorithm] 배열 활용하기

개요보통 배열은 데이터를 쌓아두는 용도로 사용한다.배열을 다음과 같은 접근으로 생각하면 문제를 효율적으로 풀 수 있는 경우가 많다!배열을 인덱스에 해당하는 원소를 빠르게 접근하는 목적으로 사용한다.문장만 봐서는 뜻이 아리까리 하다.예시 문제로 이해해보자.두 원소의 합이 100주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라. arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다. 예시func2({1, 52, 48}, 3) = 1,func2({50, 42}, 2) = 0 문제를 봤을 때 O(N^2)의 시간복잡도를 가지는 풀이가 생각날 것이다.배열을 순차적으..

• format_list_bulleted Algorithm
• · 2024. 12. 19.
• textsms

[Algorithm]C++ 배열

개요알고리즘 문제를 풀 때 배열에서의 주의사항, 팁들을 알아보자. 기본 배열주의사항배열은 순차적으로 메모리가 할당되므로 원소를 찾는데 O(1)의 시간이 걸린다.배열 끝에 할당을 하거나 삭제하는 건 O(1)의 시간이 걸린다.배열 중간에 할당을 하거나 삭제하는 건 O(1)의 시간이 걸린다.초기화 방법memset: 0, -1이 아니면 오류가 나고 2차원 배열에서도 사용 불가능 비추!!fill: 실수할 여지도 없고 사용도 간편int arr1[10] = {}; //{0, 0 ...}int arr2[10][10];//1. memsetmemset(arr1, 0, sizeof arr1);//2. fillfill(arr1, arr1+10, 0);for(int i=0; i  VectorC++의 STL중 하나로 배열과 같은..

• format_list_bulleted Algorithm
• · 2024. 12. 19.
• textsms