반응형 『 Python 』/Python 문제해결능력6 [5] Python 문제해결 - 정렬 2 [선택 정렬] 셀렉션 알고리즘 > 저장되어 있는 자료로부터 K번째로 큰 혹은 작은 원소를 찾는 방법 > 최소값, 최대값 혹은 중간값을 찾는 알고리즘을 의미하기도 함. 선택 과정 1. 정렬 알고리즘을 이용하여 자료를 정렬 2. 원하는 순서에 있는 원소 가져오기. k번째로 작은 원소를 찾는 알고리즘 > 1번부터 k번째까지 작은 원소들을 찾아 list의 앞쪽으로 이동시키고, List의 k번째를 반환 > k가 비교적 작을 때 유용하며 O(kn)의 수행시간을 필요로 한다. def select(list, k): for i in range(0, k ): minIndex = i for j in range(i+1, len(list)): if list[minIndex] > list[j]: minIndex = j list[i], list.. 2020. 1. 5. [4] Python 문제해결 - List 2 검색 검색 : 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 목적하는 탐색키를 가진 항목 탐색키 : 자료를 구변하여 인식할 수 있는 키 검색의 종류 순차검색, 이진 검색, 인덱싱 순차검색 일렬로 되어 있는 자료를 순서대로 검색하는 방법 List나 연결 List 등 순차구조로 구현된 자료구조에서 유용하다. 구현이 쉽지만, 검색 대상이 많은 경우 수행시간의 증가로 비효율적이다. 2가지 경우 - 정렬된 경우와 정렬되지 않은 경우 1. 정렬되지 않은 경우 1) 첫번째 원소부터 순서대로 검색대상과 키 값이 같은 원소가 있는지를 비교하여 찾음 2) 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환 3) 검색 대상을 찾지 못하면 실패함. > 첫 번째 원소를 찾을 때에는 1번 비교 > 두 번째 원소를 찾을 때에는.. 2020. 1. 5. [3] Python 문제해결 - List 2 2차원 List 구조 1. 1차원 List를 묶어놓은 List 2. 2차우너 이상으 ㅣ다차원 List는 차원에 따라 index를 선언 3. 2차원 List의 선언 : 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 함. list 초기화 원소를 직접나열하기 arr = [0,0,0,0,0] arr = [0]*5 arr = [ i for i in range(2,9) if i i%2==0] --> 2 4 6 8 2차원도 동일하다. 2차원 List 입력받기 1. n, m = map(int, input().split()) mylist = [0 for _ in range(n)] # my list = [0] *n for i in range(n): mylist[i] = list(map(int,input().spli.. 2020. 1. 5. [2] Python 문제해결 - 정렬 버블 정렬 : 인접한 두개의 원소를 비교하며 자리를 계속 교환하는 방식 정렬 과정 1. 첫 번째 원소부터 ㅇ니접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동 2. 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬된다. 3. 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품모양 같아서 버블 정렬이라고 한다. def BubbleSort(a) : for i in range(len(a)-1, 0, -1) for j in range(0,i): if a[j] > a[j+1]: a[j], a[j+1] = a[j+1],a[j] 카운팅 정렬 : 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 .. 2020. 1. 5. [0] Python 문제해결 알고리즘이란? 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법을 말함. 1. 컴퓨터용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법 2. 어떠한 문제를 해결하기 위한 절차 알고리즘 표현법 1. 슈도코드 특정 프로그래밍 언어의 문법을 따라 쓰여진 것이 아니라. 일반적인 언어로 코드를 흉내 내어 알고리즘을 써놓은 코드 > 의사 코드로 흉내만 내는 코드이다. > 실제적인 프로그래밍 언어로 작성된 코드처럼 컴퓨터에서 실행할 수 없다. > 특정 언어로 프로그램을 작성하기 전에 알고리즘을 대략적으로 모델링하는 데에 쓰인다. 2. 순서도 프로그램이나 작업의 진행 흐름을 순서에 따라 여러 가지 기호나 문자로 나타낸 도표 > 흐름도, 프로그램의 논리적인 흐름 데이터의 처리 과정을 표현하는 데 사용한다... 2020. 1. 5. [1] Python 문제해결 - List 1. 완전검색 Exhaustive Search : 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법. > 경우의 수가 작을 때 유용하다. > 완전검색으로 접근하여 해답을 도출한 후 성능 개선을 위해 다른 알고리즘을 사용하는게 좋음. 경우의 숫자들을 모두 나타내준다. 2. 탐욕 알고리즘 Greedy Algorithm : 최적의 해를 구하는데 사용되는 근시안적인 방법 : 여러 경우 중 하나를 결정해야 할때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식 수행 과정 A. 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤 이를 부분 해 집합에 추가함 B. 실행 가능성 검사 : 새로운 부분 해 집합이 실행 가능한지를 확인 즉 : 문제의 제약 조건을 위반하지 않는지를 검.. 2019. 11. 5. 이전 1 다음 반응형 더보기 더보기 더보기 더보기
