I about me

문제 설명이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.명령어수신 탑(높이)I 숫자큐에 주어진 숫자를 삽입합니다.D 1큐에서 최댓값을 삭제합니다.D -1큐에서 최솟값을 삭제합니다.이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.제한사항operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.operations의 원소는 큐가 수행할 연산을 나타냅니다.원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.빈 큐에 데이터를 ..

문제 설명OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하..

문제 설명임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다. n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요.제한 사항n은 1이상, 50000000000000 이하인 양의 정수입니다. 입출력 예nreturn1211443-1 문제 풀이다음의 원리만 제대로 안다면, 틀릴 이유가 없는 문제이다.A = 1.0B = 1print(A == B) # True1) import math에서 루트를 가져온다2) 루트 n한 값과 그것을 int로 씌운 것이 같다면, (n+1)^2을 return만약 이것을 찾지 못했다면, 문제에서 약간의 힌트를 얻을 수도 있다.입출력 예 설명 입출력 예#1 121은 양의 정..

문제 설명효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.제한사항n은 1 이상, 2000 이하인 정수입니다. 입출력 예nresult4533 문제 풀이 순서이거 뭔가 공부한 느낌인데 코드로 어떻게 구현하지? 라고 생각되었다. ..

문제 설명△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다. 이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번..

문제 설명대문자와 소문자가 섞여있는 문자열 s가 주어집니다. s에 'p'의 개수와 'y'의 개수를 비교해 같으면 True, 다르면 False를 return 하는 solution를 완성하세요. 'p', 'y' 모두 하나도 없는 경우는 항상 True를 리턴합니다. 단, 개수를 비교할 때 대문자와 소문자는 구별하지 않습니다. 예를 들어 s가 "pPoooyY"면 true를 return하고 "Pyy"라면 false를 return합니다. 제한사항문자열 s의 길이 : 50 이하의 자연수 문자열 s는 알파벳으로만 이루어져 있습니다. 입출력 예sanswer"pPoooyY"true "Pyy"false  문제 풀이 순서1) 대소문자를 구별하지 않으므로 :a = s.lower()2) 그걸 돌리면서 하나씩 숫자를 센다3) 같으..

예상문제 1. Divide and Conquer과 Dynamic Programming의 차이점을 서술하시오. Divide and Conquer Dynamic Programming공통점큰 문제를 작게큰 문제를 작게차이점- Top-down 접근 방식- 상호 관련이 없는 경우에 효율적근데 관련 있으면 비효율적- Bottom-up -  재 컴퓨팅 xx -> 저장 + look it up그러니까 관련 있는 거할 때 효율적예시Merge Sort, Quick SortLongest Common Subsequence, Matrix Chain Multiplication 예상문제 2. LCS(Longest Common Subsequence)시간복잡도: O(mn) - 여기서 m과 n은 각각 두 문자열의 길이를 나타냄- 두 문자..

Merge Sort만약에 코드가 주어주면 시간 복잡도를 도출할 수 있는가?MergeSort(Array, p, r): if p > r return q = (p+r)/2 mergeSort(Array, p, q) # A[p...q]를 모두 나누기 -> 정렬 mergeSort(Array, q+1, r)# B[q+1...r]를 모두 나누기 -> 정렬 merge(Array, p, q, r) # 병합 (1) divide - and - Conquer 이론과 연결지어 설명할 수 있는가?Divide-and-Conquer에 기반하여 Merge하여 정렬하는 방법시간 복잡도와 관련하여 각각 단계를 설명하면 다음과 같다.Divide - Conquer 배열을 두 개의 하위 배열로 나누고, ..

Sorting컴퓨터 과학 및 알고리즘 분야에서 중요한 개념으로, 주어진 데이터를 특정한 기준에 따라 순서대로 재배열하는 작업 Sorting의 응용예상문제 1. sorting 기반과 divide-and-conquer 기반의 큰 맥락  sortingdivide-and-conquer시간복잡도예시BestAverageWorstSearchLinear SearchOXO(1) O(n) O(n)1D Closest Pair (1차원 가장 가까운 쌍)Element Uniqueness (요소 고유성)Median and Selection(중앙값과 선택)Mode(최빈값)Binary SearchOOO(1)O(log n)O(log n)Convex hulls (볼록 껍질) 아래에 자세한 내용들을 정리해두었으니 참고해둘 것!더보기Lin..

Master Theorem재귀적인 방식으로 문제를 해결하는 경우에 자주 사용되는데, 특히 even split 알고리즘에 대한 재귀식을 다룰 때 유용어떤 알고리즘의 시간 복잡도 함수 T(n)이 다음과 같은 형태일 때,  다음의 1, 2, 3을 직관적으로 보면, 1. g(n)이 무거우면 g(n)이 수행 시간을 결정한다.2. g(n) 과 f(n)이 같은 무게이면 g(n)에 logn을 곱한 것이 수행 시간이 된다.3. f(n)이 무거우면 f(n)이 수행 시간을 결정한다. g(n)을 사용하는 이유)하나씩 차근히 살펴보자!ExampleMaster Theorem을 사용하여 주어진 재귀식을 해결해라.T(1) = 1 and T(n) = 8T(n/2) + n^2T(1) = 1 and T(n) = T(3n/4) + 10T(..