개발자의시작

Merge Sort(병합 정렬) 병합 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나입니다. 아이디어 병합 정렬은 분할 정복 알고리즘을 사용한다. 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복은 일반적으로 재귀 호출을 사용하여 구현한다. 병합 정렬은 다음의 과정을 갖는다. 1. 분할: 입력 리스트를 같은 크기의 2개의 부분 리스트로 분할한다. 2. 정복: 부분 리스트를 정렬한다. 여기서 부분 리스트가 충분히 작지 않다면 재귀 호출을 통해 다시 분할 정복을 한다. 3. 결합: 정렬된 부분 리스트를 하나의 리스트로 병합한다. 병합 정렬 과정 - 추가적인 리스트가 필요하다. - 각 부분 리스트를 정렬할 때도 병합 정렬을 재..

Quick Sort(퀵 정렬) 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속합니다. 퀵 정렬은 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행속도를 보입니다. 분할 정복 알고리즘을 사용하는 병합 정렬(merge sort)와 다르게 퀵 정렬은 비균등하게 분할합니다. 아이디어 퀵 정렬은 위에서 언급한대로 분할 정복 알고리즘을 사용한다. 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한다음 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복은 일반적으로 재귀 호출을 사용하여 구현한다. 과정은 다음과 같다. 리스트에 있는 요소 하나를 선택한다. 이를 피벗(pivot)이라고 한다. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 문제 소스코드 #Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 from collections import deque def solution(priorities, location): queue=deque( [ [v,i] for i, v in enumerate(priorities)]) answer=0 while len(queue)..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 문제 소스코드 #Python 1 2 3 4 5 6 7 8 9 10 def solution(progresses, speeds): queue=[] for p, s in zip(progresses, speeds): if len(queue)==0 or queue[-1][0]

Insertion Sort(삽입 정렬) 삽입 정렬은 버블 정렬, 선택 정렬과 함께 가장 기본적인 정렬 알고리즘에 해당됩니다. 데이터를 처리하는 데 있어서 정렬은 가장 기본적이면서도 핵심적인 내용입니다. 선택 정렬을 살펴보기 전에 이전 포스팅에서 설명한 버블 정렬과 선택 정렬에 대해 먼저 이해하시면 선택 정렬을 이해하는데 도움이 될 겁니다. 아이디어 삽입 정렬의 아이디어는 데이터를 하나씩 확인하면서 자기 자리를 찾아 해당 위치에 삽입하는 것입니다. 데이터의 앞에서부터 순서대로 진행하며 자신의 앞에 있는 데이터와 비교하고 자신보다 작으면 스왑을, 크거나 같으면 다음 루프를 진행합니다. 이와 같은 과정을 계속해서 반복하면 데이터가 오름 차순으로 정렬이 되는 것을 확인할 수 있습니다. 아래에서 구체적인 알고리즘..

Selection Sort(선택 정렬) 선택 정렬은 버블 정렬, 삽입 정렬과 함께 가장 기본적인 정렬 알고리즘에 해당됩니다. 데이터를 처리하는 데 있어서 정렬은 가장 기본적이면서도 핵심적인 내용입니다. 선택 정렬을 살펴보기 전에 이전 포스팅에서 설명한 버블 정렬에 대해 먼저 이해하시면 선택 정렬을 이해하는데 도움이 될 겁니다. 아이디어 선택 정렬의 아이디어는 전체 데이터중 가장 작은 값을 앞으로 보내는 것입니다. 데이터의 앞에서부터 순서대로 선택하고 선택된 데이터의 뒤에 있는 데이터들 중 가장 값이 작은 데이터와 스왑(Swap)합니다. 이와 같은 과정을 계속해서 반복하면 데이터가 오름차순으로 정렬이 되는 것을 확인할 수 있습니다. 아래에서 구체적인 알고리즘과 코드를 살펴보겠습니다. 알고리즘 선택 정렬의 ..

Bubble Sort(버블 정렬) 버블 정렬은 삽입 정렬, 선택 정렬과 함께 가장 기본적인 정렬 알고리즘에 해당됩니다. 데이터를 처리하는 데 있어서 정렬은 가장 기본적이면서도 핵심적인 내용입니다. 아이디어 버블 정렬의 아이디어는 전체 데이터중 가장 큰 값을 맨뒤로 보내는 것입니다. 그렇기 때문에 버블 정렬의 전체 과정을 살펴보면 뒤에서부터 앞으로 정렬되는 과정을 보입니다. 전체 데이터 중 가장 값이 큰 데이터를 맨뒤로 보낸 후, 이미 정렬된 값을 제외한 데이터중 가장 값이 큰 데이터를 맨 뒤로 보냅니다. 이와 같은 과정을 계속해서 반복하면 데이터가 오름차순으로 정렬이 되는 것을 확인할 수 있습니다. 아래에서 구체적인 방법과 코드를 통해 알 수 있는데, 데이터를 비교하고 큰 값을 계속해서 뒤로 보내는데 이..

문제링크 https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 한수라는 개념이 생소하지만 브루트 포스(Brute Force) 즉, 주먹구구식으로 해결하면 쉽게 해결할 수 있는 문제입니다. 문제의 설명대로 한수는 정수 X의 각 자리가 등차수열을 이루는 경우를 의미합니다. 여기서 주의하실 것은 입력에 사용되는 N은 1000보다 작거나 같은 정수입니다. 즉, 1000은 한수가 아니며 1000보다 ..