코딩 기록 저장소

1. 평균 선형 시간 선택 알고리즘 - 퀵 정렬처럼 분할한 후 자기호출 방법을 쓰면 평균적으로 선형 시간에 i번째 작은 원소를 찾을 수 있음. 그렇지만 이 알고리즘은 최악의 경우 O(n²) 시간이 소요됨. - 이번 알고리즘은 단점을 개선해서 최악의 경우에도 선형 시간에 i번째 작은 원소를 찾을 수 있게 함. - n개의 원소가 규칙 없이 저장된 배열에서 i번째 작은 원소를 찾으려 함. - 분할 알고리즘이 리턴하는 값으로 기준 원소가 전체에서 몇 번째 작은 원소인지 알 수 있음. - 기준원소가 전체에서 k번째 작은 원소란 사실을 알면, i와 k의 값을 비교해서 작으면 왼쪽 그룹에 있는 원소 중 하나이고, 같으면 기준 원소가 바로 i번째 작은 수이고, 크면 i 번째 작은 수는 오른쪽 그룹에 있는 원소 중 하나..

문제 정보 제목 : n^2 배열 자르기 난이도 : Lv.2 사용 언어 : Python 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/87390 문제 설명 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[rig..

문제 정보 제목 : 튜플 난이도 : Lv.2 사용 언어 : Python 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/64065 문제 설명 셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다. (a1, a2, a3, ..., an) 튜플은 다음과 같은 성질을 가지고 있습니다. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2) 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2) 튜플의 원소 개수는 유한합니다..

1. 기본적인 정렬 알고리즘 선택 정렬 - 선택 정렬은 원리가 간단한 정렬 알고리즘 중 하나. - 배열 A[1~n]에서 가장 큰 원소를 찾아 이 원소와 배열의 끝자리에 있는 A[n]과 자리를 바꿈. - 맨 뒷자리로 옮긴 가장 큰 원소는 제외하고 나머지 원소들로 같은 작업을 반복함. selectionSort(A[],n) { ① for last

1. 점화식 - 점화식은 어떤 함수를 자신과 똑같은 함수를 이용해 나타내는 것. - 동일한 함수가 등호나 부등호의 양쪽에 나타나는데, 양쪽 함수는 변수의 크기가 다를 뿐임. - n!의 점화식은 f(n)=n * f(n-1) - 피보나치 수열의 점화식은 f(n) = f(n-1) + f(n-2) - 점화식은 재귀 함수의 복잡도를 구하는 데 유용함. 자기 호출을 사용하는 알고리즘은 매우 흔함. - 명시적으로 자기호출을 사용하지 않더라도 그 속에서 자신과 똑같지만 크기가 다른 문제를 발견할 수 있는 경우도 있음. - 재귀적 관계를 이용해 알고리즘의 수행 시간을 점화식으로 표현할 수 있음. mergeSort(A[], p, r) // A[p ~ r]을 정렬함 { ① if ( p < r ) then { ② q

문제 정보 제목 : 위장 난이도 : Lv.2 사용 언어 : Python 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42578 문제 설명 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. ..