https://programmers.co.kr/learn/courses/30/lessons/43238 - flow 처음에 카테고리가 이분탐색인 것을 보고 약간 멘붕이 왔다. binary search 를 오랜만에 보다 보니 이게 이분 탐색으로 푸는 게 적합한 문제인가 감이 안 왔다. 계속 생각해보다가 적합한 time을 이분탐색으로 찾는 거구나 해서 바로 풀...
https://programmers.co.kr/learn/courses/30/lessons/42628 - flow 동시에 최소힙과 최대힙을 운용하면 된다. 예전 글에 python heapq를 이용했던 적이 있다. 이번에도 이용해서 풀면 금방 풀 수 있다.. 시간 복잡도는 힙 두개를 만드는 것이므로 O(NlogN) 이다. Operations 길이가 N이고 ...
https://programmers.co.kr/learn/courses/30/lessons/43105 - flow 너무 뻔한 dp 문제이다.. f(n) : 높이 n일 때, 바닥까지의 최댓값 리스트 로 이전 값을 계속 볼 필요 없이 한 층씩 쌓아 나갈 수 있다. 시간 복잡도는 근데 O(N^2) 이 나온다.. N은 높이 1+2+3+4... + N 의 연산이 ...
https://programmers.co.kr/learn/courses/30/lessons/49189 - flow 간선 가중치를 모두 1이라 생각하면 양수 가중치 쌍방향 그래프가 되서 다익스트라로 1번 노드와 다른 모든 노드간의 최단 거리 값을 구할 수 있다.. 그 중 거리가 가장 큰 노드들의 개수가 답이 되겠지만 약간 비효율적인 것 같아 다른 방법을 생...
https://programmers.co.kr/learn/courses/30/lessons/42861 - flow 문제를 보면서 계속 생각해봤는데 왠지 예전에 알고리즘 수업에서 봤던 되게 흔한 느낌이 났다.. 정확히는 기억 안나서 찾아보았더니 최소 신장 트리를 만드는 문제와 동치이다. 예전에 공부했던 자료도 다시 보고 정리해서 써볼까 했는데 코드를 작성하...
https://programmers.co.kr/learn/courses/30/lessons/42884 - flow 그리디 알고리즘? routes 리스트를 정렬한 후, 순서대로 겹치는 부분을 확인해 나아가면 될 듯함 정렬 했을 때, 순서대로 A와 B가 겹치는 부분 존재하고, B와 C가 겹치는 부분 존재하면서 A와 C가 겹치지 않을 때, 그냥 A와 B가 겹치...
https://programmers.co.kr/learn/courses/30/lessons/43163 - flow 가장 짧은 변환 과정을 찾는 문제.. 루트가 begin인 트리에서 자식 node들이 words에 포함되어 있고 부모로부터 변환이 가능한(철자 하나 차이) 집합을 규칙으로 하는 트리가 만들어질 때, 너비 우선 탐색을 통해서 target과 일치하...
알고리즘 문제 풀다가 heap 이용해야 되는 상황이 나와서 직접 배열로 구현할까 하다가 모듈 써보기로 해서 찾아봄. - reference http://www.daleseo.com/python-heapq/ 출처가 문제 되면 바로 내리겠습니다.
https://programmers.co.kr/learn/courses/30/lessons/42627 - flow 특정 시점일때, 요청이 들어와서 처리가 가능한 작업중 가장 짧은 작업을 선택해 나아가면 된다. 예시같은경우 처음 시점 0ms 일때, A만 가능하므로 A선택, A는 3ms 걸리므로 다음 시점은 3ms, 이 때 가능한 작업들은 요청 들어온 시간이...
원래 type hinting을 주제로 글을 쓰려다가, 타입 추론에 대해 글을 써내려가다 보니 이거 하나만으로도 글 하나가 대충 완성될 것 같았다. 그래서 이번에는 그냥 타입 추론 이야기를 해보려고 한다. 타입 추론 Python은 타입 검사가 동적이기 때문에, 모든 타입이 컴파일 타임이 아니라 런타임에 결정된다.
https://programmers.co.kr/learn/courses/30/lessons/43104 - flow 얼마 전에 봤던 타일링과 비슷하게 피보나치 수열이 이용이 된다. 규칙을 조금 생각해보면 쉽게 solution(n) = solution(n-1) + 2*f(n) 위와 같은 공식을 만들 수 있다. ( f 는 피보나치 수열 ) 키워드로 나온 dp ...
https://programmers.co.kr/learn/courses/30/lessons/43162 - flow 간단히 보면 n x n 배열의 원소들을 모두 탐색하는 문제이다. 최적화 해서 몇가지 원소들을 탐색하지 않아도 되게끔 만드려고 해도 결국 O(n^2) 이기 때문에 쉽게 가도록 하겠다. 키워드가 dfs 와 bfs 인데 둘중 어느 것을 써도 상관 ...
https://programmers.co.kr/learn/courses/30/lessons/12900 - flow n 의 총 길이를 채우는데 가로 2, 세로 1.. 가로로 배치한 수를 고정했을 때, 경우의 수를 합하면 될 것이라 생각.. 예를 들어 n = 5 이면, 가로 배치 0일때 경우의 수 1 가로 배치 1개일 때 경우의수는 n-2 개의 세로 타일들을...
https://programmers.co.kr/learn/courses/30/lessons/42895 - flow 카테고리가 dp 인 문제이다.. solution[n] 을 N을 n번 사용했을 때, 만들어질 수 있는 모든 수라고 정의하면 solution[n+1] 은 solution[n] 집합 내 모든 수에서 N 을 사칙연산 해준 값이 되지 않을 까 생각했다...
생각보다 단순한 문제들이 많아서 일일이 풀어 쓰기가 비효율적일 것 같아 넘어가기로 결정.. 가운데 글자 가져오기 (https://programmers.co.kr/learn/courses/30/lessons/12903) https://github.com/songjy6565/alg-py/blob/master/programmers/level1/A6.py htt...
https://programmers.co.kr/learn/courses/30/lessons/12901 - solution 요일 문제... 1월 1일 금요일이 주어졌으므로 input의 날짜와 1월 1일의 차이를 7로 나눈 나머지를 이용해 요일을 구할 수 있다. - result https://github.com/songjy6565/alg-js/blob/mas...
https://programmers.co.kr/learn/courses/30/lessons/42862 - solution 단순히 lost 와 reserve 간 element 들을 최대한 많이 매칭해주는 문제이다. 인풋 수가 거대하지도 않고, 시간복잡도 또한 신경쓰일 만큼 복잡해지지가 않아서 단순하게 생각 lost 가 정렬이 되어 있다고 생각해서(아닌가?)...
https://programmers.co.kr/learn/courses/30/lessons/42748 - solution 단순 정렬 문제? 정렬에서 O(NlogN) 이 걸리기 때문에 이 부분을 줄이지 않는 이상 전체 시간복잡도는 줄지 않는다. 정렬값을 반환하는 것이 아닌 k번째 수를 반환하는 문제이기 때문에 이것저것 해보고 싶긴 하다. min(k,n) (...