본문 바로가기
반응형

코딩테스트 및 개인공부54

[백준 - 5397번] 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 강산이는 키보드로 입력한 키는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표이다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000).. 2022. 4. 26.
[백준 - 1406번] 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다. 이 편집기가 지원하는 명령어는 다음과 같다. L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨) D 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨) B 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무.. 2022. 4. 26.
[강의정리] [배열] 실전 알고리즘 0x03 정리 바킹독의 [실전 알고리즘] 0x03강 - 배열 정리. -배열의 성질 O(1)에 k번째 원소를 확인/변경 가능 시작 주소에서 k칸 만큼 오른쪽으로 가면 되기 때문. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양이 거의 없다. Cache hit rate가 높음 메모리 상에데이터들이 붙어 있으니까. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 -시간 복잡도 임의의 위치에 있는 원소를 확인/변경 = O(1) 원소를 끝에 추가 = O(1) 마지막 원소를 제거 = O(1) 임의의 위치에 원소를 추가/임의 위치의 원소 제거 = O(N) -배열 전체를 특정값으로 초기화 for문으로 값을 하나하나 다 바꾸는 방식 : 무난 algori.. 2022. 4. 22.
[백준 - 10807번] 개수 세기 문제 총 N개의 정수가 주어졌을 때, 정수 v가 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거나 같으며, 100보다 작거나 같다. 출력 첫째 줄에 입력으로 주어진 N개의 정수 중에 v가 몇 개인지 출력한다. 예제 입력 1 복사 11 1 4 1 2 4 2 4 2 3 4 4 2 예제 출력 1 복사 3 예제 입력 2 복사 11 1 4 1 2 4 2 4 2 3 4 4 5 예제 출력 2 복사 0 풀이 과정 이건 풀이과정을 따로 쓸 필요도 없이 너무 쉬웠던 문제. 배열 입력받고 그냥 순회하면서 해당 v값 나올때 마.. 2022. 4. 22.
[백준 - 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) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. 예제 입력 1 복사 9 5 12 7 10 9 1 2 3 11 13 예제 출력 1 복사 3 풀이 과정 O(n^2)으로 풀면 쉽겠지만 O(n)의 시간복잡도로 풀어보자. n개의 .. 2022. 4. 22.
반응형

티스토리툴바