728x90 단계별로풀어보기4 [python] 단계별로 풀어보기 - 12단계 계수 정렬 / 카운팅 정렬 시간 복잡도 : O(n+k) (k는 데이터의 최댓값) => 속도가 엄청 빠름. 퀵 정렬, 힙 정렬, 합병 정렬의 평균 시간 복잡도 => O(nlogn) 정렬 방법: 데이터가 몇번 나왔는지 count -> 받은 수가 몇 번 들어왔는지 빈도 계산 -> 등장 횟수를 누적 합으로 바꾸기 -> 입력받았던 정렬할 배열을 뒤에서 앞으로 순회하면서 정렬된 배열에 넣기. (넣어준 뒤에는 누적합 -1 해주기) 정리: 시간 복잡도는 훨씬 유리하지만, 엄청난 메모리 낭비를 야기할 수 있음. (배열에 포함된 최댓값 만큼 메모리가 필요함) 따라서, k가 엄청 크다면 차라리 퀵정렬, 힙 정렬, 합병 정렬을 쓰는 것이 나음. 또한, 데이터 값이 정수라는 전제가 있어야한다. 순서대로 정렬을 해 주는데.. 2021. 5. 10. [python] 단계별로 풀어보기 - 11단계 브루트 포스 알고리즘(완전 탐색 알고리즘): 가장 간단한 알고리즘. 모든 경우의 수를 검사 하나하나 다 검사하다보니 시간적인 측면에서는 비효율적이지만 정확도가 100%임. 암호학에서는 가장 확실한 방법으로 통용 (ex) 숫자로만 구성된 4자리수 비밀번호를 풀 때, 0000 ~9999까지 모두 입력해보는 것) + 만들기 쉬운 알고리즘 + 문제의 복잡도에 매우 민감 11-1) 백준 2798번: 블랙잭 arr =[] a, b = map(int, input().split()) arr = list(map(int, input().split())) result = 0 for i in range(a): for j in range(i+1, a): for k in range(j+1, a): if arr[i] + a.. 2021. 5. 6. [python] 단계별로 풀어보기 - 10단계 전반적으로 풀이과정이 거의 유사하다 재귀함수에 대한 문제인데, 재귀함수는 정의 단계에서 자신을 재참조하는 함수이다. 그래서 식에 맞게 함수만 잘 선언해주면 바로 해결할 수 있는 단계! 10-1) 백준 10872번: 팩토리얼 def factorial(num): if num == 0: return 1 return num*factorial(num-1) n = int(input()) print(factorial(n)) n! = n*(n-1)*(n-2)*(n-3) ... 10-2) 백준 10870번: 피보나치 수5 def fibonacci(num): if num == 0: return 0 elif num == 1: return 1 return fibonacci(num-1)+fibonacci(num-2) n = .. 2021. 5. 1. [python] 단계별로 풀어보기 - 7단계 쉬운 문제는 쉬웠고 몇몇 문제는 조금 생각해야하는 문제들로 이루어진 단계! 7-1) 백준 11654번: 아스키 코드 a = input() print (ord(a)) 문자열을 아스키코드로 반환: ord() 아스키코드를 문자열로 반환: chr() 7-2) 백준 11720번: 숫자의 합 a = input() b = list(map(int, input()))//수 하나하나를 리스트에 저장 print(sum(b))//리스트 속에 있는 수들 합 7-3) 백준 10809번: 알파벳 찾기 a = input() result = list(range(97,123)) for i in result: print(a.find(chr(i)), end = ' ') chr함수를 사용해서 아스키코드를 문자열로 반환하고, find함수를 사.. 2021. 4. 29. 이전 1 다음 728x90
