728x90 반응형 알고리즘115 [BOJ] 1149번 RGB거리 / 사용언어 : 파이썬(python) ※ 문제링크 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net ※ 관련개념 메모이제이션 - 위키백과, 우리 모두의 백과사전 메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하 ko.wikipedia.org 해당 문제는 메모이제이션과 배열을 이용하여 푸는 문제였다. 입력값을 저장할 배열을 생성한 뒤 2차원 리스트로 배열을 만들고 반복문을 작성하여 최.. 2021. 12. 23. [BOJ] 1932번 정수 삼각형 / 사용언어 : 파이썬(python) ※ 문제링크 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net ※ 관련개념 메모이제이션 - 위키백과, 우리 모두의 백과사전 메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하 ko.wikipedia.org 해당 문제는 메모이제이션과 피보나치수열의 개념을 응용해서 풀어야하는 문제였다. 각각의 정수 삼각형마다 피보나치를 적용하고 중간에 있는 값들은 최댓값을 구해서 반영하여 반복문을 돌려서 마지막 행까지 구한 다음, 최댓값을 출력하는 방식으로 문.. 2021. 12. 22. [BOJ] 9461번 파도반 수열 / 사용언어 : 파이썬(python) ※ 문제링크 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 해당 문제는 문제의 규칙을 이용하여 배열을 만들어 푸는 문제였다. 피보나치 수열과 비슷한 규칙을 가지고 있다고 문제에서 사전에 조건을 주었기에 비교적 쉽게 규칙을 발견할 수 있었다. 해당 문제의 규칙은 3까지는 1의 값을 가지다가 그 이상이 되면 N은 값이 N-3의 값과 N-2의 값을 더한 값이 되는 것이었다. 규칙을 알고나니 구현하는 것은 어렵지 않았다. 문제를 푸는 방법과 코드는 아래와 같다. 1. 입력값을 받고 그 길이 만큼 배열을 생성한다. 2. .. 2021. 12. 22. [BOJ] 1904번 타일 / 사용언어 : 파이썬(python) ※ 문제링크 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 해당 문제는 피보나치 수열을 사용해서 풀어야하는 문제였다. 그래서 처음에는 피보나치 수열 함수를 작성하고 메모이제이션 방식을 활용하여 풀어보았는데, 시간초과가 발생하여 코드를 보다 더 간단하게 작성해보았다. 추가적으로 해당문제는 범위가 크기때문에 문제에서 주어진 숫자인 15746으로 나누어서 값을 저장하지 않으면 오버플로우 문제가발생할 수 있다. 그러므로 반드시 값을 저장할 때는 원래값이 아닌 나머지 값들을 저장해주어야 했다. 문제를 푸는 데 사용한 방법.. 2021. 12. 22. [BOJ] 9184번 신나는 함수 실행 / 사용언어 : 파이썬(python) ※ 문제링크 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net ※ 관련개념 메모이제이션 - 위키백과, 우리 모두의 백과사전 메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하 ko.wikipedia.org 해당 문제는 메모이제이션을 사용하여 풀어야하는 문제였다. 개념만 알면 비교적 간단하게 풀수 있는 문제였다. 메모이제이션은 간단하게 재귀함수를 처음쓸때 호출했던 값들을 모.. 2021. 12. 22. [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. 이전 1 ··· 8 9 10 11 12 13 다음 728x90 반응형
