meteor_yeon

[이진 탐색]이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.데이터가 무작위일 떄는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징.이진탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있음.이진탐색의 위치 변수 3가지:1. 시작점, 2. 끝점, 3. 중간점→ 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 과정 [이미 정려로딘 10개의 데이터 중 값이 4인 원소 찾기] 전체 데이터 개수는 10개지만, 이진 탐색을 이용해 총 3번의 탐색으로 원소를 찾음이진탐색은 한번 확인 시마다 개수가 절반씩 줄어들어 시간 복잡도는 O(log N)임 [재귀함수로 구현한 이진 탐색 소스코드]# 이진 탐색 ..

[순차 탐색]리스트 안에 있는 특정한 데이터를 찾기 위해 아펭서부터 데이터를 하나씩 차례대로 확인하는 방법정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용됨. 리스트의 데이터에 하나씩 방문하여 특정한 문자열과 같은지 검사하는 로직순차탐색의 용처:1. 리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인2. 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할때도 내부에서 순차탐색 수행 [소스코드]# 순차탐색 소스코드 구현def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if a..

[문제]동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 한다.N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.예를 들어 N=5, K=3이고 배열 A와 B가 다음과 같다고 하자.배열 A = [1, 2, 5, 4, 3]배열 B = [..

[문제]N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오. [입력 조건]첫 번째 줄에 학생의 수 N이 입력된다. (1 두 번째 줄부터 N + 1 번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.[출력 조건]모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다.[입력 예시]2홍길동 95이순신 77 [출력 예시]이순신 홍길동 [문제 해설]학생의 정보가 최대 100,000개 까지 입력될 수 있으므로 ..

[문제]하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수 부터 작은 수의 순서로 정렬해야한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오. [입력 조건]첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다 (1 둘째 줄부터 N + 1 번째 줄까지 N개의 수가 입력된다. 수의 범위는 1이상 100,000이하의 자연수이다.[출력 조건]입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다. 동일한 수의 순서는 자유롭게 출력해도 괜찮다. [입력 예시]3152712 [출력 예시]27 15 12 [문제 해설]가장 기본적인 정렬을 할 수 있는지 물어보는 문제.파이썬의 기본 정렬 라이브러리를 이용하는 것이 효과적 [소스 코드]# N을 입력받..

[6-7 sorted() 함수]퀵 정렬과 비슷한 병합 정렬을 기반으로 만들어짐즉, sorted()알고리즘은 최악의 경우에도 O(NlogN)을 보장함array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]result = sorted(array)print(result) [6-8 sort() 함수]리스트 변수가 하나 존재할 때, 리스트 내부 원소를 바로 정렬.리스트 자체의 내장함수인 sort()를 이용하는 것.반환값은 내부 원소가 정렬되어 반환됨.array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]array.sort()print(array) [6-9 정렬 라이브러리에서 key를 활용]sorted()나 sort()를 이용할 때는 key 매개변수를 입력으로 받을 수 있음.key 값으로..

[계수 정렬]특정한 조건이 부합할 때만 사용할 수 있음. 매우 빠른 정렬 알고리즘.데이터의 개수가 N, 대아터 중 최대값이 K 일 때, 계수 정렬은 최악의 경우에도 수행시간O(N+K)를 보장한다.다만, '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용 가능함.일반적으로 가장 작은 데이터와 가장 큰 데이터가 1,000,000을 넘지 않을 때 효과적으로 이용 가능함.왜냐하면, 계수 정렬시 가장 큰 데이터를 담을 수 있는 범위의 리스트롤 선언해야하기 때문.배열 초기화시 가장 작은 데이터와 가장 큰 데이터의 차이가 1,000,000이라면, 1,000,001로 초기화 해야함.[시각화]계수 정렬은, 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성함. 아..

[퀵 정렬]정렬 알고리즘 중 가장 많이 사용되는 알고리즘."기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?"에서 시작퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작.퀵 정렬에는 피벗(Pivot)이 사용됨. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 말함.[시각화] 파트 1step 0) 리스트의 첫 번째 데이터를 피벗으로 설정하므로 피벗은 '5'이다. 이후에 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다. step 1) 그다음 다시 피벗보다 큰 데이터와 작은 데이터를 각각..

[삽입 정렬]데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입.즉, 삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬이라 함.선택 정렬에 비해 구현 난이도는 높으나, 실행 시간 측면에서 더 효율적.삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적임.삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정.정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤 에, 그 위치에 삽입된다는 점이 특징임.삽입정렬은 두 번째 데이터부터 시작한다. 첫 번째 데이터는 그 자체로 정렬되어있다고 판단하기 때문이다.step0) 첫 번째 데이터 '7'은 그 자체로 정렬되어있다고 판단하고, 두 번째..

[정렬 알고리즘 개요]정렬: 데이터를 특정한 기준에 따라서 순서대로 나열하는 것.정렬은 이진 탐색의 선행조건임. 이진 탐색을 위해선 정렬이 필수적으로 선행 되어야 함.선택, 삽입, 퀵, 계수 정렬 등이 있음. [선택 정렬]위와 같이 데이터가 무작위로 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.가장 원시적인 방법매번 '가장 작은 것을 선택'한다는 의미에서 '선택 정렬'이라고 함.[선택 정렬 시각화]step0) 초기 단게에서는 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다. 따라서 '0'을 선택해 맨 앞에 있는 데이터 '7'과 바꾼다. step1) 정렬된 첫 번째는 제..