알고리즘

[BOJ/C++] 5397번 키로거

문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 강산이는 키보드로 입력한 키는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표이다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000)..

[바킹독 알고리즘] 0x04강:Linked List

연결리스트 성질 k 번째 원소 확인/변경 위해 O(k) 필요 임의의 위치에 원소 추가, 제거가 O(1) (추가/제거하는 위치를 알고있는 경우) Cache rate hit은 낮지만 할당이 좋다. → 임의의 위치에 원소 추가하거나 제거하는 연산이 많을경우 연결리스트 사용 좋다. 연결리스트 종류: 단일 연결리스트/이중연결 리스트/환형 연결리스트 배열 vs 연결리스트 연결리스트 구현 #include using namespace std; const int MX = 1000005; int dat[MX], pre[MX], nxt[MX]; int unused = 1; void insert(int addr, int num){ dat[unused] = num; pre[unused] = addr; nxt[unused] = ..

[BOJ/C++] 3273번 두 수의 합

문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. 풀이 아이디어 - 입력된 숫자들을 배열에 담는다 - 합으로 나올 수 있는 최대 값 크기만큼 bool array를 만든다. - O(N)에 문제를 풀고, ai+aj=x가 있는지..

[BOJ/C++] 1406번 에디터

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

[바킹독 알고리즘] 0x03강:Array

연습문제: O(1)에 배열 안 원소 중 2개의 합이 100인게 존재하는지 확인하기 int func2(int arr[], int len) { int occur[101] = {}; for (int i = 0; i < len; i++) { if (occur[100 - arr[i]] == 1) { return 1; } occur[arr[i]] = 1; } return 0; } 0~100까지 인덱스가 있는 배열을 만듬 내가 입력한 배열을 돌면서 원소에 해당하는 값을 occur 배열 인덱스 값으로 1을 추가함. 만약에 100-해당 원소 가 occur 배열에서 1 값을 가지고 있으면 합 100이 가능한 원소가 존재한다는 뜻 따라서 존재여부로 O(1)에 값을 구할 수 있다. 문제 풀이 현황 연습 문제✔ 10808 알파..

[BOJ/C++] 1475번 방번호

#include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string N; vector vec(10); int max = vec[1]; fill(vec.begin(), vec.end(), 0); cin >> N; for (int i = 0; i vec[9] + 1) { vec[6]--; vec[9]++; } else if (vec[9] > vec[6] + 1) { vec[9]--; vec[6]++; } } for (int i = 0; i < 10; i++) { if (max < vec[i]) {..

[바킹독 알고리즘] 0x02강:STL

STL과 함수 인자 stl 벡터를 함수 인자로 넘길때 이를 복사하는 과정이 필요하기 때문에 O(N) 걸림 하지만 레퍼런스 사용시 그 과정이 생략되어 우리가 생각하는 것처럼 O(1)이 걸린다. 표준 입출력 공백포함된 함수를 입력 받을땐 scanf/ cin 안됨 → 둘다 공백 앞까지만 입력으로 받기 때문 → 따라서 getline을 사용하자! c에 printf나 scanf 안쓸꺼면 ios::sync_with_stdio(0) 사용하기 (sync를 끊는다는 뜻) cin.tie(0) : cin 사용 시 cout 버퍼를 비울 필요가 없기 때문에 이를 사용. endl : 사용하지 말기.. 개행하고 버퍼 비우는 명령어이므로 할 필요가 없다.

[BOJ/C++] 1966번 프린터 큐

[Silver III] 프린터 큐 - 1966 문제 링크 성능 요약 메모리: 2024 KB, 시간: 4 ms 분류 자료 구조(data_structures), 구현(implementation), 큐(queue), 시뮬레이션(simulation) 문제 설명 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인..

자료구조 배열 복습

// 배열 인덱스에 값 추가 방법 void add(int idx, int values) { for (int i=arrSize-2; i>=idx; i--) { arr[i+1]=arr[i]; } arr[idx]=values; } // 배열에 인덱스 값 삭제 void remove (int idx) { for (int i=idx+1; iarrSize = _arrSize; this->arr = new int[arrSize]; for (int i = 0; i < arrSize; i++) { arr[i] = 0; } } void set(int idx, int values) { arr[idx] = values; } void shift(int d) { for (int i = 0; i < d; i++) { int last..

[C++] 백준 2675

문제 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다. S에는 QR Code "alphanumeric" 문자만 들어있다. QR Code "alphanumeric" 문자는 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\$%*+-./: 이다. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 반복 횟수 R(1 ≤ R ≤ 8), 문자열 S가 공백으로 구분되어 주어진다. S의 길이는 적어도 1이며, 20글자를 넘지 않는다. 출력 각 테스트 케이스에 대해 P를 출력한다. 풀이 #include ..

[C++] 백준 10809

문제 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. 출력 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다. 풀이 #include #include using namespace std; int main() { string s..

[C++] 백준 11720

문제 N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. 출력 입력으로 주어진 숫자 N개의 합을 출력한다. 풀이 #include using namespace std; int main() { int num; int sum = 0; char input; cin >> num; for (int i = 0; i > input; // char 변수 cin은 철자 한개만 변수값이됨.. sum = sum + (input-48); } cout