반응형

알고리즘 42

[알고리즘] 파이썬으로 힙 정렬 구현하기 :: heap sort in python

파이썬으로 힙 정렬(heap sort) 구현하기 힙 정렬(Heap sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 본 포스팅에서는 최소힙으로 오름차순 정렬을 구현해보겠다.내림차순은 아래 코드에서 부등호방향만 반대로 바꾸면 된다. 123456789101112131415161718192021222324252627def heapify(li, idx, n): l = idx * 2; r = idx * 2 + 1 s_idx = idx if (l li[l]): s_idx = l if (r li[r]): s_idx = r if s_idx != idx: li[idx], li[s_idx] = li..

[알고리즘] 파이썬으로 병합 정렬 구현하기 :: merge sort in python :: bottom up 방식

파이썬으로 bottom-up 방식 merge sort 구현하기 1. merge sort란? 합병정렬/병합정렬은 반씩 분할해서 다시 합치면서 정렬하는 방식이다. https://ko.wikipedia.org/wiki/합병_정렬#/media/파일:Merge-sort-example-300px.gif 2. merge sort in python 이를 python3에서 구현하면 다음과 같다. 123456789101112131415161718192021# merge sortdef merge(left, right) : v=list() i=0;j=0 while(i merge_sort([0, 5, 7, 6, 1, 2, 8, 3, 4, 9]) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] input으로 들어간 10개..

[알고리즘] 파이썬으로 거품정렬 구현하기 :: bubble sort in python

파이썬으로 bubble sort 구현하기 1. bubble sort란? 거품 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간복잡도는 \(O(n^2)\) 으로 상당히 느리지만 구현이 쉽다는 장점이 있다. 2. bubble sort in python 이를 python3에서 구현하면 다음과 같다. 12345678# bubble sortdef bubble(v) : l = len(v) for i in range(l-1): for j in range(l-i-1) : if v[j]>v[j+1] : v[j+1], v[j] = v[j], v[j+1] return vColored by Color Scriptercs * bubble sort 예시 > bubble([5,4,3,2,1])[1, 2, 3, 4, 5] ..

[백준] 2798번 : 블랙잭 in python 파이썬 코드 & 설명

파이썬으로 백준 2798번 블랙잭 풀기 https://www.acmicpc.net/problem/2798 코드 12345678910n, m = map(int,input().split())v = list(map(int, input().split()))s = list()for i in range(len(v)) : for j in range((i+1), len(v)) : for z in range((j+1),len(v)) : s.append(sum([v[i],v[j],v[z]]))s = [i for i in s if i0 : print(max(s))cs 모든 경우의 수를 다 구한 다음, 해가 존재할 때 출력한다. 파이썬이 아닌 다른 코드로는 재귀로 풀던데, 백준에서 파이썬은 재귀로 풀면 항상 런타임 에러가 난다.

[백준] 1002번 : 터렛 in python 파이썬 코드 및 설명

파이썬으로 백준풀기 : 1002번 터렛 https://www.acmicpc.net/problem/1002 코드 12345678n = int(input()) for i in range(n) : x1, y1, r1, x2, y2, r2 = map(int, input().split()) r = ((x1-x2)**2 + (y1-y2)**2)**(1/2) R = [r1,r2,r] m=max(R); R.remove(m) print(-1 if (r==0 and r1==r2) else 1 if (r == r1+r2 or m==sum(R)) else 0 if (m > sum(R)) else 2)cs 코드설명 총 네 가지 경우의 수가 있다. (두 원의 중점 사이의 거리를 r이라 하자.) -1 : 두 원이 일치하는 경우r=..

[백준] 9020번 : 골드바흐의 추측 in 파이썬 쉽게 풀어보기

백준 9020 골드바흐의 추측 in python https://www.acmicpc.net/problem/9020 코드 12345678910111213141516171819202122# n이하의 숫자들 중 소수 찾기def prime_list(n): sieve = [True] * n m = int(n ** 0.5) for i in range(2, m + 1): if sieve[i] == True: for j in range(i+i, n, i): sieve[j] = False return [i for i in range(2, n) if sieve[i] == True] # n이하의 소수들 중 합이 ndef sosu(n): li=prime_list(n) idx = max([i for i in range(len(..

[백준] 3053번 : 택시 기하학 in 파이썬 쉽게 풀어보기

백준 3053 택시 기하학 in python 쉽게 풀어보기 코드 1234import mathr=int(input())print(r*r*math.pi)print(r*r*2)cs 코드설명 이 문제는 유클리드 기하학에서의 원과 택시 기하학에서의 원만 알면 쉬워진다. 즉, 유클리드 기하학에서의 원의 넓이은 원래 알던 식 그대로 pi*R^2 이고, 택시 기하학에서는 밑변의 길이와 높이가 R인 삼각형 네 개의 넓이를 구하면 된다.

반응형