차밍이

목차 문제 설명 문제 설명 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예 prices return [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] 입출력 예 설명 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다. 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다. 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다. 5..

거스름돈 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 28162 17674 15045 62.446% 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다. 출력 제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오. 예제 입력 1 380 예제 출력 1 4 예제 입력 2 1 예제 ..

해킹 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 8889 3518 2481 38.453% 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다. 최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개..

효율적인 해킹 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 5 초 256 MB 41545 7680 5077 19.779% 문제 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다. 이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다. 이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은..

카드2 성공 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 (추가 시간 없음) 128 MB 28612 15057 12620 54.019% 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고,..

카드2 성공 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 (추가 시간 없음) 128 MB 28612 15057 12620 54.019% 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, ..

동전 0 성공 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 53997 28653 22442 52.533% 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 예제 입력 1 10 4200 ..

1. 정의 재귀 용법을 활용한 정렬 알고리즘 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 2. 알고리즘 이해 이해를 돕기위한 예시 쪼개는 단계 [1, 9, 3, 2] > [1, 9] , [3, 2] > [1], [9], [3], [2] 더 이상 쪼갤 수 없으면 합병을 진행 작은 데이터를 앞에 큰 데이터를 뒤로 가도록 병합한다. [1], [9], [3], [2] > [1, 9], [2, 3] > [1, 2, 3, 9] 왼쪽 index 번호와, 오른쪽 index 번호를 활용해서 값을 비교해서 넣어가는 방식으로 진행하면 된다. 3. 코드 작성 데이터를 나누는 부분 & 데이터를..

목차 1. 퀵 정렬 (Quick Sort) 이란? 정렬 알고리즘의 꽃 기준점(pivot이라 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽, 크면 오른쪽으로 모으는 함수를 작성한다. 왼쪽과 오른쪽은 재귀 용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복한다. 함수는 왼쪽 + pivot + 오른쪽 을 출력한다. 분할 정복에 속하는 정렬이라고 할 수 있다. 2. 퀵 정렬 코드 작성 소스코드 data_list = [49, 97, 53, 5, 33, 65, 62, 51] def quick_sort(num_list): if len(num_list) >> [5, 33, 49, 51, 53, 62, 65, 97] 알고리즘 구현 및 풀이 quicksort 함수 만들기 만약 리스트 개수가 한 개이면 해당 리스트..

목차 1. 정의 동적계획법(Dynamic Programming) "DP"라고 많이 부름 큰 문제를 해결하기 위해, 작은 문제를 부분 부분 해결하여 저장해놓고 사용한다. 상향식 접근법으로 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과를 이용해서 상위 문제를 해결한다. Memoization 기법을 사용한다. 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용된다. ex) 피보나치 수열 분할 정복(Divide and Conquer) 문제를 나눌 수 없을 때까지 나누어서 각각 문제를 풀면서 다시 합병하여 문제의 해답을 찾는다. 다시 합병한다. 하양식 접근법, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식 일반적으로 재귀 함수로 구현 문제를 잘게 쪼갤 때, 부분 문제는 서로..