728x90 반응형 전체 글163 알고리즘 성능 측정의 지표 - 빅오 표기법(Big-O Notation) 빅오 표기법 알고리즘의 성능을 측정하기 위한 가장 중요한 지표로 빅오 표기법이 존재한다. 빅오 표기법으로 시간 복잡도와 공간 복잡도를 계산할 수 있는데, 우선 빅오 표기법이 뭔지부터 알아보자. 위의 그래프가 빅오 표기법을 나타낸 그래프이다. 빅오 표기법은 크게 아래의 7가지로 나눌 수 있다. O(1) O(logN) O(N) O(NlogN) O(N^2) O(N^3) O(2^N) 빅오 표기법이란 간단히 설명해서 O() 괄호 안에 원하는 식을 집어 넣는다. 그리고 식의 계수는 다 떼어 버린다. 왜냐하면 10000000000N이 아무리 크다 하더라도 N이 극한에 가까워지게 되면 결국 N^2보다 작아지는 순간이 오기 때문이다! 그렇게 해서 어떤 식이 더 규모가 큰 식인지를 빅오 표기법으로 구분하는 것이다. O(1.. 2023. 5. 18. 백준 2667 #2 재귀함수를 사용한 두 번째 풀이. 코드 길이 단축. def dfs(x, y): global count if x = N or y = N or grid[x][y] == 0: return grid[x][y] = 0 # 방문한 집은 0으로 표시 count += 1 dfs(x-1, y) # 상 dfs(x+1, y) # 하 dfs(x, y-1) # 좌 dfs(x, y+1) # 우 N = int(input()) grid = [list(map(int, input().strip())) for _ in range(N)] counts = [] for i in range(N): for j in range(N): if grid[i][j] == 1: count = 0 dfs(i, j) coun.. 2023. 5. 17. 완전탐색(Brute Force)과 백트래킹(Backtracking)의 차이 완전탐색(Brute Force) 1) 탐색 순서 브루트포스는 가능한 모든 해를 순차적으로 검사하는 방식이다. 모든 경우의 수를 하나씩 시도하여 정답을 찾을 때까지 모든 경우를 확인한다. 즉, 문제 공간의 모든 가능성을 전부 조사하는 방식이다. 2) 제약 조건 브루트포스는 문제의 제약 조건을 고려하지 않고 모든 가능한 해를 탐색한다. 제약 조건에 따라 해의 개수가 많아질 수 있다. 3) 탐색 중단 브루트포스는 모든 가능한 해를 탐색해야 하므로, 정답을 찾지 못하더라도 모든 경우를 검사한다. 따라서 실행 시간이 길어질 수 있다. 백트래킹(Backtracking) 1) 탐색 순서 백트래킹은 탐색 도중 불필요한 부분을 가지치기하여 탐색 공간을 줄인다. 유망한 후보 해를 따라가다가 더 이상 진행할 수 없는 상황에.. 2023. 5. 17. 백준 2798 #2 두 번째 풀이 시간은 아니지만 코드 길이는 단축되었다. import itertools a = list(map(int, input().split())) b = list(map(int, input().split())) combinations = itertools.combinations(b, 3) answer=[] for c in combinations: temp = 0 for n in range(3): temp += c[n] answer.append(temp) answer2=[] for n in answer: if n 2023. 5. 17. 백준 10819 #2 2번째 풀이 시간과 코드 길이 모두 단축되었다. import itertools a = int(input()) b = list(map(int, input().split())) permutations = itertools.permutations(b) answer = [] for p in permutations: temp_sum = 0 for n in range(1, a): ans = abs(p[n-1] - p[n]) temp_sum += ans answer.append(temp_sum) max_sum = max(answer) print(max_sum) 2023. 5. 17. 파이썬 순열/조합/중복조합 파이썬에서 경우의 수(조합, 순열)를 계산하기 위해 itertools 모듈을 활용할 수 있습니다. 이 모듈은 순열(permutations), 조합(combinations), 조합 중복을 포함한 다양한 경우의 수 계산 기능을 제공합니다. itertools 모듈을 사용하려면 먼저 모듈을 import 해야 합니다: import itertools 순열(Permutations): 순열은 원소들의 순서에 따라 가능한 모든 경우의 수를 생성합니다. itertools.permutations() 함수를 사용하여 순열을 생성할 수 있습니다. 함수에는 원소들을 포함한 iterable 객체와 원소의 개수(선택적)를 전달합니다. import itertools # 순열 생성 예시 items = [1, 2, 3] permutati.. 2023. 5. 17. 이전 1 ··· 17 18 19 20 21 22 23 ··· 28 다음 728x90 반응형
