Toy야 놀자

오늘부터 코드스테이츠에서 공부하고 있는 Toy 문제를 하나씩 정리해볼 예정이다. 벌써부터 아득한 기분이 들지마, 해볼 때까지 해보려고 한다. - 문제 조의 개수와 조의 발표 순서를 인자로 받는 함수 구현이다. 모든 경우의 발표 순서 중에 인자로 받은 발표 순서가 몇

- 문제: 하나의 집합을 의미하는 문자열을 입력받아 각 문자를 가지고 만들 수 있는 모든 부분집합을 리턴 입출력 예시: 풀이: (주의) 입출력 예시를 통해 알 수 있듯이, 중복되는 요소의 값은 제외가 되고 결과값의 알파벳순으로 정렬되어야 한다. >DFS를 활용해야 한다는 것까지 생각해 냈지만, 코드로 구현해내지 못했다. reference code를 보...

- 문제: 아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴한다. 입출력 예시: 풀이: (주의) 재귀함수를 사용해야 하고, 효율적인 알고리즘(O(N))으로 풀어야 한다. > 아래처럼 단순 재귀함수를 사용하면 효율적이지 못하다. memoization을 활용하자.

- 문제: 두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴한다. 입출력 예시: 풀이: naive한 풀이는 이중 for문을 사용하거나 sample 요소 하나씩 indexOf를 사용하여 base 배열에 확인해 보면 되겠지만, 이는 모두 효율적인 방법이 아니다. > base와 sample 모두 요소의 숫자...

삽입정렬 삽입정렬 한 번에 한 항목 씩 정렬 된 배열을 작성한다. 1회전을 수행할 때마다 인덱스가 증가하며 해당 인덱스까지 요소들의 정렬이 끝난다. 시간 복잡도 최선의 경우 : O(N) 최악의 경우 : O(N^2) 평균 : O(N^2) 장점 안정적인 정렬 알고리즘이다. 배열이 대부분 정렬되어 있는...

- 문제 부분적으로 오름차순 정렬된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다. 부분적으로 정렬된 배열: 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열 예시: [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬됩...

- 문제 다음의 조건을 만족하면서 현재의 비밀번호('curPwd')를 새 비밀번호(newPwd)로 변경하는 데 필요한 최소 동작의 수를 리턴해야 합니다. 한 번에 한 개의 숫자만 변경가능하다. 4자리의 소수(prime)인 비밀번호로만 변경가능하다. 정리하면, 비밀번호가 계속 소수를 유지하도록 숫자 한 개씩을 바꿔갈 때 현재 비밀번호에서 새 비밀번호로 바꾸...

- 문제 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. Quick Sort (퀵 정렬) 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 > 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가...

- 문제 문자열을 입력받아 문자열 내의 모든 괄호의 짝이 맞는지 여부를 리턴합니다. 주의사항 괄호의 종류는 (, )만 고려합니다. 괄호는 먼저 열리고((), 열린만큼만 닫혀야()) 합니다. 빈 문자열을 입력받은 경우, true를 리턴해야 합니다. 입출력 예시 - 풀이 > stack을 이용했다는 점과 짝을 키와 값으로 설정해 두어 비교하는 식을 구현했...

- 문제: 길이가 m, n이고 오름차순으로 정렬되어 있는 자연수 배열들을 입력받아 전체 요소 중 k번째 요소를 리턴해야 합니다. 입출력 예시 - 풀이: > 하지만 위 풀이식은 O(K) 시간복잡도로 푼 것이지만, O(logK) 시간복잡도로 풀려면 이진탐색으로 풀어야 한다.

- 문제: 문자열을 입력받아 다음의 조건을 만족하는 LPS*를 찾아 그 길이를 리턴해야 합니다. 참고 LPS: 주어진 문자열의 가장 긴 접두어이자 접미어(Longest Prefix which is also Suffix) non-overlapping: 접두어와 접미어는 서로 겹치는 부분이 없어야 합니다. 다시 말해, prefix와 suffix는 문자열의 동...

- 문제: 아래와 같은 과정을 거쳐 부등호 수(inequalityNumber)를 만들 수 있습니다. 최대 9개의 부등호()가 주어집니다. 부등호의 좌우에는 0부터 9사이의 숫자가 한 번씩만 들어가야 합니다. 부등호를 만족하는 숫자의 조합을 차례대로 이어 붙여 만든 정수를 부등호 수라고 한다. 부등호 기호들을 입력받아 부등호를 만족하는 최대 부등호 수와 ...

- 문제: 정수를 요소로 갖는 배열을 입력받아 다음의 조건을 만족하는 LSCS*를 리턴해야 합니다. LSCS: 주어진 배열의 연속된 부분 배열*의 합을 구한다고 할 때, 이 중 가장 큰 값(Largest Sum of Contiguous Subarray) 연속된 부분 배열들: 배열 [1,2,3]의 연속 부분 배열은 [1], [1, 2], [1, 2, 3], ...

- 문제: 정수를 요소로 갖는 배열을 입력받아 이진 힙(binary heap)*을 리턴해야 합니다. - 참고: > * 이진 힙(binary heap)은 노드의 값이 특정한 순서를 가지고 있는 완전 이진 트리(Complete Binary Tree)입니다. 완전 이진 트