본문 바로가기
728x90

파이썬

 (171)
[백준] 1927번 최소 힙 [Python] - 자료구조, 힙 0이 아닌 숫자를 배열에 저장 0일 경우 배열 내 최솟값 출력 및 제거 위 연산을 구현하는 문제 더보기 문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N$(1 ≤ N ≤ 100,000)$이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는$($추가하는$)$ 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또..
[백준] 11727번 2xn 타일링 2 [Python] - 다이나믹 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 문제 더보기 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. $(1 ≤ n ≤ 1,000)$ 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. https://www.acmicpc.net/problem/11727 2x$(n-1)$개 타일이 채워진 경우 2×1 타일을 추가하면 2xn 직사각형을 타일로 채우게 되고, 2x$(n-2)$개 타일이 채워진 경우 1x2 타일 2개 또는 2×2 타일을 추가하면 2xn 직사각형을 타일로 채우게 됩니다. 위..
[백준] 18110번 solved.ac [Python] 30% 절사평균과 반올림으로 점수 매기기 30% 절사평균은 상위 15%, 하위 15%를 각각 제외하고 계산한 평균입니다. 더보기 문제 solved.ac는 Sogang ICPC Team 학회원들의 알고리즘 공부에 도움을 주고자 만든 서비스이다. 지금은 서강대뿐만 아니라 수많은 사람들이 solved.ac의 도움을 받아 알고리즘 공부를 하고 있다. ICPC Team은 백준 온라인 저지에서 문제풀이를 연습하는데, 백준 온라인 저지의 문제들에는 난이도 표기가 없어서, 지금까지는 다양한 문제를 풀어 보고 싶더라도 난이도를 가늠하기 어려워 무슨 문제를 풀어야 할지 판단하기 곤란했기 때문에 solved.ac가 만들어졌다. solved.ac가 생긴 이후 전국에서 200명 이상의 기여자 분들께서 소중한 난이도 의견을 공유..
[백준] 1929번 소수 구하기 [Python] M이상 N이하의 소수를 모두 출력 더보기 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. $(1 ≤ M ≤ N ≤ 1,000,000)$ M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. https://www.acmicpc.net/problem/1929 에라토스테네스의 체 - 크기가 작은 소수 순서대로 그 소수의 배수를 제거해 나가는 방식 위 과정을 통해 합성수는 제거되고 소수만 남게 됩니다. import sys def f(M,N): li = [False,False,True]+[i%2 for i in range(3,N+1)] for n in range(3, ..
[백준] 2775번 부녀회장이 될테야 [Python] - 다이나믹 k층에 n호에는 몇 명이 살고 있는지 알아내는 문제 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다. a층의 b호에 살려면 자신의 아래$($a-1$)$층의 1호부터 b호까지 사람들의 수의 합만큼 산다. 더보기 문제 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래$($a-1$)$층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다. 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에..
[백준] 2231번 분해합 [Python] 주어진 N에 대한 생성자 찾기 어떤 수의 분해합은 어떤 수와 그 수의 모든 자리수와 합이고, 어떤 수는 그 분해합의 생성자이다. 더보기 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256$(=245+2+4+5)$이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N$(1 ≤ N ≤ 1,000,000)$이 주어진다. 출력 첫째 줄에 답을..
[백준] 21316번 스피카 [Python] - 그래프이론 별이 번호로 주어지고, 이어진 별의 정보가 주어졌을 때, 스피카를 찾는 문제 더보기 문제 위 그림은 처녀자리 중 12개의 별을 12개의 선분으로 이어 만든 그림이다. 시은이는 임의로 각 별에 1부터 12까지의 서로 다른 정수 번호를 부여하고, 12개의 정수 쌍으로 각 선분이 어떤 두 별을 잇는지 기록하였다. 하지만 어떤 별에 어떤 번호를 부여했는지 잊어버렸다고 한다. 선분들의 정보가 주어질 때, 가장 밝은 별인 Spica가 몇 번 별이였는지 알려주자. 입력 입력은 12개의 줄로 주어진다. 각 줄에는 서로 다른 두 개의 정수 x, y가 주어지며, 두 별 x와 y를 잇는 선분이 있음을 의미한다. 반드시 그림과 같은 모습임이 보장된다. 출력 입력으로 주어진 그래프에서 Spica는 몇 번 별인지 출력하여라. 번..
[백준] 26265번 멘토와 멘티 [Python] - 정렬 멘토와 멘티 이름을 전달 받으면 멘토 이름은 사전 순서대로 멘토 이름이 같으면 멘티 이름은 역순으로 정렬 하는 문제 더보기 문제 서울사이버대학교에는 멘토링 프로그램이 있다. 멘토링 프로그램은 한 명의 멘토$($선배학습자$)$가 여러 명의 멘티$($후배학습자$)$에게 대학 생활에 대한 노하우와 정보 등을 전수하는 것이다. 빅데이터·AI 센터에서 딥러닝 서버를 돌리며 바쁜 나날을 보내던 노교수는, 어느 날 멘토링 회의 참석 요청이 들어와 이를 준비하던 도중 멘토-멘티 순서쌍 목록이 적힌 노트를 찾았다. 하지만 노트가 제대로 정리되어 있지 않아 분석이 어려웠으므로, 마침 센터에서 인턴을 하는 대학원생 뚜루에게 목록의 정렬을 맡기기로 했다. 하지만 논문을 쓰느라 수면 부족에 시달리고 있는 뚜루는 이러한 프로그램..
[프로그래머스] Lv.1 로또의 최고 순위와 최저 순위 [Python] 6개의 숫자 중 모르는 번호는 0을 주어졌을 때, 최고 순위와 최저 순위를 구하는 문제 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호가 일치 3 4개 번호가 일치 4 3개 번호가 일치 5 2개 번호가 일치 6(낙첨) 그 외 더보기 문제 설명 로또 6/45$($이하 '로또'로 표기$)$는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. $($실제로 사용되는 로또 순위의 결정 방식과는 약간 다르지만, 이 문제에서는 지문에 명시된 대로 로또 순위를 결정하도록 합니다. $)$ 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호가 일치 3 4개 번호가 일치 4 3개 번호가 일치 5 2개 번호가 일치 6(낙첨) 그 외 로또를 구매한 민우..
[프로그래머스] Lv.1 올알이[2] [Python] 발음 가능한 옹알이로만 조합해서 발음 할 수 있는 단어의 개수를 구하는 문제 연속된 옹알이는 못 함 더보기 문제 설명 머쓱이는 태어난 지 11개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음과 네 가지 발음을 조합해서 만들 수 있는 발음밖에 하지 못하고 연속해서 같은 발음을 하는 것을 어려워합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ babbling의 길이 ≤ 100 1 ≤ babbling[i]의 길이 ≤ 30 문자열은 알파벳 소문자로만 이루어져 있습니다. https://school.programmers.co.kr/..
[백준] 20114번 미아 노트 [Python] 주어진 N,H,W와 옆으로, 위 아래로 번진 단어를 통해 원래 단어를 찾는 문제 N : 원래 단어의 길이 H=2 일 때, abc -> abc abc W=3 일 때, abc -> aaabbbccc 더보기 문제 미아는 과일을 좋아하는 소녀이다. 그녀의 비밀 노트에는 과일에 대해 그녀가 수집한 정보들이 가득하다. 평소와 다를 바 없이 과일들을 잔뜩 관찰하고 기쁜 마음으로 하교하던 어느 날, 친구가 뒤에서 덮치는 바람에 실수로 비밀 노트를 물에 빠뜨리고 말았다. 다행히 노트는 건질 수 있었지만, 노트에 적어두었던 정보들이 번지고 지워져버려 일부는 알아볼 수 없게 되었다. 노트에 적힌 문자열이 번진 패턴은 일정했는데, 가령 "abc" 문자가 세로로 3글자씩, 가로로 2글자씩 번진 경우는 다음과 같았다. aabbc..
[백준] 9575번 행운의 수 [Python] 주어진 세개의 수열의 원소들의 조합으로 합을 냈을 때 5나 8로만 이루어진 숫자를 만들 때, 그 숫자의 개수를 구하는 문제 더보기 문제 한슬이는 5와 8이 행운의 수라고 생각한다. 그래서 한슬이는 각 자리가 5와 8로만 이뤄져 있는 수를 행운의 수라고 한다. 정수 수열 A, B, C가 주어졌을 때 세 수열에서 각각 하나의 정수를 골라서 만들 수 있는 서로 다른 행운의 수의 개수를 구해보자. 예를 들어 A = [1, 10, 100], B = [3, 53], C = [4, 54]라고 한다면, 행운의 수를 만드는 방법은 8 = 1 + 3 + 4, 58 = 1 + 3 + 54, 58 = 1 + 53 + 4와 같이 총 3가지가 있다. 58은 2가지 방법으로 만들 수 있으니, 서로 다른 행운의 수의 개수는 8과 5..

티스토리툴바