파이썬

[파이썬/Python] 정규표현식 - 리스트 내 원소들 중 숫자만 필터링하기

import re page = ['처음', '5개 앞', '이전', '6', '7', '8', '9', '10', '다음', '5개 뒤', '마지막'] p = re.compile("^[0-9]+$") page_only_digit = list(filter(p.match, page)) print(page_only_digit) # ['6', '7', '8', '9', '10'] 원래는 p.match 부분에 isdigit 내장 함수를 사용하려고 했는데, '5개 앞' 같이 원소 내 공백이 존재하면 내부적으로 구현되어 있는 ord 메서드를 적용할 수가 없어서 먹히질 않았습니다. 그래서 어쩔 수 없이 정규표현식으로 걸러줬습니다.

[파이썬/Python] Collections - Deque

들어가며 코딩테스트에 응시할 때 빠르게 찾아볼 수 있도록 따로 정리한 내용입니다. 공부하시기에는 빈약한 내용일 수 있음을 미리 알려드립니다. 공식 문서를 참고할 때에는 대부분의 기업이 이용하고 있는 프로그래머스 코딩테스트 환경에 적용된 python 3.8 버전의 collections을 참고했습니다. 코딩테스트용으로 작성한 글인 만큼 빠르게 훑을 수 있어야 하므로 경어체를 사용하지 않겠습니다. 초기화 방법 1. 기존의 iterable 객체 없이 빈 큐를 초기화 from collections import deque queue = deque() print(d) # deque([]) 2. 기존의 iterable 객체 없이 큐를 구현하되, 구현하면서 임시의 iterable 객체를 이용하여 초기화 from coll..

[파이썬/Python] 리스트(list)의 메소드 시간 복잡도(Big-O) 정리

파이썬으로 코딩테스트를 진행하며 가장 많이 쓰는 기본 자료형은 리스트(list)와 문자열(string), 딕셔너리(dictionary), 집합(set) 정도이다. 기본 자료형을 벗어난 것 중 많이 쓰는 것은 collections 모듈의 Counter와 deque 정도가 있겠고, 아주 가끔 itertools 모듈의 permutations 혹은 combinations 정도를 쓰는 것 같다(사실 이 둘은 시간복잡도가 터져버리기 때문에 거의 안 쓴다). 약간 난이도가 있는 코딩테스트 문제들은 항상 시간복잡도와 공간복잡도에 대한 제약이 주어진다. 특히 시간복잡도에 대한 제약은 아주 중요하며, 이를 고려하기 위해서는 이용하는 자료형의 메소드 별 시간 복잡도를 알고 있어야 한다. 그래서 이번 기회에 정리를 해볼까 한..

[백준 알고리즘][파이썬/Python] 1057번: 토너먼트

문제 시간 제한 : 1초, 메모리 제한 : 128 MB 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를..

[백준 알고리즘][파이썬/Python] 1500번: 최대 곱

문제 시간 제한 : 2초, 메모리 제한 : 128 MB 세준이는 정수 S와 K가 주어졌을 때, 합이 S인 K개의 양의 정수를 찾으려고 한다. 만약 여러 개일 경우 그 곱을 가능한 최대로 하려고 한다. 가능한 최대의 곱을 출력한다. 만약 S=10, K=3이면, 3,3,4는 곱이 36으로 최대이다. 입력 첫째 줄에 두 수 S와 K가 주어진다. K는 20보다 작거나 같고, S는 100보다 작거나 같으며 K보다 크거나 같다. 출력 첫째 줄에 정답을 출력한다. 답은 9223372036854775807보다 작다. 입출력 예 제출 코드 s, k = map(int, input().split()) key = s // k if s % k == 0: print(pow(key, k)) else: result = 1 while..

[백준 알고리즘][파이썬/Python] 1812번: 사탕

문제 시간 제한 : 2초, 메모리 제한 : 128 MB N(3≤N≤999, N은 홀수)명의 학생들이 원 모양으로 둘러앉아 있다. 각 학생들은 모두 몇 개의 사탕(≤100,000)을 가지고 있는데 그 개수는 사람마다 다를 수 있고, 사탕을 아예 가지고 있지 않을 수도 있다. 물론 사탕의 개수는 음이 아닌 정수이다. 편의상 학생들에게 번호를 매기는데, 반시계 방향으로 1번 학생, 2번 학생, …, N번 학생으로 번호를 매겼다. 1번 학생 오른쪽엔 2번 학생, 2번 학생 오른쪽엔 3번 학생이 앉아 있는 것이고, 마지막 N번 학생 오른쪽엔 1번 학생이 앉아 있게 된다. 우리는 인접한 두 학생이 가지고 있는 사탕의 수의 합을 안다. 즉 1번 학생과 2번 학생이 가지고 있는 사탕의 수의 합, 2번 학생과 3번 학생..

[백준 알고리즘][파이썬/Python] 1094번: 막대기

문제 시간 제한 : 2초, 메모리 제한 : 128 MB 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른 다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다. 막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다. 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, ..

[백준 알고리즘][파이썬/Python] 2293번: 동전 1

문제 시간 제한 : 0.5 초 (추가 시간 없음), 메모리 제한 : 4 MB n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 2 ³¹ 보다 작다. 입출력 예 제출 코드 n, k = map(int, input().split()) c = ..