본문 바로가기

Dev/Algorithm62

Defaultdict 사용하기 defaultdict란?defaultdict는 Python의 collections 모듈에 포함된 클래스입니다. 일반적인 딕셔너리(dict)와 비슷하지만, 키가 존재하지 않을 때 기본값을 제공하는 기능을 추가로 제공합니다. 이를 통해 키가 없는 경우 KeyError를 발생시키는 대신, 지정된 기본값을 반환하거나 새로운 키-값 쌍을 자동으로 생성합니다.defaultdict는 첫 번째 인자로 기본값을 생성하는 팩토리 함수를 받습니다. 예를 들어, int, list, set 등을 팩토리로 사용할 수 있습니다. 키에 접근할 때 해당 키가 없으면 팩토리 함수가 호출되어 기본값이 생성됩니다.defaultdict의 동작 방식일반 dict: d = {}d['key'] += 1 # KeyError 발생: 'key'가 없기.. 2025. 8. 7.
[백준] #2343 기타 레슨 - 파이썬 문제강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.강토의 각 강의의 길이가 분 단.. 2025. 8. 1.
[백준] #31091 거짓말 - 파이썬 문제당신 앞에는 $N$명의 사람들이 있다. 각 사람은 자신을 포함하여 몇 명 이상이 거짓말을 하고 있다고 말하거나, 몇 명 이하의 사람이 거짓말을 하고 있다고 말한다.예를 들어, 각 사람이 다음과 같이 주장한다고 하자.첫 번째 사람이 이렇게 말한다: "1명 이상이 거짓말을 하고 있다!"두 번째와 세 번째 사람이 이렇게 말한다: "1명 이하가 거짓말을 하고 있다!"네 번째 사람이 이렇게 말한다: "2명 이상이 거짓말을 하고 있다!"이 경우에 가능한 시나리오는 다음과 같다.네 번째 사람만 거짓말을 하고 있다.두 번째와 세 번째 사람이 거짓말을 하고 있다.사람들의 주장이 주어질 때, 거짓말을 하는 사람의 수로 가능한 것을 모두 구해라.입력첫째 줄에 사람의 수 $N$이 주어진다.둘째 줄에 $N$개의 정수 $k_.. 2025. 7. 31.
[백준] #11058 크리보드 - 파이썬 문제크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.화면에 A를 출력한다.Ctrl-A: 화면을 전체 선택한다Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.출력크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.예제 입력 1 3예제 출력 1 3예제 입력 2 7예제 출력 2 9복기1. 패턴을 파악하기 너무 어렵다...ㅠㅠ2. 복붙을 하려면 전체선택(Ctrl+A) -> 복사.. 2025. 7. 23.
[백준] #21921 블로그 - 파이썬 문제찬솔이는 블로그를 시작한 지 벌써 $N$일이 지났다.요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.찬솔이는 $X$일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.찬솔이를 대신해서 $X$일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.입력첫째 줄에 블로그를 시작하고 지난 일수 $N$와 $X$가 공백으로 구분되어 주어진다.둘째 줄에는 블로그 시작 $1$일차부터 $N$일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.출력첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.제한 $1 .. 2025. 7. 21.
[백준] #10655 마라톤 1 - 파이썬 문제농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.마라톤 코스는 N (3 ≤ N ≤ 100000) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다. 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한개를 몰래 건너뛰려 한다. 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.젖소 박승원이 체크포인트 한개를 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?참고로, 젖소 마라.. 2025. 7. 14.
[백준] #14503 로봇 청소기 - 파이썬 문제로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.로봇 청소기가 있는 방은 N×M$N \times M$ 크기의 직사각형으로 나타낼 수 있으며, 1×1$1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r,c)$(r, c)$로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0)$(0, 0)$, 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N−1,M−1)$(N-1, M-1)$이다. 즉, 좌표 (r,c)$(r, c)$는 북쪽에서 (r+1)$(r+1)$번째에 있는 줄의 서쪽에서 (c+1)$(c+1)$번째 칸을 .. 2025. 6. 18.
[백준] #1992 쿼드트리 - 파이썬 문제흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 .. 2025. 6. 11.
[백준] #12851 숨바꼭질2 - 파이썬 문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오. 입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.출력첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.둘째 줄에는 .. 2025. 6. 10.
[백준] #1759 암호 만들기 - 파이썬 문제바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형.. 2025. 6. 5.

티스토리툴바