무작정 따라해보기(정리, 문제풀기)/어서와! 자료구조와 알고리즘은 처음이지? (5) 썸네일형 리스트형 선형탐색, 이진탐색(python) 탐색 선형탐색 또는 순차탐색 리스트의 앞에서부터 뒤로 하나씩 조사하면서 값을 탐색 리스트의 마지막 인덱스보다 i가 작으면서 리스트의 i방 값이 찾고자 하는 값이 아니면 계속 1을 증가시킨다. 찾고자 하는 값이면 그냥 바로 나와서 그 인덱스를 리턴해준다. 찾고자 하는 값이 리스트 안에 없다면 i는 리스트의 길이와 같아지므로 -1을 리턴한다.(원하는 값이 없다.) 리스트의 길이에 비례하는 시간이 소요됨 시간복잡도 : O(n) def linear_search(L, x): i = 0 while i < len(L) and L[i] != x: i+=1 if i < len(L): return i else: return -1 이진 탐색 탐색하려는 리스트가 정렬되어있을 때만 적용 가능 맨 처음, 맨 마지막의 중간 인덱스.. 정렬(python) 리스트의 정렬 python의 정렬 함수나 리스트의 메서드는 기본적으로 오름차순으로 설정되어있습니다. 만약 내림차순으로(반대로 정렬) 정렬하려면 reverse=True로 설정하시면 됩니다.( ex: sorted(L, reverse=True), L.sort(reverse=True) ) 리스트의 정렬 함수와 메서드 sorted(), sort() sorted(리스트) 내장 함수, 정렬된 새로운 리스트를 얻어냄 리스트.sort() 리스트의 메서드, 해당 리스트를 정렬함 문자열이 들어있는 리스트의 정렬 사전 순서(알파벳 순서)에 따라 정렬이 됨 대문자가 우선적으로 정렬이 됨 문자열 길이 순서의 오름차순으로 정렬하려면? key를 이용 ex: sorted(L, key=lambda x: len(x)) 이진탐색(python 코드) "어서와! 자료구조와 알고리즘은 처음이지?" 강의의 이진탐색 실습의 코드 def solution(L, x): answer = -1 upper = len(L)-1 lower = 0 while lower x: upper = middle-1 elif L[middle] < x: lower = middle+1 elif L[middle] == x: answer = middle break return answer 이 리스트는 정렬이 되어있다. 그렇기 때문에 이진탐색을 할 수 있다. lower가 upper보다 커질 때까지 반복한다. 만약 x가 리스트에 없다면 이 while문을 끝까지 돌 것이다.(x값이 없어서 lower가 upper보다 커지면) 그럼 결국 answer에는 -1의 값이 들어간다. 그리고 lower, up.. 리스트에서 원소 찾아내기(python 코드) "어서와! 자료구조와 알고리즘은 처음이지?" 강의의 리스트에서 원소 찾아내기 문제를 풀고 고치는 과정을 기록합니다. def solution(L, x): answer = [] for i in range(len(L)): if x == L[i]: answer.append(i) if len(answer)==0: answer.append(-1) return answer 일단 처음에는 for문 돌면서 x와 비교를 하면서 인덱스를 넣어주고 길이가 0, 즉 아무것도 들어오지 않았으면 리스트에 -1만을 넣어주는 방식으로 풀었어요. 처음에는 이렇게 풀었는데 힌트를 참고하여 다시 풀어보기로 했어요! def solution(L, x): answer = [] if x in L: for i in range(len(L)): if .. 정렬된 리스트에 원소 삽입하기(python 코드) "어서와! 자료구조와 알고리즘은 처음이지?" 강의의 정렬된 리스트에 원소 삽입 문제를 풀고 고치는 과정을 기록합니다. def solution(L, x): cnt = 0 for i in range(len(L)): if L[i] > x: L.insert(i, x) cnt+=1 break if cnt == 0: L.append(x) return L 제 처음 코드입니다. x값을 넣지 못하면 마지막에 값이 들어가게 한다는 그런 코드를 짰습니다. 근데 이렇게 보다는 맨 마지막의 값이 x보다 작다면 맨 뒤에 넣어주고, 그렇지 않다면 for문을 돌면서 x보다 더 큰 값의 자리에 넣어줘서 정렬을 하는 방법이 나을 것 같다고 생각했습니다. def solution(L, x): if x > L[-1]: L.append(x) .. 이전 1 다음