본문 바로가기
728x90
반응형

분류 전체보기229

[BOJ] 1003번 피보나치 함수 / 사용언어 : 파이썬(python) ※ 문제링크 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net ※ 관련개념 메모이제이션 - 위키백과, 우리 모두의 백과사전 메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하 ko.wikipedia.org 해당문제는 피보나치 함수의 성질을 이용하여 0와 1의 호출횟수를 출력하는 문제였다. 단순하게 피보나치 함수를 재귀함수로 구현하게 되면 시간초과가 발생할 것 같아 동적계획법 중 하나인 메모이제이션을 활용하기로 하였다. 간단하게 메모이제이션에 대해 설명하면 특정 함수.. 2021. 12. 22.
[BOJ] 2004번 조합 0의 개수 / 사용언어 : 파이썬(python) ※ 문제링크 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 해당 문제는 조합의 수를 구하는 공식을 활용해서 풀어야하는 문제였다. 팩토리얼을 쓰면 무조건 시간초과 또는 메모리 초과가 뜰 것으로 예상했기에 다른 방식으로 풀어야 한다고 생각했다. 처음에 생각한 방식은 곱해야하는 수들을 리스트로 받은 후 하나하나씩 2의 개수와 5의 개수를 세고 최솟값을 반환하여 나눠주는 것이었는데 해당 방식도 곱할 수들을 하나하나 모두 세어야 했기에 메모리 초과가 발생했다. 그래서 다른 방법을 고민해보던 중 해당 숫자를 2의 배수와 5의 배수로 나누어 주면 보다 간단하게 2의 지수의 개수와.. 2021. 12. 22.
[BOJ] 1676번 팩토리얼 0의 개수 / 사용언어 : 파이썬(python) ※ 문제링크 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해당문제는 팩토리얼을 사용하면 비교적 간단하게 풀 수 있는 문제였다. 수의 범위가 매우 작은 수준이었기에 팩토리얼 함수를 작성해서 풀어도 무방했으나 범위를 만약 늘렸다면 오버플로우 문제가 발생할 수도 있었기에 오버플로우 발생까지 고려하여 문제를 2가지 방법으로 풀어보았다. 문제를 푸는데 쓴 방법과 코드는 아래와 같다. 1번째 방법 1. 팩토리얼 값을 구할 함수를 작성한 후 값을 문자열 형태로 변환한다. 2. 변환한 문자열을 뒤에서부터 하나씩 확인하며 카운트한다. 2번째 방법 1. 팩토리얼 함수가 1부터 N까지의 값을 모두 곱한다는 성질.. 2021. 12. 22.
[BOJ] 11051번 이항 계수2 / 사용언어 : 파이썬(python) ※ 문제링크 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 해당 문제는 조합론과 스택오버플로우와 관련된 문제였다. 이항계수를 구하는 식을 재귀함수로 그대로 사용하게 되면 사용하는 숫자가 너무 커져서 완전히 다른 값을 반환하기에 중간에 숫자의 크기를 줄일 수 있게 약분을 해준 후 최종적으로 결과값을 산출해야 하는 문제였다. 문제를 해결한 방법과 코드는 아래와 같다. 1. 팩토리얼 함수를 만들때 결과값이 아닌 곱해야하는 값들을 리스트 값으로 만들어 반환하도록 한다. 2. 반환한 리스트 함수들을 반복문을 통해 공통 약수들은 모두 약분해준다. 3. n!이 k!(n-k)! [단, k 2021. 12. 21.
[BOJ] 3036번 링 / 사용언어 : 파이썬(python) ※ 문제링크 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net ※ 관련 개념 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 ko.wikipedia.org 이번 문제는 최소공약수를 통해 문제를 해결하는 문제였다. 문제를 풀기 위해서는 반지름으로 원의 둘레를 구하는 방법을 알아야했다. 원의 둘레는 반지름에 2를 곱하고 𝝅를 추가적으로.. 2021. 12. 21.
[BOJ] 2981번 검문 / 사용언어 : 파이썬(python) ※ 문제링크 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net ※ 관련 개념 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 ko.wikipedia.org 해당문제는 나머지정리와 유클리드 호제법을 사용해서 풀어야하는 문제였다. 처음에는 단순히 브루스포트방식으로도 풀 수 있지 않을까 해서 해당 방식으로 풀어봤는데 역.. 2021. 12. 20.
[BOJ] 2609번 최대공약수와 최소공배수 / 사용언어 : 파이썬(python) ※ 문제링크 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 해당문제는 두개의 수가 주어졌을때, 두 수의 최대공약수와 최소공배수를 구하는 문제였다. 문제를 해결하기 위해 최대공약수와 최소공배수의 성질을 이용했다. 예시) 18, 24 -> 18 = 2x3x3 / 24 = 2x2x2x3 -> lcm = 2x3(6) / gcf = 2x2x2x3x3(72) 자세한 문제풀이 방식은 아래와 같다. 1. 에라토스테네스의 체를 활용하여 10000이하의 소수리스트 생성 2. 소수리스트를 활용하여 두개의 숫자를 소인수 분해하여 리스트 생성 3. 리스트들을 합쳐서 소인수들을 확인하고 해당 소인수.. 2021. 12. 19.
[BOJ] 14889번 스타트와 링크 / 사용언어 : 파이썬(python) ※ 문제링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net ※ 관련 알고리즘 설명 [알고리즘] 백트래킹(Backtracking)이란? (feat. DFS, 기준함수, sum of subset) 백트래킹(Backtracing)의 개요 백트래킹은 구하고자 하는 해를 튜플로 나타내고 튜플에 기준 함수(한정 함수)를 적용했을 때의 결과가 최대치, 최소치 혹은 일정 조건을 만족하게끔 만들어주는 퇴 it00.tistory.com 해당문제는 DFS와 백트래킹을 활용하여 푸는 문제였다. 문제를 해결하기 위해 처음 떠올린 풀이방법은 아래와 같았다.. 2021. 12. 19.
[BOJ] 1037번 약수 / 사용언어 : 파이썬(python) ※ 문제링크 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 해당 문제는 약수를 통해 해당 값들을 약수로 가지는 수를 도출해내는 문제였다. 비교적 간단하게 풀 수 있는 문제로 약수 중 가장 작은 값과 가장 큰 값을 곱하면 해당 숫자를 구할 수 있는 성질을 이용하여 문제를 풀었고, 결과도 정상적으로 출력되는 것으로 확인하였으며, 해당 코드는 아래와 같다. N = int(input()) number_list = list(map(int, input().split())) maxValue = max(number.. 2021. 12. 19.
728x90
반응형

티스토리툴바