성덕이의 개발공간

1. 문제 설명 H - index는 과학자의 생산성과 영향력을 나타내는 지표이다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 과학자의 H-index이다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때 H-index를 return 해라 2. 제한사항 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하 논문별 인용 횟누는 0회 이상 10,000회 이하 3. 입출력 예 citations return [3,0,6,1,5] 3 이 과학자가 발표한 논문의 수는 5편이다. (3, 0, 6, 1, 5) 그중 3편의 논문은 3회 이상 인용되었다. (3, 6, 5) 나머지 2편의 논문은..

1. 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내라. 예를들어 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고 가장 큰 수는 6210이다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 가장 큰 수를 문자열로 바꾸어 return하라. 2. 제한사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으므로 문자열로 바꾸어 return 합니다. 3. 입출력 예 array return [6, 10, 2] "6210" [3,30,34,5,9] "9534330"..

1. 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k 번째에 있는 수를 구하려한다. 예를 들어 array가 [1,5,2,6,3,7,4], i = 2, j = 5, k = 3이라면 1. array의 2번째부터 5번째까지 자르면 [5,2,6,3]이다. 2. 배열을 정렬하면 [2,3,5,6]이다. 3. 위 배열의 3번째(k)는 5이다. 배열 array, [i,j,k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때 return 구하라 2. 제한사항 array의 길이는 1 이상 100 이하 array의 각 원소는 1 이상 100 이하 commands의 길이는 1 이상 50 이하 commands의 각 원소는 길이가 3이다. 3. 입출력 예 array comm..

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체 A에 대하여 오름차순 정렬, B에 대하여 내림차순 정렬 각 배열의 첫 번째 인덱스부터 차례로 확인하면서 A원소가 B의 원소보다 작을 때만 교채 최악의 경우 O(NlogN)을 이용 4. 답안 N, K = map(int, input().split()) #N, K 동시에 입력 count = K result = 0 A_array = list(map(int, input().split())) B_array = list(map(int, input().split())) A_array.sort() B_array.sort(reverse = True) for i in range(N): fo..

선택 정렬 알고리즘 특징 키 값을 찾아서 비교한다. 구현이 매우 쉽다. 삽입 정렬 알고리즘 특징 데이터가 거의 정렬되어 있을 때 가장 빠르다. 자신의 위치를 찾아서 계속해서 삽입한다. 퀵 정렬 알고리즘 특징 Pivot 값을 정한 후 계속해서 정렬한다. 충분히 빠른 속도를 가진다. 계수 정렬 알고리즘 특징 데이터의 크기가 한정되어 있는 경우에만 사용한다. 그만큼의 배열, 리스트가 필요하다. 매우 빠른 속도를 가지고 있다.

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능 데이터의 개수(N), 데이터 중 최댓값(K)일 때, 최악의 경우에도 시간복잡도 O(N+K)를 가진다. 1. 계수 정렬 동작 예시 [Step 0] 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 리스트를 생성한다. 총 9개가 필요하다는 말! 여기서 인덱스는 특정 데이터의 값이랑 동일시 한다. [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2], 15개, min = 0, max = 9 [Step 1] 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다. 여기선 7이므로 7인덱스를 1증가시킨다. [Ste..

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다. 1. 퀵 정렬 동작 예시 [Step 0] 현재 Pivot 값은 5이다. 왼쪽에서는 Pivot값 보다 큰 데이터를 선택하고 오른쪽에서는 Pivot값 보다 작은 데이터를 선택한다. 왼쪽은 5보다 큰 7을, 오른쪽에서는 5보다 작은 4를 선택한다. 이제 두 데이터의 위치를 서로 변경한다. [Step 1] 현재 Pivot 값은 5이다. 왼쪽에서는 9는 Pivot보다 크므로 선택, 오른쪽에서는 2가 5보다 작으므로 2를 선택 9와 2의 데이터 위치를 서로 변경한다. [Step 2] 9와 2의 위치가 바뀌었다. 왼쪽에서는 Pivot보다 큰 값을 다시 찾는다. 6을 발견하는데 이때 1..

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 데이터를 하나하나씩 확인 선택 정렬에 비해 난이도가 높지만 더 효율적 1. 삽입 정렬 동작 예시 [Step 0] 7은 그 자체로 정렬되어 있다고 판단하고 이 다음 데이터인 5가 어떤 위치로 들어갈지 판단한다. 7보다 작으면 7의 왼쪽(파란색 화살표) 7보다 크면 7의 오른쪽(회색 화살표) 로 들어간다. 5는 7보다 작으므로 왼쪽으로 들어갈 것이다. [Step 1] 5가 7의 왼쪽으로 삽입되었다. 다음으로 9가 어떤 위치로 들어갈지 판단한다. 9는 7보다 작으면 왼쪽으로 갔을 것이고 또 5보다 작았으면 왼쪽으로 갔을 것이다. 여기서는 7보다 크므로 그자리에 그대로 있는다. [Step 2] 그다음 위치에 있는 0을 비교한다. 0은 그 앞 수들보다 모두 ..

정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 선택 정렬이란 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 행위 1. 선택 정렬 동작 예시 [Step 0] 처리되지 않은 데이터 중 가장 작은 '0'을 선택해 가장 앞의 '7'과 바꾼다. [Step 1] 이렇게 [Step0]에서 '0'이 '7'과 자리가 바뀐것을 알 수 있다. 처리되지 않은 데이터 중 가장 작은 '1'을 선택해 가장 앞의 '5'와(0은 바꿨으므로 무시) 바꾼다. [Step 2] 처리되지 않은 데이터 중 가장 작은 '2'를 선택해 가장 앞의 '9'와 바꾼다. [Step 3] 처리되지 않은 데이터 중 가장 작은 '3'을 선택해 가장 앞의 '7'과 바꾼다. 최종적으..