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

문제 유형 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) 옮긴다. 지나오는 마을의 남..

: 우선순위 큐, 힙 큐(Queue) : FIFO(First In First Out)의 자료구조로 먼저 들어온 데이터가 먼저 추출되는 구조를 갖는다. 우선순위 큐(Priority Queue) : 각 자료에 부여된 우선순위에 따라서 추출되는 순서가 정해지는 자료 구조이다. 힙(Heap) : 우선순위 큐의 구현을 위한 완전 이진트리의 자료구조, 파이썬에서는 최소힙이 제공된다. 또한, 이진트리의 힙 구조를 이용하면 최솟값과 최댓값을 구하는 데에 걸리는 시간이 단순 배열보다 매우 빠르다는 장점이 있다. (단순 배열의 시간복잡도 O(n), 힙을 이용한 탐색 시간복잡도 O(log₂n) ) : 최대힙 (Max Heap) - 부모 노드가 항상 자식 노드보다 큰 구조, 루트 노드에 최댓값이 저장됨 : 최소힙 (Min H..

: 규칙 찾기 - 이 문제의 낯선 점은 도형의 회전과 도형을 만들어가는 과정의 규칙을 찾아 구현하는 것이다. - 이때 생각해야 하는 것은 도형의 회전을 이 도형을 이루는 선분들의 회전으로 치환하는 것이다. 시계 방향으로 90도 회전했을때 방향을 가진 선분들은 다음과 같이 변환된다. → ☞ ↑ ← ☞ ↓ ↑ ☞ ← ↓ ☞ → - 그리고 다음 세대의 드래곤 커브가 될 때 끝점부터 다시 이어 붙여 선분을 curve 리스트에 차례로 추가하게 되는데, 그림과 같이 0, 1, 2, 3의 순서대로 선분이 추가 된다. 따라서 다음 세대의 선분을 그릴 때 앞선 세대의 드래곤 커브 리스트의 인자를 배열의 마지막 인덱스부터 거꾸로 순으로 이어붙여 만들어 짐을 유의해야 한다. dr_map : (101, 101) 의 크기를 갖..

: DP(Dynamic Programming) -1~n번 물건을 순차적으로 살펴보면서 무게 1~k 까지 넣을 수 있는 최대의 가치를 갱신하면서 테이블을 작성해나간다. -DP 테이블 · row: 1~n 물건, col: 1~k 배낭에 넣을 수 있는 무게 · (1+n)*(1+k) 사이즈의 2D 테이블 · dp[i][j]의 의미: i번째 물건까지 살펴본 결과 가방에 j의 무게만큼 넣을 수 있을 때의 최대의 가치 · i번째 물건의 무게를 w, 가치를 v 라고 할 때, dp[i][j] = max( 물건 i를 포함시킬 경우 가방에 j의 무게를 넣을 수 있을때의 가치 , 물건 i가 포함되지 않고 가방에 j의 무게를 넣을 수 있을 때의 가치 ) (이때, 물건 i가 포함될때 가방에 j의 무게를 넣을 수 있을 때는 ( i-..

: 구현 ☞ 문제 상황을 논리적, 체계적으로 구현하는 문제이다. 반복문을 돌면서 각 시행마다 톱니 번호, 회전 방향을 입력받아 양 옆의 톱니바퀴를 순차적으로 확인하면서 회전 가능한지 여부 확인해서 회전 가능하다면 리스트에 넣고 회전 가능하지 않으면 반복문 break해서 더이상 옆의 톱니들 확인하지 않도록 해주기 톱니 회전 가능 여부를 살펴본 뒤 모든 톱니 한번에 회전시키기 ※ 주의 사항: 톱니 하나씩 확인하면서 회전 가능 여부 따지고 나서 그 순간 회전을 바로 시키지 않도록 주의 한다// 톱니의 정보가 바뀌면 회전 가능 여부가 바뀐 톱니의 정보에 대해서 따지게 되므로 톱니의 회전의 반영은 회전 가능 여부를 마친 뒤 동시에 회전시켜야 한다. (1) 회전시키려는 톱니의 오른쪽에 있는 톱니들 회전 가능 여부 ..

DP [Dynamic Programming], 동적계획법 DP: 하나의 문제를 작은 여러개의 문제들로 나누어 부분의 결과를 저장해 재사용하는 것으로, 메모리 사용을 효과적으로 개선할 수 있다. DP의 유형 1) top-down: 큰 문제부터 시작해서 작은 문제로 쪼개가면서 답을 내는 과정이다. 이때, 한번 계산된 값들은 저장해두고 또 필요한 경우 이를 참고해 재사용한다 2) bottom-up: 작은 문제들에 대한 값을 미리 모두 저장해두고 작은 문제에서부터 큰 문제로 가면서 답을 낸다. DP 사용조건 1) overlapping subproblems (겹치는 문제): 동일한 작은 문제가 반복적으로 나타나 그 값을 재사용할 수 있는 경우 2) obtimal substructure (최적 부분 구조): 작은 ..