본문 바로가기
728x90
반응형

파이썬438

[백준] 11659번 : 구간 합 구하기 4 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 1. 문제 설명 2. 풀이과정 문제에서 수의 개수와 합을 구해야 하는 횟수는 최대 100,000이다. 게다가 구간마다 합을 매번 계산하면 0.5초 안에 모든 구간 합 계산을 끝낼 수 없다. 하여 구간 합을 이용해 문제를 해결한다. N개의 수를 입력받음과 동시에 합 배열을 생성한다. S[i] = S[i - 1] + A[i] 구간 i ~ j가 주어지면 구간 합을 구하는 공식으로 정답을 출력한다. S[j] - S[i - 1] 슈도코드 N(숫자 개.. 2024. 1. 4.
[백준] 1546번 : 평균 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net 1. 문제 설명 2. 풀이과정 최고 점수를 기준으로 전체 점수를 다시 계산해야 하므로 모든 점수를 입력받은 후에 최고점을 별도로 저장해야 한다. 또한 문제에서 제시한 한 과목의 점수를 계산하는 식은 총합과 관련된 식으로 변환할 수 있다. A, B, C 점수에 대해 변환 점수의 평균을 구하는 식 (A / M * 100 + B / M * 100 + C / M * 100) / 3 = (A + B + C) * 100 / M / 3 = 총합 * 100 / 최댓값 /.. 2024. 1. 4.
[백준] 11720 : 숫자의 합 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 파이썬의 리스트 자료구조를 통해 쉽게 해결할 수 있다. 입력으로 주어지는 숫자를 문자열로 입력받아 리스트의 형태로 저장한다. 저장 후, 해당 리스트의 각 원소를 하나씩 불러와 문자형을 정수형으로 변환해 모든 자릿수의 값을 더한다. 숫자의 개수만큼 입력받은 값을 리스트 형태로 저장한다. numbers 리스트를 탐색하며 각 값을 정수형으로 젼환하여 결과에 누적으로 더한다. 슈도코드 n값 받기 numbers 변수에 list 함수를 이용하여 숫자를 한 자리씩 나누어 받기 sum 변수 선언 및 초기화 for nu.. 2024. 1. 3.
[백준] 9251번 : LCS - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 두 문자열의 부분 수열 중 가장 긴 부분 수열의 길이를 구하는 문제이다. 각 문자열을 2차원 리스트로 고려하여 해당 문자열까지 가장 긴 부분 수열의 길이를 저장해 나간다. 2차원 리스트는 각 문자열의 길이보다 1씩 크게 만들어 제일 앞에는 문자열을 빼는 경우를 생각한다. 초기 2차원 리스트는 위 배열처럼 나타낼 수 있다. [1][1] 위치에서부터 시작하여 마지막 칸까지 가장 .. 2023. 12. 29.
[백준] 2565번 : 전깃줄 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 전깃줄이 교차하지 않도록 하기 위해 제거해야 하는 전깃줄의 최소 개수를 구하는 문제이다. 전깃줄은 A 전봇대에서 B 전봇대로 연결되기 때문에 교차하지 않으려면 연결된 전깃줄을 전깃줄의 B 전봇대 번호를 기준으로 오름차순 정렬하고, 이후 전깃줄을 차례대로 이전 전깃줄과 비교하여 교차되는지 안되는지 확인하면 된다. 처음부터 비교할 전깃줄 전까지 비교하며 만약 이전 전깃줄의 B 전봇대 번호가 더 작으면 해당 두 전깃줄은 서로 공존할.. 2023. 12. 28.
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 부분 수열 중 가장 긴 바이토닉 수열의 길이를 찾는 문제이다. 해당 문제는 이전의 백준 11053번 : 가장 긴 증가하는 부분 수열 문제를 응용하면 쉽게 해결할 수 있는 문제이다. DP 알고리즘을 활용하여 처음부터 끝까지 부분 수열 중 앞의 수보다 크면 1씩 해당 위치의 값을 증가하면서 각 위치별로 증가하는 부분 수열의 길이를 알 수 있다. 이를 거꾸로 생각하면 가장 긴 감소하는 부분 수열을 찾을 수 있다. 두 부분 수열의 길이를 위치별로 .. 2023. 12. 27.
[백준] 1904번 : 01타일 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 길이를 입력받아 가능한 모든 2진 수열의 개수를 구하는 문제이다. 길이가 1일 때는 1가지, 2일 때는 2가지의 경우가 나온다. 해당 경우를 구하다 보면 각 경우의 수는 앞선 결과 2개를 더한 값이라는 것을 알게 된다. 0, 1, 2, 3, 5, 8, 13, 21,... 여기에서 해당 결과를 15746으로 나눈 값을 저장한다. 이를 활용해 원하는 길이까지의 경우를 저장하며 마지막으로 해당 길이의 경우의 수를 출력하면 된다. .. 2023. 12. 26.
[백준] 9184번 : 신나는 함수 실행 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 -50부터 50까지 범위에서 3개의 수를 입력받아 w(a, b, c)의 값을 출력하는 문제이다. 문제에 나와있는 함수를 사용하면 재귀를 활용해 해당 값을 계산하므로 값에 따라 많은 시간이 소요될 수 있다. 하여 이미 구한 값을 저장하고 그 값을 사용하는 DP 알고리즘을 활용해 문제를 해결하고자 했다. 또한 해당 문제는 -50부터 50까지의 범위의 수를 입력받을 수 있는데 3개의 수 중 하나라도 0 이하이면 해당 결과는 1이.. 2023. 12. 24.
[백준] 14889번 : 스타트와 링크 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 14889번: 스타트와 링크예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.www.acmicpc.net 1. 문제 설명2. 풀이과정해당 문제는 모든 인원을 정확하게 두 팀으로 나누고 나눈 두 팀의 능력치를 계산하여 그 차이의 최솟값을 구하는 문제이다.팀을 정확하게 두 팀으로 나누어야 하고, 나눈 두 팀에 대해 각 능력치를 구한 뒤, 두 팀의 능력치의 차이를 계산해야 한다. 계산한 능력치의 차이 중 최솟값을 구하면 된다.하여 제일 앞사람부터 첫 번째 팀으로 이동하며 팀을 나눈다.만약 첫 번째 팀의 인원이 전체 인원의 절반이 되면, 남은 사람들은 모두 두 번째 팀이 된다.두 팀으로 나누어졌으면.. 2023. 12. 23.
[백준] 24416번 : 알고리즘 수업 - 피보나치 수 1 - 우당탕탕 개발자 되기 프로젝트 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 1. 문제 설명 2. 풀이과정 처음에 문제를 아래의 코드처럼 풀었다. 문제에 있는 두 함수를 그대로 사용하면서 각 함수가 호출되는 횟수를 구하는 방식으로 문제를 해결하였으나, 시간 초과가 발생하였다. import sys def fib(n): global cnt1 if (n == 1 or n == 2): cnt1 += 1 return 1 else: return (fib(n - 1) + fib(n - 2)) def fibonacci(n): global .. 2023. 12. 22.
728x90
반응형

티스토리툴바