본문 바로가기

coding20

[Baekjoon] 1543. 문서 검색 # Problem 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다. 세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어.. 2021. 4. 19.
[Baekjoon] 1920. 수 찾기 # Problem N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. # My Answer import collections h = collections.defaultdict(list) n = in.. 2021. 4. 15.
[코딩 + 알고리즘 완주반] 19일차. 이진탐색( Binary Search ), 순차탐색 ( Sequential Search ) # 이진 탐색 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 # 분할 정복 알고리즘 divide : 문제를 하나 또는 둘 이상으로 나눈다 conquer : 나눠진 문제가 충분히 작고 해결이 가능하다면 해결하고, 그렇지 않으면 다시 나눈다 # 이진탐색 divide : 리스트를 두 개의 서브 리스트로 나눈다 conquer : 검색할 숫자 > 중간값이면 뒷부분의 서브 리스트에서 검색할 숫자를 찾는다 검색할 숫자 < 중간값이면 앞부분의 서브 리스트에서 검색할 숫자를 찾는다 # 알고리즘 구현 def binary_search(data, search): print (data) if len(data) == 1 and search == data[0]: return True if len(data) .. 2021. 4. 5.
[코딩 + 알고리즘 완주반] 18일차. 병합정렬 (merge sort) # 병합 정렬 재귀 용법을 사용한 정렬 알고리즘 리스트를 반으로 잘라 나눈 후 재귀적으로 병합 정렬 부분 리스트를 다시 하나의 정렬된 리스트로 합병 # 알고리즘 구현 # 병합하기 def merge(left,right): lp = 0 rp = 0 merged=list() # left,right 둘다 데이터 있을 때 while len(left) >lp and len(right) >rp : if left[lp]>right[rp]: merged.append(right[rp]) rp+=1 else: merged.append(left[lp]) lp+=1 # left에만 데이터 남아있을 때 while len(left) > lp : merged.append(left[lp]) lp+=1 # right에만 데이터 남아있을.. 2021. 4. 4.
[코딩 + 알고리즘 완주반] 18일차. 퀵 정렬 # 퀵 정렬 기준점을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수 작성 각 왼쪽, 오른쪽은 재귀 용법을 사용해서 반복 return qsort(left) + [pivot] + qsort(right) #퀵 정렬 구현 def qsort(data): if len(data) data[index]: left.append(data[index]) else: right.append(data[index]) return qsort(left) + [pivot] + qsort(right) # 리스트 컴프리헨션 사용 def qsort(data): if len(data) item ] right = [ item for item in data[1:] if pivot 2021. 4. 4.
[LEET CODE] 20. Valid Parentheses # Problem Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Constraints: 1 bool: stack = [] table = { ')': '(', '}': '{', ']': '[', } # 스택 이용 예외 처리 및 일치 여부 판별 for char in s: if char not in.. 2021. 3. 23.
반응형

티스토리툴바