본문 바로가기
728x90

IT/Python

 (167)
[백준] 1735번 분수합 [Python] - 기약 분수 두 분수의 합을 기약 분수로 표현하는 문제 더보기 문제 분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자. 두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다. 입력 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. 출력 첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다. https://www.acmicpc.net/problem/1735 분모끼리 곱해서 분모로 두고, 분자는 다른 분수의 ..
[백준] 1074번 Z [Python] $2^N \times 2^N$ 배열을 Z 모양으로 탐색할 때 r행 r열은 몇 번째로 방문하는지 구하는 문제 $($0부터 시작$)$ 더보기 문제 한수는 크기가 $2^N \times 2^N$인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 $2^{N-1} \times 2^{N-1}$로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 $2^2 \times 2^2$ 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 첫째 줄에 정수 N, r, c가 주어진다. 출력..
[백준] 1931번 회의실 배정 [Python] - 정렬 회의실 사용표 시간을 보고 이어서 사용할 수 있는 최대 회의의 수 구하는 문제 더보기 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회..
[프로그래머스] Lv.1 덧칠하기 [Python] 가로 n 미터 벽, 가로 m미터 롤러와 페인트가 벗겨진 구간의 정보가 담긴 배열이 주어질 때, 최소 롤러 사용 횟수를 구하는 문제 롤러 1번 사용으로 벽의 가로 m미터가 모두 칠해짐 $($세로를 다 훑는다고 생각하면 됨$)$ 더보기 문제 설명 어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있습니다. 벽에 동아리 · 학회 홍보나 회사 채용 공고 포스터 등을 게시하기 위해 테이프로 붙였다가 철거할 때 떼는 일이 많고 그 과정에서 페인트가 벗겨지곤 합니다. 페인트가 벗겨진 벽이 보기 흉해져 학교는 벽에 페인트를 덧칠하기로 했습니다. 넓은 벽 전체에 페인트를 새로 칠하는 대신, 구역을 나누어 일부만 페인트를 새로 칠 함으로써 예산을 아끼려 합니다. 이를 위해 벽을 1미터 길이의 구역 n개로 나누고, 각 구역..
[프로그래머스] Lv.1 실패율 [Python] 주어진 스테이지 별 플레이어 수를 통해 실패율이 높은 순서대로 스테이지를 정렬한 배열 만드는 문제 더보기 문제 설명 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라. 실패율은 다음과 같이 정의한다. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 전..
[백준] 18870번 좌표 압축 [Python] - 좌표 압축 입력 받은 숫자를 오름차순으로 정렬하고 중복을 없애 인덱스 값으로 치환하는 문제 출력은 원래 받은 숫자의 순서대로 치환한 값을 출력하기 더보기 문제 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. 출력 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다. 제한 1 ≤ N ≤ 1,000,000 -109 ≤ ..
[백준] 11724번 연결 요소의 개수 [Python] - 그래프 이론 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 문제 더보기 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. https://www.acmicpc.net/problem/11724 1번 노드부터 시작해서 연결된 번호의 노드를 훑고 지나면서 각 노드랑 연결된 노드까지도 살펴봅니다..
[백준] 2630번 색종이 만들기 [Python] - 재귀 아래 그림처럼 색종이를 가로, 세로를 2등분해서 나누어 각 색깔별 색종이 수를 구함 처음 가로, 세로의 길이는 2의 제곱수이고 같은 색으로만 이루어진 색종이는 더이상 나누지 않는다. 더보기 문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크..
[프로그래머스] Lv.1 [1차] 다트 게임 [Python] 주어진 규칙에 따라 다트 게임 점수 총합을 구하는 문제 더보기 문제 설명 다트 게임 카카오톡에 뜬 네 번째 별! 심심할 땐? 카카오톡 게임별~ 카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다. 갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다. 다트 게임은 총 3번의 기회로 구성된다. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다. 점수와 함께 Single$($S$)$, Double$($D$)$, Triple$($T$)$ 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제..
[프로그래머스] Lv.1 기사단원의 무기 [Python] - 약수의 개수 주어진 number에 대해서 1~n까지의 수의 약수의 개수의 총합을 구하는 문제 주어진 limit을 초과한 약수의 개수는 그 값 대신 주어진 power로 치환해서 총합을 구해야 함 더보기 문제 설명 숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다. 각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다. 예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 ..
[백준] 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 직사각형을 타일로 채우게 됩니다. 위..

티스토리툴바