본문 바로가기

python61

Programmers - 자동완성[파이썬(python)] 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/17685 코딩테스트 연습 - [3차] 자동완성 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g programmers.co.kr 문제 설명 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른.. 2022. 1. 3.
Trie 자료구조 [Python / 파이썬] 1. Trie 자료구조란? ※ 입력되는 문자열을 Tree 형식으로 만들어 진행되어 보다 빠르게 문자열 검색이 가능한 자료구조이다. 보통 list에서 문자열이 존재하는지 확인하기 위해서는 O(n) (n은 list의 길이)이라는 시간이 걸리는데 Trie 알고리즘을 사용하면 O(m) (m은 문자열의 길이) 이라는 짧은 시간이 소요되기 때문에 엄청 효율적이라고 할 수 있다. 2. 어떤 경우에 적합한가? ※문자열을 검색하는 문제에서 입력되는 문자열이 많을 경우 자주 사용된다. 빠른 시간복잡도 덕분에 검색엔진 사이트에서 제공하는 자동 완성 및 검색어 추천 기능에서 Trie 자료구조를 사용한다. 3. Trie 자료구조의 형태 1. Trie 알고리즘은 노드를 이용한 Tree 형태로 이루어져 있다. 2. 문자열의 끝을 .. 2022. 1. 3.
백준 - 11000번 - 강의실 배정[파이썬(python)] 문제 출처 : https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력 첫 번째 줄에 N이 주어진다. (1 ≤ N.. 2021. 12. 30.
백준 - 2470번 - 두 용액[파이썬(python)] 문제 출처 : https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 .. 2021. 12. 30.

티스토리툴바