머신러닝 개발자의 러닝머신

문제 - 링크 문제 해결 아이디어 실제로 왔다갔다를 구현하지 않고 다음에 택배를 배달해야 하는 위치, 상자를 수거해야 하는 위치를 업데이트 하기 -> 문제를 가장 단순한 형태로 바꾸자 가장 먼 지점부터 택배를 배달하고, 상자를 수거한다 문제 풀이 택배를 배달해야하는 가장 먼 위치의 집(idx1), 수거 해야하는 가장 먼 위치의 집 인덱스(idx2)부터 시작 매 턴마다 answer += max(idx1, idx2), 두 인덱스 중 더 먼지점까지 이동 cap 만큼 뒷집부터 배달해야 하는 택배 제거, cap 만큼 뒷집부터 수거해야 하는 상자 제거 -> idx1, idx2 갱신 -> 이때, idx1, idx2는 다음번 방문 필요한 지점을 의미하므로 값이 0보다 큰 위치를 가르키고 있어야 함 -> cap만큼 이동..

문제 설명- 문제링크 유형 완전탐색 : 어떤 알고리즘으로 최적의 답을 찾을 수 있을 지 방법이 없음 & 이모티콘의 갯수가 최대 7개 -> 완전탐색으로 모든 경우의 수 살펴보자 알아야 하는 것 1. 중복순열 라이브러리 itertools.product 2. 대소비교 우선순위-> 원소들 배열에 넣고 (>, 중복순열로 각 이모티콘의 할인율 리스트에 대해 구독자 수, 판매금액 계산 - 각 케이스에 대해 모든 사람들의 구매 결제, 구독 여부 판단 - answer 구독자 수, 판매금액 순차적으로 대소비교 가능 코드 구현 from itertools import product def solution(users, emoticons): answer = [0, 0] #구..

문제 유형 dp 아이디어 이 문제를 읽고 처음에는 완전탐색을 떠올렸다. 하지만 dfs/bfs를 이용하면 선택하지 않은(이웃하지 않은) 스티커를 매 column마다 반드시 하나는 선택하기 때문에 한 column에서 스티커가 하나도 선택되지 않는 경우는 고려할 수 없을 것이라는 생각에 다른 아이디어를 생각했다. -> dp 아이디어 ! dp 테이블을 이용해 해당 칸까지 얻을 수 있는 점수를 매 칸마다 계산한다면 위의 한계점을 극복할 수 있을 것이라 생각했다. 해당 칸의 스티커가 선택된 경우, 이웃 column의 스티커가 선택될 수 있거나 선택되지 않을 수 있다는 점을 주의하자! 이웃 column의 스티커가 선택되지 않은 경우, 그 이전 column의 0 또는 1행의 스티커가 선택되는 경우가 존재한다 dp[i]..

아이디어 - 앞에서부터 순차적으로 검색하는데, 찾는 단어를 발견하면 다음 탐색 인덱스 += len(find), 발견하지 못하면 다음 탐색 인덱스 += 1 구현 - 처음 ~ (마지막인덱스-len(find)) 인덱스까지 탐색해야 함 (등호 포함됨 주의!!) 코드 text = input() find = input() num = len(text) -len(find) +1 result = 0 idx = 0 while idx

유형: 그리디 해결 아이디어 - 도착이 빠른 순서대로 택배 리스트 재정렬 : 그리디 아이디어, 1번 마을부터 출발하므로 도착이 가장 짧은 순서대로 정렬해서 순서대로 짐을 싣는다면 가장 짧은 기간동안 물건을 가지고 있을 수 있다. (처음 풀때는 (출발, 도착) 튜플을 정렬해서 출발지와 도착지가 모두 빠른 순서대로 검사해나갔지만 도착이 빠른 순서대로 재정렬하면 됨.) 구현 - able_remain: 각 마을 번호의 위치에서 실을 수 있는 무게, 남아 있는 용량 리스트 - 동작과정 (1) 도착이 빠른 주문부터 순서대로 확인하면서 from->to 경로를 지날 수 있는 남은 용량을 구한다 (2) 옮길 최종 무게를 결정한다 = min(지날 수 있는 남은 용량, 주문 물건의 무게) (3) 옮긴다. 지나오는 마을의 남..

점화식 관계가 뚜렷하다면 dp 재귀적 호출 기억하기,,! (1) top-down 방식 : 내가 원하는 값을 구하기 위해 재귀적으로 호출하며 더 낮은 쪽으로 계속 파헤치기 (ex) 피보나치 수열 F[n] = F[n-1] + F[n-2] (단, F[0] = 0, F[1] =1) dp = [-1 for _ in range(30+1)] def fibo(num): if num == 0: return 0 if num == 1: return 1 if dp[num] != -1: return dp[num] dp[num] = dp[num-1] + dp[num-2] return dp[num] print(fibo(30)) (2) bottom-up 방식 : 가장 작은 항부터 구하고자 하는 항까지 모든 dp 테이블 완성하기 de..

해야할 것 많은 구현 - 터지는 블록의 크기가 2*2로 정해져 있으므로 bfs나 dfs를 사용하지 않고 board 한번씩 훑으면서 터지는 블록 여부 확인 1. while 더이상 없을 때까지 (2*2 윈도우 사이즈로 board 검사하면서 터지는 블록 있는지 확인) 2. 터지는 블록있으면 dic에 좌표 추가해준다. 3. 맵을 한번 훑은 뒤 board 갱신 : dic 을 set() 형태로 바꿔주어 중복제거 : dic에 있는 좌표들의 board값을 "None"으로 바꿔준다. 4. len(dic)만큼 answer 에 더해준다 5. board 빈칸 채우기 : 아래쪽 행부터 확인하면서 빈칸이 있으면 빈칸이 아닌 칸까지 탐색하여 빈칸이 몇칸인지 num+= 해주고, none이 아닌 값들을 하나씩 빈칸의 갯수 칸 수만큼 ..

-> 분할정복 ; 예전부터 분할 정복에 약하다 생각했지만 이번 문제를 마주했을 때 분할 정복/ 재귀 개념을 떠올리지 못해서 더 많은 연습이 필요하다고 느낀 문제이다. 0. +/-/* 연산자의 우선순위 순서는 총 6개이며 각 우선순위 배열에 따른 연산 결과를 계산한다 prior = [ '*+-', '*-+', '+*-', '+-*', '-*+', '-+*' ] 1. 우선순위가 낮은 연산자 순서부터 split(연산자) 를 통해 문자열을 분리한다 2. 분리된 문자열을 다시 재귀적으로 그 다음 우선순위가 낮은 연산자를 기준으로 분리한다 3. 우선순위가 가장 높은 연산자까지 문자열 분리가 모두 완료되었다면 우선순위가 높은 순서대로 연산을 진행하며 재귀를 하나씩 탈출한다 4, 해당 우선순위 배열에 따른 연산의 결과..