문제 코드 def solution(N, number): if N == number: return 1 answer = -1 arr = [set() for _ in range(8)] for i in range(len(arr)): arr[i].add(int(str(N)*(i+1))) for i in range(1,8): for j in range(i): for op1 in arr[j]: for op2 in arr[i-j-1]: arr[i].add(op1+op2) arr[i].add(op1-op2) arr[i].add(op1*op2) if op2 != 0: arr[i].add(op1//op2) if number in arr[i]: answer = i+1 break return answer 풀이방법 이 문제는 동..

이 문제는 얼핏하면 dfs, bfs처럼 보여서 나도 처음에는 dfs로만 구현을 했었다. 하지만 dfs로 구현하면 값이 커질수록 반복되는 구간이 증가하기때문에 당연히 시간초과가 났었고 이를 고치기 위해 dp를 이용한 방법을 추가시켰다. 처음에는 dp를 어떻게 적용해야하는지가 감이 안와서 주변 친구들에게 도움을 받아서 이해를 하게 되었다. 이 문제를 시작점에서부터 도착점으로 가는 경로의 수를 구하는 문제에서, 임의의 점(x, y)에서 도착점 까지의 경우로 세분화 하여 구한다면, 그 어떤 경로로 (x, y)에 도착 하기만 해도 그 때부터의 경우의 수는 다시 구할 필요가 없다. 이 관점으로 코드를 구현해보자. 우선 처음에 dfs만 구현해서 시간초과가 난 코드이다. from sys import stdin as s..

💡그리디 알고리즘이란? 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다. 그리디 해법은 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지를 검토합니다. 그리디 알고리즘 예시 문제 - 문제 : 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. - 입력 : N = 1260 - 풀이 : 가장 큰 화폐 단위부터 돈을 거슬러 주는 식으로 풀이합니다. 먼저..

💡다이나믹 프로그래밍(DP)란? - 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상하는 방법입니다. - 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. - 다이나믹 프로그맹의 구현은 일반적으로 두 가지 방식(Top Down, Bottom Up)으로 구성됩니다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다. 2. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 합니다. 다이나믹 프로그래밍 예시 - 피보나치 수열 n번째 피보나치 수를 f(n)라고 할 ..