본문 바로가기

수학8

[백준 10837] 동전 게임 - python 💡문제 분석 요약영희와 동수는 동전 던지기 게임을 하고 있다. 이 게임은 K번 라운드로 구성되고 다음과 같은 규칙들을 따른다:한 라운드에서 영희와 동수는 한 번씩 동전을 던지고 항상 영희가 먼저 던진다.동전을 던져 앞면이 나오면 1점을 얻고, 뒷면이 나오면 점수를 얻지 못한다.한 명이 남은 기회에 모든 점수를 얻더라도 상대방이 현재까지 얻은 점수보다 작게 되면 게임 도중 어떤 시점에서도 게임은 바로 끝난다.0이상 K이하인 임의의 정수 M과 N에 대해서, 이것이 항상 게임이 끝난 후 영희와 동수가 얻는 점수가 되는 것은 아니다. 예를 들어서, K = 2인 경우에, M과 N의 모든 경우에 대해서, 이것이 영희와 동수가 얻는 점수가 될 수 있는 지의 여부는 다음 표와 같다:M N 영희, 동수의 점수가 될 가.. 2025. 1. 19.
[백준 15736] 청기 백기 - python 💡문제 분석 요약소프트웨어융합대학 학생회에서 주최한 소융체전에서 청기 백기 뒤집기 게임이 한창이다. 소프트웨어학부, ICT융합학부가 번갈아가면서 게임을 진행하는 중이다. 게임의 규칙은 간단하다. 게임을 진행할 차례인 학부에서 출전한 선수들 N명이 존재한다. 학생들의 앞 탁자에는 N개의 깃발이 청색이 위로 백색이 아래로 보이도록 놓여있다.이때 출전한 선수 중 첫 번째 선수는 N개의 깃발 중 1의 배수에 해당하는 번호의 깃발을 뒤집어 놓는다.다음 두 번째 선수는 N개의 깃발 중 2의 배수에 해당하는 번호의 깃발을 뒤집어 놓는다.i 번째 선수는 i의 배수에 해당하는 번호의 깃발을 뒤집고, N 번째 선수까지 진행하면 끝이 난다.그렇다면 이 게임에서 N 명의 선수가 참가하고 N개의 깃발이 존재할 때, N 번째 .. 2025. 1. 13.
[백준 15624] 피보나치 수 7 - python, js https://www.acmicpc.net/problem/15624💡문제 분석 요약피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 n이 주어진다. n은 1,000,000보다 작거나 같은 자연수 또는 0이다.출력첫째 줄에 n번째 피보나치 수를 1,000,000,007으로.. 2025. 1. 7.
[백준 20186] 수 고르기 - python, js https://www.acmicpc.net/problem/20186 💡문제 분석 요약N개의 자연수가 좌우로 배열되어 있다. 여러분은 이 중 K개를 골라야 한다. 고를 때는 K개 모두를 한번에 골라야 한다.여러분이 고른 수 각각에 대해서 그 수의 점수를 계산할 것이다. 점수는 자신의 수에서 자신의 왼쪽에 있는 수 중 선택된 수의 개수를 뺀 값이다. 이렇게 고른 수 각각에 그 점수를 계산한 후 전체점수는 계산된 점수들의 합이다. 여러분은 전체점수가 최대가 되도록 K개의 수를 골라야 한다.예를 들어서, N = 5개의 자연수가 순서대로 2 3 1 2 1 로 주어지고, K = 3이라고 하자. 만약 첫 번째 2와 두 개의 1을 골랐다면, 각 수의 점수를 계산해서 나열하면 2 0 −1과 같다. 따라서 전체 점수는 .. 2025. 1. 4.
[백준 13706번] 제곱근 - python, js https://www.acmicpc.net/problem/13706 💡문제 분석 요약문제정수 N이 주어졌을 때, N의 제곱근을 구하는 프로그램을 작성하시오.입력첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다.출력첫째 줄에 정수 N의 제곱근을 출력한다.💡알고리즘 설계N**(1/2) 와 같은 짧은 방법으로 해결된다면 좋았겠지만 아쉽게도 N이 800자리라 메모리 부족으로 런타임 에러가 발생하게 된다.이분 탐색을 사용해보자.left=0, right=Nmid=(left+right)//2if mid**2==N: print(mid)elif mid**2else: right=mid-1💡코드N = int(input())print(round(N**(1/2).. 2025. 1. 3.
[백준 26517] 연속인가? ? - python, js https://www.acmicpc.net/problem/26517💡문제 분석 요약💡알고리즘 설계ax+b == cx+d 일 경우 Yes와 f(x)를 출력한다.아닐 경우 No를 출력한다.함수의 연속성에 대한 설명함수 f(x)가 특정 점 x=t에서 연속이라는 것은 다음 세 가지 조건을 만족하는 경우를 의미한다.f(t)가 정의되어 있어야 한다.lim⁡x→tf(x)가 존재해야 한다.lim⁡x→tf(x)=f(t)이어야 한다.즉, x=t에서 함수값과 극한값이 모두 존재하며, 그 값이 서로 같을 때 f(x)는 x=t에서 연속이라고 한다. 예시 입력에서 k=2, a=6, b=2, c=5, d=4,일 때 그래프이다. 예시 입력에서 k=-7, a=-9 b=-6 c=-7 d=-8일 때, 함수의 비연속성을 보여주는 그래프.. 2025. 1. 2.
[백준 24313] 알고리즘 수업 - 점근적 표기 1 - python, js https://www.acmicpc.net/problem/24313 💡문제 분석 요약문제오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.입력첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. .. 2024. 12. 31.
[백준 1124번] 언더프라임 - 파이썬 https://www.acmicpc.net/problem/1697💡문제 분석 요약자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자.💡알고리즘 설계2부터 B+1 까지, 해당 숫자가 소수인지와 소수의 목록 길이를 배열에 저장한다.만약 이 소수의 목록 길이가 소수일 경우, answer에 1을 더한다.마지막에 answ.. 2024. 6. 1.

티스토리툴바