본문 바로가기
728x90

IT

 (221)
[백준] 21736번 헌내기는 친구가 필요해 [Python] - 그래프 이론 $N \times M$ 크기이며 캠퍼스에서 O는 빈 공간, X는 벽, I는 도연이, P는 사람으로 주어질 때, 상하좌우로만 이동가능한 도연이가 몇 명의 사람을 만날 수 있을까? 더보기 문제 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 도연이가 다니는 대학의 캠퍼스는 $N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 $(x, y)$에 있다면 이동할 수 있는 곳은 $(x+1, y)$, $(x, y+1)$, $(x-1, y)$, $(x, y-1)$이다. 단, 캠퍼스의 밖으로 이동할 수는 없..
[프로그래머스] Lv.1 소수 찾기 [Python] 1~n 사이의 소수 개수 구하기 더보기 문제 설명 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. $($1은 소수가 아닙니다.$)$ 제한 조건 n은 2이상 1000000이하의 자연수입니다. https://school.programmers.co.kr/learn/courses/30/lessons/12921 에라토스테네스의 체를 이용해서 풀었습니다. 소수의 배수를 제거함으로써 소수만 남기는 방법 n의 제곱근 까지만 위 방법으로 체로 거르면 n까지의 소수를 모두 구할 수 있습니다. def solution(n): s = [0, 0] + [1] * (n-1) for i in range(2, int(n**...
[백준] 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인 무기를 ..

티스토리툴바