본문 바로가기

Baekjoon Algorithm/python46

[Python]BAEKJOON 1065번 한수 https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 문제 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다. 출력 첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. .. 2023. 2. 6.
[Python]BAEKJOON 1946번 신입사원 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지.. 2023. 1. 30.
[Python]BAEKJOON 9095번 1,2,3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 동적계획 알고리즘(Dynamic Programming(aka. DP))을 이용해서 푼다. 배열 d를 만들고, d[1]=1, d[2]=2, d[3]=4로 초기값을 설정한다. 3개나 초기값을 설정한 이유는 이 문제의 점화식이 다음과 같기 때문이다. d[i] = d[i-1]+d[i-2]+d[i-3] 이 점화식이 유도되는 과정은 아래 예시를 참고. i = 4일 때, d[4] = d[3]+d[2]+d[1] 4 = (3) + 1 d[3] = 4(개) (1+1+1)+1 (3)+1 (2+1)+1 (1+2)+1.. 2023. 1. 27.
[Python]BAEKJOON 2012번 등수 매기기 https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 입력 받은 값을 순차적으로 정렬시킨후, 1,2,3,4,...N-1,N값과의 차이의 절댓값을 모두 합한 값이 불만도 합의 최솟값이다. Sol1 -552ms 227B import sys input = sys.stdin.readline N = int(input()) lst = [];lst2 = [i for i in range(1,N+1)];res = [] for i in range(N):lst.append(i.. 2023. 1. 26.
[Python]BAEKJOON 1025번 제곱수 찾기 https://www.acmicpc.net/problem/1025 1025번: 제곱수 찾기 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지 www.acmicpc.net 기본 아이디어는 부르트 포스(brute force) 완전탐색이다. 아래 코드에서 rowt와 colt는 각각 행 공차, 열 공차다. (공차가 영어로 tolerance) 4중 for문으로 구현했는데, 이래도 시간초과 나지 않는 까닭은, 입력값 1 ≤ N, M ≤ 9로 제한되었기 때문이다. 시간복잡도가 최악의 경우(행과 열이 모두 n=9인 정방행렬) n^4이라고 해도, 9^4 = 6561에 그.. 2023. 1. 26.
[Python]BAEKJOON 9372번 상근이의 여행 sol1 (164ms) import sys input = sys.stdin.readline for i in range(int(input())): N,M = map(int,input().split()) for j in range(M): lst = list(map(int,(input().split()))) print(N-1) sol2 (56ms) import sys input = sys.stdin.readline for i in range(int(input())): N,M = map(int,input().split()) for j in range(M): input() # 이 부분만 수정. 어차피 이 값은 받아도 쓸모 없음 print(N-1) 2023. 1. 20.
[Python]BAEKJOON 1110번 더하기 사이클 문제 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자. 26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다. 위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다. N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 .. 2023. 1. 18.
[Python]BAEKJOON 3003번 '킹, 퀸, 룩, 비숍, 나이트, 폰' 문제 동혁이는 오래된 창고를 뒤지다가 낡은 체스판과 피스를 발견했다. 체스판의 먼지를 털어내고 걸레로 닦으니 그럭저럭 쓸만한 체스판이 되었다. 하지만, 검정색 피스는 모두 있었으나, 흰색 피스는 개수가 올바르지 않았다. 체스는 총 16개의 피스를 사용하며, 킹 1개, 퀸 1개, 룩 2개, 비숍 2개, 나이트 2개, 폰 8개로 구성되어 있다. 동혁이가 발견한 흰색 피스의 개수가 주어졌을 때, 몇 개를 더하거나 빼야 올바른 세트가 되는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 동혁이가 찾은 흰색 킹, 퀸, 룩, 비숍, 나이트, 폰의 개수가 주어진다. 이 값은 0보다 크거나 같고 10보다 작거나 같은 정수이다. 출력 첫째 줄에 입력에서 주어진 순서대로 몇 개의 피스를 더하거나 빼야 되는지를 출력한다. .. 2023. 1. 16.
[Python]BAEKJOON 11021번 A+B - 7 https://www.acmicpc.net/problem/11021 11021번: A+B - 7 각 테스트 케이스마다 "Case #x: "를 출력한 다음, A+B를 출력한다. 테스트 케이스 번호는 1부터 시작한다. www.acmicpc.net 매일 한문제씩 풀고 있는데, 오늘은 정말 백준할 시간이 안나서(내일 머신러닝 세미나 발표가 있어서 준비해야했다.. 그리고 기도회있어서 교회갔다 왔다..) 10초컷 문제풀고 가져왔다. 문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (0 < A, B < 10) 출력 각 테스트 케이스마다 "Case #x: .. 2023. 1. 14.

티스토리툴바