지금은마라톤중

해당 문제는 DP 문제입니다. 접근법- 규칙성 찾기- 점화식 형태 구현- 조건을 만족하려면 100, 101 형태를 지켜야함. 1 : 12: 103 : 100, 1014 : 1000, 1001, 10105 : 10000, 10001, 10010, 10100, 10101→ 점화식 : dp[i] = dp[i-1] + dp[i-2]  n = int(input())dp = [0] *(n+1)dp[1] = 1for i in range(2,n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n])

해당 문제는 DP 문제 입니다. 접근법- 작은 문제로 나눴을 때 이번 값을 중복해서 사용할 수 있음- 메모리제이션 활용- 이전 dp를 활용하여 값 계산- 3과 2로 나누어 떨어질 경우 : 최솟값 계산      1) 이전 dp 활용      2) 3과 2로 나누어지는 dp 활용 연산 조건를 한번 더 생각해 볼 필요가 있었습니다.연산 조건의 우선순위를 다시 생각해봤으면 좀 더 빠른 풀이가 가능했을 것 같습니다. x = int(input())dp = [0] * (x+1)def func_dp(n): for i in range(2,n+1): dp[i] = dp[i-1] + 1 if i % 3 ==0: dp[i] = min(dp[i], dp[i//3]..

사실 이 문제를 계기로 DP를 먼저 공부하기로 마음 먹었던 것입니다. 풀다가 6개 실패했습니다..알고보니 DP 알고리즘으로 푸는 문제였습니다. ㅎㅎ 그래서 지난 포스팅에서 DP를 푸는 이론을 먼저 공부하고 다시 도전하게 되었습니다. 접근법 - DP - 최댓값을 가지게 하는 방법 - 1,2번 계산을 무조건 밟는다 - 3번 계산부터 마지막 계산까지는 1칸 or 2칸을 이동 - i 번째 칸 일때 가능한 경우는 1) i-2칸에서 오는 경우와 2) i-3칸에서 i-1로 이동하여 오는 경우 *3칸을 연속해서 이동하지 못하는 점 고려 n = int(input()) scores = [0] scores += [int(input()) for _ in range(n)] dp = [0 for _ in range(n+1)] d..

이 문제는 2가지 풀이법으로 해결했습니다. 1. 조합 2. DP 1. 조합 문제를 봤을 때 가장 직관적으로 생각났습니다. # 조합으로 풀기 def fac(a): num = 1 for i in range(1,a+1): num *= i return num t = int(input()) for _ in range(t): n,m = map(int,input().split()) res = fac(m)//(fac(n)*fac(m-n)) print(res) 2. DP DP 문제를 풀어보려고 DP 문제 목록에서 골랐기 때문에 DP인걸 알 수 있었습니다. 하지만 문제만 보고 DP라는걸 알아차리는 것이 쉽지 않은 것 같습니다..ㅎㅎ 위 그림처럼 경우의 수가 규칙성을 가졌습니다. 그래서 작은문제로 쪼개어 해결할 수 있었습니..

이번에는 DP(Dynamic Programming, 동적 계획법)에 대해 공부해봤습니다. 원래 BFS와 DFS를 했으니 다른 그래프 이론들을 공부하려다가 코테에 잘 나오는거 먼저 하자!! 해서 순서가 좀 바뀌었습니다 ㅎㅎ DP(Dynamic Programming, 동적 계획법) : 복잡한 문제를 효율적으로 해결하기 위한 알고리즘 설계 기법 중 하나입니다. 이 방법은 주로 최적화 문제를 해결하는 데 사용되며, 큰 문제를 작은 부분 문제로 나누어 해결한 후, 그 결과를 저장해두고 필요할 때 다시 사용(메모이제이션)함으로써 계산의 중복을 피하는 것이 핵심 전략입니다. 동적 계획법은 문제를 분할하여 각각의 작은 문제들을 한 번씩만 풀어 큰 문제의 해답을 구하는 방식으로, 불필요한 계산을 줄이고 효율성을 높입니다..

이번 문제에서는 런타임 에러와 시간초과로 2번 실패했었습니다. 접근법 - DFS로 접근 - 깊이 탐색 후 방문하지 않은 노드 있을 때 cnt 증가 에러해결 1. 런타임에러 - 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회 → 재귀 최대깊이는 재설정해줌 sys.setrecursionlimit(10000) 2. 시간초과 - input 대신 sys.stdin.readline을 통해 시간초과 해결 input = sys.stdin.readline import sys input = sys.stdin.readline sys.setrecursionlimit(10000) n,m = map(int,input().split()) graph = [[] for _ in range(n+1)] for _ in range(m)..

컴파일러 언어 컴파일러는 고급언어를 저급 언어로 변환하는 것입니다. 고급언어는 사람이 이해하기 쉽도록 작성된 프로그래밍 언어로 C,C++,JAVA 등이 있습니다. 저급언어은 컴퓨터 내부에서 바로 처리가 가능한 프로그래밍 언어로 기계어와 어셈블리어 등이 있습니다. 컴파일 단계와 실행 단계가 분리되어 있어, 실행시에는 컴파일하지 않고 실행만 하면 되어 실행 속도가 빠릅니다. - 종류 : C, C++, C#, JAVA 인터프리터 언어 인터프리터는 프로그래밍 언어의 소스 코드를 바로 실행하는 프로그램입니다. 인터프리터 언어는 컴파일 하지 않고 소스 코드를 한줄씩 읽어들여 실행합니다. 빌드 과정을 거치지 않아, 별도의 실행 파일이 존재하지 않고 코드 수정에 용이하다는 장점이 있습니다. 컴파일 과정이 없기 때문에 ..

이 문제 역시 그래프 탐색 문제입니다. 접근법 - DFS로 접근 - DFS로 탐색하면서 cnt를 증가하여 단지 내 건물 수 체크 - 건물 수 담은 리스트 활용하여 결과 출력 n = int(input()) matrix = [] visited = [[False] * n for _ in range(n)] cnt_list = [] dx = [0,0,1,-1] dy = [1,-1,0,0] # mapping matrix for _ in range(n): m = input() matrix.append(m) def dfs(matrix,x,y,visited): global cnt if x = n or y = n : return 0 if matrix[y][x] == "0" or visi..