최대 최소 찾기 선택 문제 주어진 리스트의 최대, 최소 값을 찾거나 n번째 큰 값, n번째 작은 값을 찾는 과정도 프로그램에서 많이 등장한다. 이렇게 n개의 숫자들 중 k번째로 작은(또는 큰) 값을 찾는 문제를 'Selection problem' 즉, 선택 문제 라고 한다. 최대 최소 찾기 선택 문제에서 가장 쉬운 문제가 최대 / 최소를 찾는 문제이다. 주어진 리스트의 최대값을 찾기 위해서는 어떤 방법을 사용하면 될까? 정렬 먼저, 이전에 배웠던 정렬을 이용할 수 있다. 정렬 후 리스트의 마지막 요소를 가져오면 최대값을 알 수 있기 때문이다. 하지만 중간 요소들의 정렬은 최대값을 찾는데에 불필요한 과정이다. 따라서 정렬을 이용하면 정렬의 최소 시간복잡도인 O(nlgn)로 문제를 해결할 수 있다. min/..

탐색 탐색은 주어진 자료들 중 원하는 조건에 해당하는 자료를 찾는 과정이다. 컴퓨터에서 탐색은 자주 이루어지므로 효율적인 방식으로 수행하는 것이 중요하다. 이전에 배웠던 '정렬'은 탐색을 수행할 수 있는 방법 중 하나이다. 정렬은 리스트를 하나의 기준으로 나타내기 위해서도 쓰이지만 원하는 자료를 빠르게 탐색하기 위해 쓰이기도 한다. 물론 굳이 정렬이 아니더라도 탐색을 수행할 수 있는 방법은 있다. 정렬 보기 앞으로 소개할 탐색은 다음의 4가지 종류이다. 선형탐색 이진탐색 해시탐색 BST 탐색을 위해서는 배열, 연결 리스트, 트리, 그래프 등 다양한 자료구조가 사용되며, 상황에 따라 맞춰서 사용하면 된다. 자료구조 보기 선형 탐색 순차 탐색이라고도 불리는 선형 탐색은 가장 간단한 탐색 방법이다. 선형 탐색..

BST BST(Binary Search Tree)는 트리의 한 종류이자 이진탐색을 위한 방법 중 하나이다. 과정 BST를 이용한 탐색에서는 다음과 같은 과정을 거친다. 이진 탐색 트리 만들기 (생성) 루트 노드에서 내려가면서 원하는 요소 찾기 (탐색) 삭제 및 삽입 하기 (삭제 / 삽입) 예시 먼저 이진 탐색 트리를 만들어보자. 이진 탐색 트리는 부모 노드를 기준으로 왼쪽 서브트리에는 더 작은 값의 노드가 오른쪽 서브트리에는 더 큰 값의 노드가 있어야한다. 따라서 요소를 하나씩 삽입하면서 알맞은 위치를 찾아주면 된다. 결과적으로 나온 이진 탐색 트리를 중위 순회하면 정렬된 리스트가 된다. 그 다음에는 루트 노드에서 내려가면서 원하는 요소를 찾고 삭제해보자. 원하는 요소는 6이다. 왼쪽 그림에서 오른쪽 그..

H-index 문제 https://programmers.co.kr/learn/courses/30/lessons/42747# 문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 제한사항 과학자가 발표한 논문의 수는 1편..

K번째 수 문제 https://programmers.co.kr/learn/courses/30/lessons/42748 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아..

퀵 정렬 개념 퀵 정렬의 세부과정은 다음과 같다. pivot이라는 요소를 선택한 후, pivot을 기준으로 왼쪽에는 pivot보다 작은 요소들을 놓고 오른쪽에는 pivot보다 큰 요소들을 놓는다. 이후 순환호출을 이용하여 재귀적으로 왼쪽, 오른쪽으로 분류해둔 요소들에 대해 전과 같은 과정을 반복한다. 위의 그림은 오른쪽 요소들에 대해 순환호출한 모습이다. 분할이 불가능할 때까지 반복하다보면 최소한의 요소로 나누어지고 이후 순서대로 결합을 진행한다. 위의 그림에서 색이 칠해져있는 요소들을 순서대로 합치면 된다. 퀵 정렬은 분할 정복 알고리즘 중 하나이다. pivot으로 2개의 부분 배열을 생성하는 분할(Divide) 과정과 부분 배열을 재귀적으로 호출하는 정복(Conquer) 과정과 정렬된 부분 배열을 합..

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

체육복 https://programmers.co.kr/learn/courses/30/lessons/42862# 문제 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 res..