몽상실현개발주의

[종만북] 문자열 검색 - KMP 알고리즘 / 문자열 문자열 검색 - KMP 알고리즘 단순한 알고리즘의 검색 과정에서 얻는정보를 이용하여 시간을 절약 할 수 있다. H 의 부분 문자열을 N 과 비교 시, N 의 첫 글자와 대응 되지 않는 H 의 부분문자열 위치를 시작 위치 후보들에서 제외 시키는 방법으로 구현하면 최적화가 가능하다. 이와 같은 방법은 커누스-모리스-프랫(Knuth-Morris-Pratt) 알고리즘이며, 흔히 KMP 알고리즘으로 부른다. H[i...i+matched-1] = N[...matched-1](접두사) 이 일치 할때, i < i+k < matched-1, H[i+k...i+matched-1] = N[K...] (접미사) 가 일치 한다면, N[K...] (접미사) = N[...mat..

[종만북] 문자열 검색 / 문자열 문자열 현대의 컴퓨터는 많은 양의 문자열 자료를 다룹니다. 문서 파일, 인터넷의 웹페이지. 이메일 그리고 문자 메시지들이 모두 다 문자열입니다. 때문에 문자열을 다루는 문제와 자료구조는 전산학의 중요한 연구 주제이며, 정보 검색 (Information retrieval) 이나 생물 정보학 (bioinformatics) 분야에서 특히 이용하게 사용됩니다. 문자열을 다루는 알고리즘 또한 매우 범위가 깊고 넓지만, 시간이 제한된 프로그래밍 대회 특성상 구현이 비교적 간단한 알고리즘이 주로 사용 됩니다. - KPM 알고리즘 : 문자열 검색 - 접미사 배열 (suffix array) : 문자열 처리 용어에 관하여 문자열의 부분 문자열(substring), 접두사(prefix), ..

[종만북] Queue, Stack, Deque / 큐와 스택, 데크 큐와 스택, 데크 Queue 큐 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있다. 가장 먼저 들어간 자료를 가장 먼저 꺼내게 된다. FIFO (First In First Out) 선입선출 Stack 스택 한쪽 끝에서만 자료를 넣고 뺄 수 있다. 가장 늦게 들어간 자료를 가장 먼저 꺼내게 된다. LIFO (Last In First Out) 후입 선출 전산학 전반에 걸쳐 널리 사용된다. 함수 호출이 끝나고 이전 함수로 돌아갈 때, 이 함수 바로 이전의 함수로 돌아가야 하는데 컴퓨터는 내부적으로 스택(Stack)을 사용하여 함수들의 문백(context)를 관리한다. Deque 데크 양쪽 끝에서 자료들을 넣고 뺄 수 있는 자료 구..

[Algospot] 비트마스크 / GRADUATION / Python 파이썬 풀이 원형 큐를 구현하는 문제이다. 모든 병사의 생사여부 정보를 원형 큐로 구현하여 index 로 조회하였더니 시간초과가 발생하였다. 모든 병사의 정보가 아닌 생존한 병사의 정보만 저장하고, 사망한 병사의 정보는 array 에서 삭제시켜 전체 array 크기를 줄여 매 시행마다 전체 시간을 축소 시키는 방법이 유효한 전략이다. 간단하지만 간단하지 않은 문제였다. C = int(input()) for _ in range(C): N, K = map(int, input().split()) alive = [x+1 for x in range(N)] kill = 0 while len(alive) > 2: del alive[kill] kil..

[프로그래머스] level1 / 최소직사각형 / Python 파이썬 https://programmers.co.kr/learn/courses/30/lessons/86491 코딩테스트 연습 - 최소직사각형 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133 programmers.co.kr 풀이 알고리즘 스킬이 아닌 아이디어가 중요한 문제였다. 완전 탐색으로 접근하였다가 아주아주 큰 코 다친 문제. 1. 가로와 세로 2개의 모서리 중 큰 값을 모두 가로로 두고 작은값을 모두 세로로 둔다 2. 가로/세로 중 가장 큰값으로 만든 사격형의 넓이가 답이 된다. 간단하였다... def solu..

[프로그래머스] level1 / 없는 숫자 더하기 / Python 파이썬 https://programmers.co.kr/learn/courses/30/lessons/86051 코딩테스트 연습 - 없는 숫자 더하기 0부터 9까지의 숫자 중 일부가 들어있는 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요. 제한 programmers.co.kr 풀이 def solution(numbers): answer = 0 numsCheck = [0] * 10 for number in numbers: numsCheck[number] += 1 for i in range(10): if numsChec..

[프로그래머스] level1 / 약수의 개수와 덧셈 / Python 파이썬 https://programmers.co.kr/learn/courses/30/lessons/77884 코딩테스트 연습 - 약수의 개수와 덧셈 두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주 programmers.co.kr 풀이 def get_n(N): cnt = 0 for i in range(1, N+1): if N % i: continue cnt += 1 return cnt def solution(left, right): answer = 0 for i ..

[프로그래머스] level1 / 숫자 문자열과 영단어 / Python 파이썬 https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 풀이 영어 문자를 숫자와 매칭시켜 변환하는 문제이다. num_dic = {'zero': '0', 'one': '1', 'two': '2', 'three': '3', 'four':'4', 'five':'5', 'six':'6', 'seven':'7', 'eight':'8', '..