아이테킨의 끄적끄적

3줄 요약. 1. (정의) - 확률에 관하여서 사전확률과 사후확률 사이의 관계를 나타내는 정리이다. 2. (의의) - 사전확률을 계속해서 갱신(update)할 수 있다는 굉장히 큰 의미가 있다. 3. (활용) - 넷플릭스 추천 알고리즘, 암진단 확률, 베이즈정리에 관해 수식이나 어려운 용어들을 사용해서 설명ㅎ 베이즈 정리와 관련하여 여러가지 자 료를 본 결과 베이즈정리의 가장 중요한 포인트는 한다는 것이다. 내가 알고자 하는 확률에 대해서 계속해서 갱신하면서 의사결정을 할 때 더 큰 확신을 줄 수 있다. 이것이 무슨 의미인지 간단한 사례 두가지를 통해서 느껴보자. 1. 어떤 이성이 나에게 선물을 주었다. 이것은 그린라이트일까?? 학교에서 어떤 이성이 나에게 선물을 주었다고 생각해보자. 이때 진짜로 나에게..

점화식 $$ a_n = min(a_{n/3}+1, a_{n/2}+1, a_{n-1}+1) $$ 코드 # 1463 - 1로 만들기 n = int(input()) dp = [0] * (n+1) for i in range(2,n+1): dp[i] = dp[i-1]+1 if i%3 == 0: dp[i] = min(dp[i//3]+1, dp[i]) if i%2 == 0: dp[i] = min(dp[i//2]+1, dp[i]) print(dp[n])

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제의 조건은 세가지다. 1. 연속된 세개의 계단을 밟으면 안됨 2. 마지막 계단은 밟아야함 3. 한칸 또는 두칸씩 이동 가능함. 마지막 계단은 밟아야하므로 i번째 계단이라고 한다면 max(i-2번째 계단을 밟고 두칸을 뛰어 i번째로 온 경우, i-3번째 계단을 밟고 i-1번째를 밟고 i번째로 온 경우) 이런식으로 점화식을 만들면 된다. 코드 # 2579 - 계단 오르기 n = int(input()) step..

역시나 DP문제이므로 처음엔 점화식을 구해보려고 생각해보았다. 그러나 이전처럼 뭔가 깔끔하고 정리가 딱 되는 점화식이 생각나지 않아서 각 층마다의 최대값을 모두 구하는 방식으로 문제를 풀었다. 각 층의 첫번째 값과 마지막 값은 바로 직전 층의 값을 그대로 더해주면 되었고 그 이외의 값들은 위에 층의 더해질 수 있는 두가지 값 중 큰 값을 더해주는 방식으로 풀었다. 코드 # 1932 - 정수삼각형 # 아이디어는 각 층마다 최대값을 다 구한뒤 최대값을 찾아서 출력한다 import sys input = sys.stdin.readline n = int(input()) triangle = [] for _ in range(n): triangle.append(list(map(int,input().split()))) ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP문제를 계속해서 풀면서 느끼는점은 결국 점화식을 생각해내는 것이 핵심 포인트인것 같다. 문제를 어떻게 쪼개고 반복해서 연산한다음 합칠것인지 충분히 고민하고 문제를 푸는게 오히려 더 빠르고 정확하다는 생각이 든다. 점화식 i번째에 빨강을 칠할 때 최소값 = i번째 빨강의 비용 + min(i-1번째 파랑의 최소값, i-1번째 초록의 최소값) 코드 # 1149 - RGB거리 #..

이 문제도 점화식을 구하면 쉽게 풀 수 있는 문제다 그림을 유심히 살펴보거나 혹은 결과들을 유심히 살펴보면 숫자들간에 규칙이 있는것을 발견할 수 있다. (사실 다른 더 논리적이고 멋있는 해설이 있기야 하겠지만 나는 이렇게 풀었다...;;) 점화식 $$ a_n = a_{n-5} + a_{n-1} $$ 코드 # 9461번 - 파도반 수열 import sys input = sys.stdin.readline t = int(input()) for _ in range(t): dp = [0] * 101 dp[1] = 1 dp[2] = 1 dp[3] = 1 dp[4] = 2 dp[5] = 2 n = int(input()) for i in range(6,n+1): dp[i] = dp[i-5] + dp[i-1] print..

일단 이 문제는 점화식으로 표현할 수 있다면 쉽게 풀 수 있는 문제다. $$A_n = A_{n-1} + A_{n-2}$$ 처음 1,2 까지의 값만 다른 피보나치 수열이다. 점화식을 알았으니 반복문 또는 재귀함수를 이용해서 풇어주면 된다. 반복문을 이용해서 풀어보았다. # 1904번 - 01타일 # 반복문을 이용해서 - 바텀업 import sys input = sys.stdin.readline n = int(input()) tile_list = [0]*(n+1) tile_list[1] = 1 tile_list[2] = 2 for i in range(3,n+1): tile_list[i] = (tile_list[i-1] + tile_list[i-2])%15746 print(tile_list[n]) 이때 주의해..

메모이제이션을 이용해서 풀어야 하는 DP 문제다. 3차원 리스트를 이용하면 쉽게 풀 수 있다. # 9184 - 신나는 함수 실행 dp = [[[0]*21 for _ in range(21)] for __ in range(21)] def w(a, b, c) : print(dp) if a20 : return w(20, 20, 20) if dp[a][b][c]: return dp[a][b][c] if a

피보나치 함수를 구하는 문제이다 보통 피보나치 수열은 재귀함수를 이용해서 구할 수 있다. def fibo(x): if x == 1 or x == 2: return 1 else: return fibo(x-1) + fibo(x-2) 이런 식으로 구할 수 있는데 문제는 숫자가 조금만 커지게되면 연산횟수가 급격하게 증가하고 그에 따라서 속도도 엄청 느려지게 된다. 이런 문제를 메모이제이션(재귀함수이용) 또는 반복문을 이용해서 해결할 수 있다. 메모이제이션은 이미 한번 연산을 했던 값은 따로 저장해뒀다가 필요할때마다 찾아서 쓴다는 아이디어다. 말 그대로 따로 메모해둔다고 생각하면 된다. 반복문을 이용하는 방법은 작은 문제부터 하나하나씩 풀어나가는 방법이다. 결론적으로는 선형시간의 시간복잡도를 갖는다. 코드로 살펴..

통계학에서 주로 사용되는 개념들을 직접 구현해보라고 만든 문제인 것 같다. 산술평균이나, 중앙값, 범위 구하는 문제는 max,min,sum,등등 파이썬 내장함수를 이용하면 어렵지 않게 구할 수 있는 문제다. 특별히 최빈값을 구할때 collections 모듈에서 Counter클래스 썻다. 코딩테스트에서는 다른 라이브러리를 불러오지 못하게 하는 경우도 있다고 들어서 이런 모듈을 불러와서 문제를 풀어도 될지에 대해서 불안하지만 Counter함수에 대해서 공부도 할겸 구글링하면서 풀어보았다. 여기에 counter에 대한 documentation이 있다. https://docs.python.org/ko/3/library/collections.html#collections.Counter collections — 컨..