바닥부터 시작하는 개발 공부

알고리즘 분류: 그리디 탐색 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1..

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

알고리즘의 성능을 평가하는 지표는 크게 두 가지가 있습니다. 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 당연히 복잡도가 낮을수록 좋은 알고리즘이 됩니다. 이중 for문이라던가 재귀함수라던가 문제를 굉장히 쉽게 풀 수 있음에도 어렵고 복잡한 알고리즘을 사용하는 이유는 이 복잡도를 줄기이 위해서입니다. 빅오 표기법(Big-O notation) 가장 차수가 높은 항만을 고려하는 표기법입니다. 다음의 예를 보겠습니다. $3N^3+ 5N^2+ 100000$ N의 3승의 차수가 가장 높으므로 $O(N^3)$이 됩니다. 코딩 테스트에서는 일반적으로 $O(nlogn)$정도에서 해결을 목표로 합니다. 시간 복잡도에 대해서 예를 들어..

문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할..

문제 자연수 N과 정수 K가 주어졌을 때 이항 계수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ N) 출력 $(N/K)$를 출력한다. N, K = map(int, input().split(" ")) a=1 b=1 for i in range(N-K+1,N+1): a*=i for i in range(1,K+1): b*=i print(int(a/b)) 가능한 N의 범위가 적기 때문에 어떻게든 값만 구하면 시간 초과는 안나올 것이라고 생각해 접근했다 팩토리얼을 반복문으로 구현할때와 마찬가지로 진행한다 최대한 계산을 간략히 하기 위해서 n!과 (n-k)!을 약분해준뒤 진행한다

문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 배열 안에 숫자가 존재하는지 탐색하는 알고리즘입니다. 간단하게 if not in 이나 in을 사용하게 되면 배열의 범위가 100,000까지이..

코딩 테스트 문제를 풀다보면, 배열에서 내가 원하는 원소가 들어 있는지 확인 해야하는 일이 꽤 있습니다 if a in arr: print True 물론 파이썬에서는 이런 식으로 in, not in 연산을 통해 확인할 수 있습니다. 그런데 코딩테스트 문제에서는 시간 복잡도라는 걸 반드시 고려해야합니다 배열에 대해서 몇번 정도만 원소를 탐색한다면 괜찮겠지만 모든 원소에 대해서 위치를 탐색하는 경우라면 어떨까요? N의 길이를 가지면 배열에서 원소를 탐색하면 평균적으로 N/2정도만 뒤져보면 원소의 위치를 탐색할 수 있습니다 그러면 $N*N/2$ = > 시간복잡도 $O(N)$은 $ N^2$이 나오게 되는 상황이 나옵니다. 배열의 길이가 짧은 경우는 상관이 없지만, 대부분 굉장히 긴 배열을 채점 단계에서 집어 넣어..

음식의 스코빌 지수가 들어있는 리스트 scovlle을 입력받는다 가장 스코빌이 낮은 음식과 두번째로 낮은 음식을 섞에 새로운 스코빌의 음식을 얻는데 섞인음식 mixed = 가장 낮은 스코빌 + 2*두번째로 낮은 스코빌이다. 모든 음식이 K이상의 스코빌을 가지도록 이를 반복하고 반복횟수의 최솟값을 return한다 from heapq import heappush, heapify ,heappop def solution(scoville, K): cnt =0 heapify(scoville) while scoville[0]