알고리즘7 [알고리즘] 프로그래머스 - 해시 - 완주하지 못한 선수 출처: https://programmers.co.kr/learn/courses/30/lessons/42576/solution_groups?language=python3&type=all 문제 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 2.. 2019. 12. 4. [알고리즘] 삽입정렬, 인서션 소트 (Insertion Sort) 삽입정렬, 인서션 소트 (insertion Sort) i번째 인덱스의 값을 0부터 i-1번째의 값들 중 자신의 위치를 찾아 정렬을 완성하는 알고리즘. 처음 key값을 "두번째 값"부터 시작한다. 최선의 경우: O(n) 비교 회수: 이동없이 한번의 비교만 이루어진다. 외부 루프: (n-1)번 최악의 경우: O(n^2) 비교 회수: 외부 루프 안의 각 반복마다 i번의 비교 수행 교환 회수: 외부 루프의 각 단계마다 (i+2)번의 이동 발생 영상으로 보기 - Folk Dance Insert-sort with Romanian folk dance Python Code def insertion_sort(arr): arr_len = range(1, len(arr)) for i in arr_len: arr_sort_l.. 2019. 8. 8. [알고리즘] 선택정렬, 셀렉션소트 (Selection Sort) 선택정렬, 셀렉션소트 (Selection Sort) 1. 주어진 배열에서 최솟값을 찾아 맨 앞에 위치한 값과 SWAP한다. 2. 다음 수행시에 처음 위치의 값을 제외한 나머지 값들을 1번을 수행한다. 장점: 자료 이동 횟수가 미리 결정된다. 단점: 값이 같은 레코드가 있는 경우 상대적인 위치가 변경될 수 있다. 비교회수: 외부 루프: (n-1)번 내부 루프: n-1, n-2, ..., 2, 1번 교환회수: 외부 루프의 실행 회수와 동일 SWAP을 위한 3번의 이동이 필요 영상으로 보기 - Folk Dance Python Code def selection_sort(arr): arr_len = range(len(arr)) for i in arr_len: min_idx = i arr_sub_len = rang.. 2019. 8. 7. [알고리즘] 거품정렬, 버블 소트(Bubble sort) 거품정렬, 버블소트 (Bubble Sort) 인접한 두 원소를 비교하여 정렬하는 알고리즘. 두 원소의 순서가 정렬되어 있지 않을 경우 두 원소를 swap한다. 1회전 수행 후 가장 큰 값이 뒤로가므로 2회전 때는 맨 끝에 있는 자료는 정렬에서 제외한다. 비교회수: n-1, n-2, ..., 2, 1 번 = n(n-1)/2 교환회수: 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다. T(n) = O(n^2) 영상으로 보기 - Folk Dance Bubble-sort with Hungarian ("Csángó") .. 2019. 8. 6. [알고리즘] Extra Long Factorials 해커랭크 문제. Extra Long Factorials 링크: https://www.hackerrank.com/challenges/extra-long-factorials/problem Author: vatsalchanana Difficulty: Medium #!/bin/python3 import math import os import random import re import sys # Complete the extraLongFactorials function below. def extraLongFactorials(n): total = 1 while n > 1: total = total * n n -= 1 print(total) if __name__ == '__main__': n = int.. 2019. 7. 24. [알고리즘] Sherlock and Squares 해커랭크 문제. Sherlock and Squares 링크: https://www.hackerrank.com/challenges/sherlock-and-squares/problem Author: darkshadows Difficulty: Easy 문제 요약: a, b 포함 사이의 수중 제곱수의 개수를 찾아라. #!/bin/python3 import math import os import random import re import sys # Complete the squares function below. def squares(a, b): count = 0 import math n = a while n 2019. 7. 18. [알고리즘] 시간 복잡도, 공간 복잡도, 빅오(Big O) Big O 빅-오 표기법은 시간복잡도를 표현한는데 사용되며, 계수와 낮은 차수의 항을 제외시킨다. 예를 들어, 만약 크기 n의 입력에 대해 5n3 + 3n의 식을 가진다. 이 알고리즘의 점근적 시간 복잡도는 O(n3)이다. 크기 n의 입력에 대한 복잡도. O(1): Constant Time(상수 시간): 작업 수행을 위한 알고리즘은 단일 단계이다. O(log n): Logartirhmic time(Log 시간): 작업을 수행하는데 걸리는 단계가 시간이 지날 수록 (어떤 요인에 의해) 점차 줄어든다. O(n): Linear Time(선형 시간): 필요한 단계의 수는 직접적으로 관련이 있다. (1 대 1의 관계) O(n²): Quadratic Time(이차 시간): 작업을 수행하는데 걸리는 단계의 수가 n의.. 2019. 4. 9. 이전 1 다음
