전체 글128 구간 합 계산 [Python / 파이썬] 1. 구간 합 계산 백준이나, 프로그래머스 문제를 풀다보면 구간 합을 구해야 하는 문제가 종종 출제된다. 구간 합 문제란 연속적으로 나열된 N 개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제를 말한다. 예를 들어 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정해보자. 여기에서 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40으로 90이 될 것이다. 이러한 구간 합 계산 문제는 여러 개의 쿼리로 구성되는 문제 형태로 출제되는 경우가 많다. 다수의 구간에 대해서 합을 각각 구하도록 요구된다. 예를 들어 M개의 쿼리가 존재한다고 가정해보자. 각 쿼리는 Left와 Right로 구성되며, 이는 [Left, Right]의 구간을 의미한다. 결과적으로 .. 2022. 1. 5. 정규 표현식 2 [Python / 파이썬] 정규 표현식 1에 이어서 몇몇 메타 문자의 의미, 그룹(Group)을 만드는 법, 전방 탐색 등 더욱 강력한 정규 표현식에 대해 정리 해보자. 1. 메타문자 아직 살펴보지 않은 메타 문자에 대해서 모두 살펴보자. 여기에서 다룰 메타 문자는 앞에서 살펴본 메타 문자와 성격이 조금 다르다. 앞에서 살펴본 +, *, [], {} 등의 메타문자는 매치가 진행될 때 현재 매치되고 있는 문자열의 위치가 변경된다(보통 소비된다고 표현한다). 하지만 이와 달리 문자열을 소비시키지 않는 메타 문자도 있다. 이번에는 이런 문자열 소비가 없는(zerowidth assertions) 메타 문자에 대해 살펴보자. 1.1 | | 메타 문자는 or과 동일한 의미로 사용된다. A|B라는 정규식이 있다면 A 또는 B라는 의미가 된다... 2022. 1. 4. 정규 표현식 1 [Python / 파이썬] 파이썬 문법 중 정규 표현식이라는 것이 있는데, 자주 사용하지 않다 보니 자꾸 까먹는다. 그래서 정규 표현식을 사용할 때마다 구글링 해서 사용하곤 했다. 구글링 없이 정규식을 사용하기 위해 자주 사용되는 정규 표현식을 내 나름대로 정리해보려 한다. 참고 자료 : https://wikidocs.net/4308 1. 메타 문자 정규 표현식에서 사용하는 메타 문자(meta characters)에는 다음과 같은 것이 있다. ※ 메타 문자란 원래 그 문자가 가진 뜻이 아닌 특별한 용도로 사용하는 문자를 말한다. . ^ $ * + ? { } [ ] \ | ( ) 정규 표현식에 위 메타 문자를 사용하면 특별한 의미를 갖게 된다. 자, 그러면 가장 간단한 정규 표현식부터 시작해 각 메타 문자의 의미와 사용법을 알아보자.. 2022. 1. 4. 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. 이전 1 ··· 17 18 19 20 21 22 다음
