난이도: Lv.3유형: DP해결 여부: 성공내가 생각했던 아이디어/큰 가닥문제 푸는 방향을 처음에 잘 잡았다. 문제 읽고 바로 풍선 왼쪽의 최솟값, 오른쪽의 최솟값 둘과 비교해서 풀면 된다고 나왔다.오답 이유처음에는 매번 최솟값을 구하느라 시간초과가 났다.이후 왼쪽은 최소는 누적시키며 비교하고, 오른쪽은 같은 수가 없는 점을 이용해 같을 때 갱신하는 식으로 했는데, 오른쪽 갱신 부분에서 시간초과가 나는 것 같았다.그래서 처음부터 왼쪽 최솟값과 오른쪽 최소값을 2번의 순회로 2*N의 시간복잡도로 구할 수 있게 해놨다.해답저렇게 해서 정답을 맞았다#기억할 문법 #내 정답코드def solution(a): answer = 0 length=len(a) if length
Algorithm/DP
난이도: Lv.3유형: DP해결 여부: 정답 내가 생각했던 아이디어/큰 가닥처음에는 갈피를 못잡았다. 일단 dp로 가능할거 같기도 생각하면서도 원형이라 답이 안나왔고, 그리디로는 예외 케이스 있을 거 같아 안했다.최소크기를 생각해보자. 적어도 3칸 중 하나는 무조건 골라야 한다. 안그러면 손해. 왜? 가운데 고르는 경우 있으니까그러면 3칸씩 슬라이딩 윈도우 하는 방식으로 해야하나 싶었다. 기댓값 방식으로 지금 고른 값-나머지 포기하는 값들... 은 예시보니 바로 예외 나와서 아니었다.최소:ceil(N/3) ~최대: ceil(N/2) 개 값을 고르게 되는데 이 개수 안에서 bruteforce인가 싶었다. 아니면 경우의수로 파면서 재귀함수 인가 싶었다.이게 일직선이었으면 DP 쓰기 편한데 원형이어서 생각이 ..
난이도: Lv.3유형: DP해결 여부: 틀림내가 생각했던 아이디어/큰 가닥행렬 곱은 순서에 따라서 연산횟수가 달라지는데 그 연산횟수를 최소화 하는 방법에 대한 문제였다. 사실 행렬 곱 자체에 대한 이해가 없어서 한번 gemini한테 물어봤다. 그러고 나서, 일단 행렬곱을 가능하게 만드는 열을 찾고, 그게 큰 수부터 계산해서 제거해나가면 되지 않을까 싶었다. A * B 행렬과 B * C 행렬을 곱하면 A * C 가 되어서 B가 사라지니까... 커다란 B 부터 없애면 되지 않을까 싶었다. 즉 greedy로 푸나 싶었다. 하다가 이건 아닌거 같아서 중단하고 답을 봤다. 오답 이유근데 접근 방법 자체가 그게 아니었다. DP로 푸는거였는데 애초에 나는 큰 오해를 하고 있었다.주어진 행렬끼리 가능만 하다면 순서를 ..
난이도: Lv.3유형: DP해결 여부: 오답내가 생각했던 아이디어/큰 가닥전형적이고 쉬운 문제라고 생각했다. DP를 사용해서 풀면 될거 같았고, 주된 식으로는 거스름돈 종류만큼 이전 dp 배열에다가 다 합하고, 같은 종류 예방을 위해 1을 빼주는 복잡한 점화식을 생각했다. 오답 이유근데 이러면 재귀도 너무 깊어지고, 점화식도 복잡하다. 훨씬 간단한 해법이 있었다. 해답그냥 화폐 종류별로 하나씩 꺼내서 이전 만큼 더해주는 거였다. 생각보다 훨씬 간단했다.잘못된 사고 (Top-down의 위험): "n원을 만들기 위해 화폐들을 조합해보자." (중복 발생 위험↑)올바른 사고 (Bottom-up): "지금까지 1원짜리로만 만들 수 있는 경우의 수를 다 구해놨어. 이제 여기에 2원짜리 동전을 쓸 수 있다는 허락이 ..
난이도: Lv.3유형: DP해결 여부: 통과아이디어삼각형 내려오면서 가장 큰 값을 구하는 문제. 내려오면서 DP로 기록하는식으로 구하면 된다.오답 이유 혹은 알게 된것로직틀리진 않았는데, 2차원 배열인거 무시하고 값 처음꺼 하나라고 index를 하나밖에 안써주거나 배열 초기화 할때 그냥 빈 배열 선언해놓고, list out of index 나게 하는거. append로 처리할 수 있는거는 처음부터 append 쓰는게 나을듯lamda 식 쓰면 앞으로도 임시값 처리할때 유용할 것 같다. def solution(triangle): height = len(triangle) arr = [int(triangle[0][0])] temp=[] for i in range(1,height): ..
난이도: Lv.3유형: DP해결 여부: 에러 후 통과아이디어평범한 길찾기 DP 문제오답 이유 혹은 알게 된것for문에서 range 안쓰고 그냥 in 써서 틀림...초깃값 설정 문제와 문제에서 말한 좌표가 1씩 더해진 것 보정이어야 하는데 그걸 안해서 틀렸다. 근데 또 테케에서는 맞아서 왜틀린지 몰랐었다.def solution(m, n, puddles): arr=[[0]*m for _ in range(n)] for puddle in puddles: arr[puddle[1]-1][puddle[0]-1]=-1 arr[0][0]=1 for i in range(0,n): for j in range(0,m): if (i==0 and j==0) or ..
난이도: Lv.3유형: DP해결 여부: 오답 아이디어주어진 숫자를 최소로 써서 사칙연산만으로 목표 숫자에 도달하는 개수 맞추기 오답 이유 혹은 알게 된것문제좀 잘 읽자. DP 인데 숫자의 개수가 아닌 사칙연산의 개수로 착각했던 점, 최대 8까지라는 제한이 없다는 점을 빼먹어서 더 효율적인 방법이 있을거라 생각해 애먹었다.DP 지만 bruteforce 적인 성격도 띄는 문제였다. 처음에 혹시 index 숫자에 value로 그 값 넣는 식으로 안되나 싶어서 시간이 걸렸다. set()의 사용이 미흡해 좀 걸렸다. set() 은 그냥 이렇게 선언해서 for문 돌리면 된다.update로 한번에 여러개 하려고 했는데 그게 아니었다. update로 set 여러개 add하고 싶으면 묶어주어야 해서 걍 add 여러번 쓰..
난이도: Lv. 3유형: DP, 수학, 부분합해결 여부: 오답아이디어홀수는 들어올 수 없다. 애초에 0으로 잡아야 한다.짝수가 들어올때 이전에 있던 모양에서 가로 2줄씩 3가지 경우가 붙는다고 봐야 한다.. 하지만 여기에 특수한 형태가 있다. 오답 이유 혹은 알게 된것DP로 접근하는 것 까지는 맞았으나, 이후 점화식에서 틀렸다. f(n)은 항상 f(n-2) 에서 도출되며 3*f(n-2) +2 로 잡았는데 f(n-4) 에서도 도출되는 경우를 생각해야 했다. 만약 하나만 세로로 하고 그 옆을 3줄짜리 가로로 주르륵 채운다면 그건 f(n-2) 에서는 얻을 수 없는 형태가 된다. 그래서 f(n) = 3f(n-2) -> f(n-2) 에서 3칸 붙이기 뿐만 아니라 2f(n-4), 2*f(n-6) ...2f(0) ..
