https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 풀이 문제에 따르면 우리는 생성자를 이용하여 분해합을 나타낼 수 있습니다. 예를들어 생성자 123이 주어진다면 우린 129(123 + 1 + 2 + 3)라는 분해합을 얻을 수 있습니다. 생성자는 분해합보다 항상 같거나 작습니다. for문을 이용해서 0부터 분해합까지 모든 수를 생성자로 취급하여 분해합을 구해봅니다. 찾고자하는 분해합을 찾게되면 우린 생성자를 찾을 수 있..

https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 풀이 본문의 글자 수를 보고 지레 겁먹지않으면 됩니다. 본문 내용을 요약하자면 알파벳 [a, b, c, d ..... x, y, z] = [1, 2, 3, 4 .....24, 25, 26] 으로 바꾸어줄 수 있습니다. 소문자로만 이루어진 문자열의 알파벳을 문자단위로 위와 같은 정수로 바꾸어준뒤 문자열의 인덱스 값만큼 31을 제곱해준뒤 곱해줍니다. 이렇게 일련의 과정을 거친 숫자들을 모두 합친 뒤..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 전제 조건. 1, "익은" 토마토가 존재한다면 창고에서 1로 표현된다. 2, "익지않은" 토마토가 존재한다면 창고에서 0으로 표현된다. 3, 창고 안에는 벽이 존재하는데 이 벽은 인접한 토마토가 익지않게 막는다. 창고에서 -1로 표현된다. 목표: 창고안에 존재하는 토마토가 전부 익을 수 있다면 익게되는데 걸리는 최소 일 수를 출력한다. 만일 창고 안의 모든 토마토가 익지 못한..

https://www.acmicpc.net/problem/3003 3003번: 킹, 퀸, 룩, 비숍, 나이트, 폰 첫째 줄에 동혁이가 찾은 흰색 킹, 퀸, 룩, 비숍, 나이트, 폰의 개수가 주어진다. 이 값은 0보다 크거나 같고 10보다 작거나 같은 정수이다. www.acmicpc.net 풀이 단순 구현 문제이기에 문제를 풀어주시면 됩니다. # 3003번 킹, 퀸, 룩, 비숍, 나이트, 폰 n = list(map(int, input().split())) # 원래 필요한 말의 개수. right_nums = [1, 1, 2, 2, 2, 8] # 입력과 필요한 말의 개수를 비교해준다. for i in range(6): print(right_nums[i] - n[i], end=" ") 출력결과

순열과 조합을 재귀함수를 통해 구현하는 방법과 라이브러리를 통해 구현하는 방법으로 나누어서 설명해보겠습니다. 1. 순열(Permutation) 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다. 1-1. 재귀함수 # 개수가 5개인 리스트 [1, 2, 3, 4, 5] 주어졌을 때 중복없이 순서있게 3개를 뽑아보자. # 순열 사용. # 주어진 숫자들 nums = [1, 2, 3, 4, 5] # 3개를 뽑는다. r = 3 # 순열을 만드는 테이블 ans = [] # 중복을 확인할 리스트 visited = [False] * (max(nums)+1) def print_args(): print(" ".join(map(str, ans))) ..

https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 풀이 다이나믹 프로그래밍을 위해 dp테이블을 생성하여 문제를 풀어줍니다. # 16395 파스칼의 삼각형 n, m = map(int, input().split()) s = [[1 for _ in range(i)] for i in range(1, 31)] for i in range(2, 30): for j in range(1, i): s[i][j] = s[i-1][j-1] + s[i-1]..

https://www.acmicpc.net/problem/15624 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 피보나치 수 문제입니다. 이전 문제들과 차이가 있다면 메모리 제한이 주어진 입력값에 비해서 작기에 DP테이블을 사용하지않고 for문안에서 변수 2개를 이용해서 계산에 필요한 수만 저장해놓는 방법으로 풀어주었습니다. # 15624번 피보나치 수 7 n = int(input()) a = 0 # i-2 자리 b = 1 # i-1 자리 if n == 0: print(0) else: for _ in range(2, n+1): a %= 1000000007 b %= 1000000007 a, b = b,..

https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 풀이 실행횟수를 출력해주는 문제입니다. 다만 시간 초과를 방지하기 위해 PyPy3으로 제출해주시길 바랍니다. # 24416번 알고리즘 수업 - 피보나치 수 1 k = int(input()) ans_1 = 0 ans_2 = 0 def fib(n): global ans_1 ans_1 += 1 if (n == 1 or n == 2): return 1; else: return (fib(n ..