아이테킨의 끄적끄적

이 문제를 풀때의 아이디어는 나머지의 크기에 따라서 답이 달라진다는 것이다. 나머지가 연속으로 사용할 수 있는 기간(L)과 비교해서 큰 경우와 작은경우 케이스별로 처리하면 된다. 사실, 그냥 생각나는대로 풀어보았는데 운좋게 한번에 맞았다. 어떻게 이렇게 풀게 되었는지 설명하기가 애매한 듯 싶다. 이게 그리디 문제의 특징이 아닌가 싶다...? 라는 개인적인 생각.. 크흠... # 4796 캠핑 case = 0 while True: case += 1 L, P, V = map(int, input().split()) if (L + P + V) == 0: break remainder = V%P if V%P

이번 블로그는 파이썬을 이용해서 힙 자료구조를 이용하는 방법을 정리해보고자 한다. 일단 힙(heap)은 우선순위 큐를 만들때 이용하면 좋다. [자료구조] 먼저 알아야한 자료구조들에 대해서 간단하게 정리해보자! - 스택(LIFO : Last In First Out) : 자료가 들어오는 순서대로 위로 쌓인다고 생각하면 됨 - 큐(FIFO : First In First Out) : 자료가 들어오는 순서대로 영화관 줄 처럼 줄을 서 있는다고 생각하면 됨. - 우선순위 큐(Priority Queue) : 들어온 순서에 상관없이 우선순위에 따라 데이터가 처리되는 자료구조. : 힙(heap)자료구조로 구현할 수 있다. 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 이중에서 힙(heap)으로 구현하는 것이..

우선순위 큐의 힙 자료구조를 이용하면 문제를 풀 수 있다. 처음에 이 문제를 풀 때 '힙(heap)'이라는 자료구조를 생각해내지 못해서 한참을 헤맸다. 이 문제를 풀때 가장 중요한 아이디어는 힙(heap)이라는 생각이다. 알고리즘은 이러하다. 0) 총 비교한 횟수(answer)를 0으로 둔다. 1) 현재의카드 묶음(card_deck) 중 가장 작은 2개의 카드 묶음을 꺼낸다. 2) 두 개를 더한 값 = 현재 단계에서 비교한 횟수 3) 두 개를 더한 값을 총 비교한 횟수(answer)에 더해준다. 4) 두 개를 더한 값을 다시 카드 더미(card_deck) 안에 넣는다. 5) 1 ~ 4 과정을 힙에 하나의 덱만 남을 때 까지 반복한다. (참고. https://claude-u.tistory.com/341) ..

30의 배수 중 가장 큰 수를 찾아서 출력해내는 문제이다. 위키피디아에 배수 판정법이라는 것을 알게되었다. https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%88%98_%ED%8C%90%EC%A0%95%EB%B2%95 배수 판정법 - 위키백과, 우리 모두의 백과사전 배수 판정법은 배수인지 확인하려는 수의 배수가 맞는지 간단히 확인하는 것이다. 배수인지 확인하려는 수가 클 때에는 나눗셈을 이용하여 계산하는데 시간도 오래 걸리고 틀린 답이 나올 수 ko.wikipedia.org 결국 문제는 30의 배수인지 확인하는 것이기 때문에 위키피디아에서 나온 개념을 적용하면 될 것 같다. 3의 배수는 각 자리 숫자의 합이 3의 배수인 수이다. 30의 배수는 3의 배수이면서 일의 자리가 0인 ..

오랜만에 코딩테스트 문제를 다시 풀어보았다. 곱셈의 값들이 각각 가장 작게 되도록 만드는 방법을 생각하는 것이었다. 가장 큰 값에 가장 작게 곱셈을 해줄때 최종 합이 가장 작을것이라는 아이디어로 풀어보았다. 각 리스트를 정방향, 역방향으로 정렬한 후에 excel에서 쓴 sumproduct를 구현해보았다. [x*y for (x,y) in zip(list_1,list_2)] 이 부분이 sumproduct인데 알아두면 두고두고 유용하게 써먹을 코드가 될 것 같다. # 1026 보물 n = int(input()) # 각 데이터를 공백으로 구분하여 입력값을 받는다. list_1 = list(map(int, input().split())) list_2 = list(map(int, input().split())) l..

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거리 #..