10000COW

문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 ..

문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 더보기 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 답을 출력한다. 예제 1 10 10 -4 3 1 5 6 -35 12 21 -1 출력: 33 예제 2 10 2 1 -4 3 4 -4 6 5 -5 1 출..

백준 15624번 피보나치 수 7 문제 유형: DP (동적 계획법) 문제 주의할 점 Python, JavaScript로 풀이시 Top-Down 방식 즉, 재귀 방식으로는 시간 초과가 발생한다. 또한 입력으로 주어지는 수가 최대 100만인데, Python은 최대 1000번까지 재귀할 수 있으므로 재귀 방식으로는 풀리지 않는다. 따라서 이 문제는 메모이제이션 + Bottom-Up 방식으로 풀이한다. Python 코드 JavaScript 코드

들어가기 전에 다익스트라 알고리즘을 이해하기 위해 여러 유튜브와 블로그를 방문했었는데 대체로 설명이 어렵거나 생략이 많다.. 코드 설명도 자세하지 않아 아쉬움이 있었다. (특히, 블로그에 있는 표나 그림은 왜이렇게 딱딱한걸까.. 잘 모르는 사람에겐 거부감이 든다) 직접 하나하나 그려가보며 이해한 나의 깨달음을 다른 분들께 자세하고 쉽게, 마치 아무것도 모르는 어린 아이에게 설명하듯이 설명해보려고 한다. 그리고 시간이 지나면 잊어버리는 미래의 나를 위하여 상세히 기술해보았다. 자세한 예시부터 점점 과정을 추상화해나가므로 이해하기 쉬울 것이라고 생각한다. 다익스트라 알고리즘이란? 그래프의 한 정점(Vertex 또는 Node)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘으로, 최단 경로 문제에 사용된다..

기수 정렬 : 주어진 수 들간의 비교를 하지 않고 버킷을 사용해 정렬하는 방법으로, 낮은 자리(1의 자리)에서 높은 자리(10^n 자리) 순으로 버킷에 넣는 방법으로 정렬한다. 실제로 숫자들 간의 비교를 통해 정렬을 하는 것이 아닌, 0~9까지의 버킷이 있고 이 버킷에 숫자를 넣어가며 분류한다고 생각하면 된다. 시간복잡도 O(r*n) : r은 숫자의 자릿수, n은 정렬될 수의 갯수 특징 1. 시간 복잡도에서 엄청난 이점을 갖는다. 무려 O(N).. 2. 하지만 그만큼 추가적인 메모리가 많이 필요하다. [153, 262, 37, 598, 433, 855]를 기수 정렬을 이용해 정렬해보자. 가장 낮은 1번째 자리부터(1의 자리) 가장 높은 3번째 자리(100의 자리) 순으로 정렬한다. 다음과 같이 0~9 까..