지금은마라톤중

1. 탐욕적(Greedy) 알고리즘이란?Greedy는 “탐욕스러운, 욕심 많은”이란 뜻을 가진 용어로, 바로 눈앞의 이익만 쫓는 알고리즘을 말합니다.최적화 문제를 대상으로 하며, 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼습니다.  2. 그리디 알고리즘의 2가지 조건탐욕 선택 속성탐욕 선택 속성이란 앞의 선택이 이후 선택에 영향을 주지 않는 것을 말합니다. 즉, 선택을 다시 고려하지 않습니다.최적 부분 구조최적 부분 구조란 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말합니다. 3. 그리디 vs 다이나믹 프로그래밍(DP)두 알고리즘은 흔히 비교되는데, 서로 풀 수 있는 문제의 성격이 다..

이제 그리디 문제를 풀어볼까 합니다. 접근법- 최소시간을 구하는 문제- 조건에 맞게 분기- 공통 좌표값과 여분 좌표값  ex) (x,y) = (2,5) → 공통 좌표값 : 2 , 여분 좌표값 : 3- 비교1 : 대각선 이동 vs 한 블록 이동 *2 -> 공통 좌표값 이동 시 - 비교2: 대각선이동 vs 한 블록 이동 → 공통 좌표값 외 여분 좌표 이동 시 조건 비교비교1   1) 공통 좌표값까지 대각선 이동 후 여분 좌표값 한 블록 이동비교2   2-1) 공통 좌표값까지 대각선 이동 후 여분 좌표값만큼 대각선 이동   2-2) 공통 좌표값까지 대각선 이동 후 여분 좌표값-1만큼 대각선 이동 후 1만큼 한 블록 이동 3) 한 블록 이동만 사용  코드 : 조건문 활용x,y,w,s = map(int,input..

이 문제는 그리디 문제입니다.실버5 난이도여서 뚝딱하고 해결할줄 알았지만 예상외로 복잡한 코드로 풀었습니다. 접근법- 리스트 생성- 카약이 손상되었는데 여분 카약이 있는 팀을 우선적으로 제거- 그 후 반복문 통해 앞뒤 팀의 여분 카약 여부 체크하고 있을 시 여분 카약 리스트(rev_r_teams)에서 제거- 조건문에 걸리지 않으면 출발하지 못한 팀 cnt 증가 n,s,r = map(int,input().split())teams = [i for i in range(1,n+1)]s_teams = list(map(int,input().split()))r_teams = list(map(int,input().split()))cnt = 0rev_s_teams = list(set(s_teams)-set(r_teams..

실패한 접근법- matrix를 그리고 반복문을 통해 구현→ 시간초과로 실패import sysinput = sys.stdin.readlinen, m = map(int,input().split())matrix = [list(map(int,input().split())) for _ in range(n)]for _ in range(m): result = 0 x1,y1, x2,y2 = map(int, input().split()) for i in range(y1, y2+1): if x1 == x2 : result += matrix[i-1][x1-1] else: result += sum(matrix[i-1][x1-..

접근법- 메모리제이션 활용- (이전의 최대값 + 현재값)과 현재값 비교하며 최대값 결정 n = int(input())lst = list(map(int, input().split()))dp = [0] *(n+1)for i in range(1,n+1): dp[i] = max(dp[i-1]+ lst[i-1], lst[i-1])print(max(dp[1:]))

하루를 마무리하며 하나 풀어봅니다. 접근법- DP- 점화식 : dp[i] = dp[i-2] + dp[i-1] 실패 코드 - 입력값의 범위를 모두 충족하지 못했습니다. - n = 1일때 dp[2]에서 index out of range 에러 발생n = int(input())dp = [0 for _ in range(n+1)]dp[1], dp[2] = 1,2for i in range(3,n+1): dp[i] = dp[i-1] + dp[i-2]print(dp[n]%10007) 정답 코드n = int(input())dp = [0 for _ in range(n+1)]if n

제곱수의 합들을 구해보면 다음과 같습니다.1 : 12: 1 + 13: 1 + 1 + 14: 45: 4 + 16: 4 + 1 + 17: 4 + 1 + 1 + 18: 4 + 49 : 910: 9 + 111: 9 + 1 + 112: 4 + 4 + 4 시도 : 실패- 재귀함수 사용- N보다 작거나 같은 제곱수를 빼면서 카운팅- 반례 존재 : 12( 9+1+1+1)로 나오지만 최소개수는 3개(4+4+4)- 시도방법은 최소개수가 아닌 단순히 제곱수들의 합으로 나타내기만 한 것import syssys.setrecursionlimit(100000)def cal_func(n, cnt): num = int(n**0.5) rest = n - (num**2) cnt +=1 if rest == 0 : ..

DP 문제가 익숙해질 때까지 난이도를 올려가면 문제를 풀어보려고 합니다.해당 문제는 규칙성을 찾았다고 생각했는데 올바른 접근법이 아니여서 시간이 걸렸습니다. 시도- 안 되는 경우의 수를 찾기- 전체 경우의 수 - 안되는 경우의 수→ 안 되는 경우의 수가 1,2,3,6,10..... 나름의 규칙성을 가졌다고 생각해서 접근법을 가졌다고 생각했으나 틀렸다.  올바른 접근법- 각 자리에 대한 경우를 쪼개서 생각- 자리수가 늘어날때마다 각 숫자의 경우의 수를 생각하여 합하여 값 산출- 일반적 경우 : 2~8은 다음 자리에 올 수 있는 경우가 2가지(이전 자리의 단계수의 경우의 수)- 특수한 경우 : 0,9는 연속된 숫자가 1개임으로 각각 1가지 경우만 존재- dp를 2차원 배열로 만든다( n자리수, n 자리에 올..