메모장

https://softeer.ai/practice/6293 Softeer - 현대자동차그룹 SW인재확보플랫폼 남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다. 이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지 softeer.ai import sys n = int(input()) lst = list(map(int, input().split())) dp = [1]*(n*1) for i in range(n): for j in range(i-1, -1, -1): #이전 돌 찾기 if lst[i] > lst[j]: #이전 돌보다 크다면 dp[i] = max(dp[i],dp[j]+1) print(max(dp)) 생각보다 헤맸던 문제..

보호되어 있는 글입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/154538#qna 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 보고, 처음에 그리디를 생각했는데 그리디 문제가 아니였다 그래서 dp를 생각하고 아래와 같이 풀었으나 75점을 받게 됐다. #### 1차 풀이 => 75점 #### def solution(x, y, n): answer = 0 dp = [1000001]*(y+1) dp[x] = 0 for i in range(x+1,y+1): if i % (x*6) == 0: dp[i] = min(d..

- Knapsack Problem 어떤 배낭이 있고 그 배낭 안에 넣을 수 있는 최대 무게는 K이다. 배낭에 넣을 수 있는 N개의 물건이 각기 다른 가치 V를 가지고 있으며 각 물건마다 다른 무게 W를 가지고 있을 때, 배낭이 최대한 가치 높은 물건들을 담을 수 있는 조합을 찾는 문제이다. 위 문제를 어떻게 접근해야 할까? 브루트포스 알고리즘으로 접근하게 된다면, 그 물건을 넣었을 때와 안 넣었을 때의 모든 조합을 확인해봐야하기 때문에 O(2^n)이 걸리게 된다. 그리디 알고리즘도 옳지 않다. 최적의 해를 구할 수 없다. 그래서 이 문제는 DP로 접근해야 한다 ! 하지만, 막상 DP로 풀려고 하니 식을 도출하지 못했다. 그래서 단계별로 식을 도출해보려고 한다. 우선 위에서 말했듯이 우리가 선택할 수 있는..

알고리즘 공부할 때, 빈번하게 나오는 유형이 아니다보니 매번 공부를 미뤘다. 이젠, 시간에 쫓기지 않아도 되니 조금씩 다뤄볼 예정이다 ! 이분탐색 이분 탐색이란 말그대로 정렬된 리스트에서 검색 범위를 줄여나가며 특정 값을 찾는 알고리즘이다. 왜 사용 ? 검색이 반복될 때마다, 범위를 절반씩 줄여나갈 수 있기 때문에 시간복잡도 O(logN)이다. 범위 절반씩 줄기 때문에, 당연하다. 투 포인터(Two Pointer)와 무슨 차이 ? 조금 깊게 생각해보면 차이를 확연히 느낄 수 있다. 이분 탐색 투 포인터 시간복잡도 O(logN) O(N) 조건 정렬된 리스트 상관없음 방식 mid를 활용해서 범위를 절반씩 줄여나감 start, end 사용해서 한 칸씩 이동 정렬되지 않은 리스트에서 특정한 값을 찾아야한다면, ..