코르시카's Blog

참고 : debuglog.tistory.com/67 Python으로 알고리즘 공부 02. 퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort) 파이썬으로 구현 퀵 정렬은 분할 정복 알고리즘의 좋은 예이다. 리스트 중 하나를 pivot으로 정하고, pivot보다 작은 아이템은 왼쪽, pivot보다 큰 아이템은 오른쪽으로 보내면서 pi debuglog.tistory.com ■ 퀵 소트 1) 정의 : 분할정복을 사용하여 piviot 값을 기준으로 하여 좌, 우를 나누어 정렬하는 방식 > (꼭 그래야 하는 것은 아니지만) piviot 보다 작은 아이템은 왼쪽, 큰 아이템은 오른쪽 > pivot은 랜덤 값이 제일 적당 ...OR... 평균에 가까운 수 > 재귀 형식 사용 : 점화식의 형태 2) 복잡도 ..

■ 일반적 알고리즘의 시간복잡도 시간 복잡도 worst 시간 복잡도 least for문 1 / while문 1 당== iteration O(N) python sorting O(N*log(N)) ■ python list Operation Example Big-O Notes Index l[i] O(1) Store l[i] = 0 O(1) Length len(l) O(1) Append l.append(5) O(1) Pop l.pop() O(1) l.pop(-1) 과 동일 Clear l.clear() O(1) l = [] 과 유사 Slice l[a:b] O(b-a) l[:] : O(len(l)-0) = O(N) Extend l.extend(…) O(len(…)) 확장 길이에 따라 Construction list..

참조: velog.io/@jahoy/%EC%8B%A4%EC%9A%A9%EC%A0%81%EC%9D%B8-Python-%EB%94%94%EC%9E%90%EC%9D%B8-%ED%8C%A8%ED%84%B4-%EC%A0%95%EB%A6%AC 실용적인 Python 디자인 패턴 정리 Mastering Python Design Patterns을 읽고 정리한 글입니다. velog.io www.fun-coding.org/PL&OOP2-2.html 파이썬과 객체지향 프로그래밍: 디자인 패턴 - 잔재미코딩 간단히 개념만! 어떤 객체는 하나만 만들면 되는 객체가 있음 - 예: 데이터베이스를 연결하고, 데이터베이스를 제어하는 인터페이스 객체 보통 프로그램은 여러 파일로 구현합니다. 각 파일에서 www.fun-coding.org ..

참조 : programmers.co.kr/learn/courses/4008/lessons/13173 programming119.tistory.com/196 [Python] bisect 사용법👀 / 이분탐색 / 코딩테스트 bisect 는 이진 탐색을 쉽게 구현하게끔 해주는 함수입니다. 이진 탐색은 직접 코드로도 구현할 수 있지만, bisect 함수를 이용하여 구현 시간을 줄이고 편하게 사용할 수 있습니다. 예제 [0, 1, 2, 3, 4 programming119.tistory.com 파이썬을 파이썬답게 - 이진 탐색하기 - binary search 본 강의는 파이썬 문법을 이미 알고 있는 분들을 대상으로 만들어졌습니다. ##### 이런 분들께 추천합니다 * 파이썬 문법을 알고 계시는 분 * 알고리즘 문제..

■ 동적계획법, (aka. DP) - 입력 크기가 작은 부분 문제들을 해결한 후, 해당 문제의 해를 활용해서 큰 부분 문제를 해결 ( bottom to up-towards solution ) - 이 과정에서 Memoization을 이용, 계산 결과가 저장되는 형식을 채택해 전체 실행 속도를 높임 - 최종 해를 구하는 과정에서 greedy 방식이 사용되는 경우도 많음 ■ 예시 1) Fibonacci 예시 1 def fibo_dp(num): cache = [ 0 for index in range(num + 1) ] cache[0] = 0 cache[1] = 1 for index in range(2, num + 1): cache[index] = cache[index - 1] + cache[index - 2] ..

문제 2017년 카카오 코테 문제(?) 직사각형을 만드는 데 필요한 4개의 점 중 3개의 좌표가 주어질 때, 나머지 한 점의 좌표를 구하려고 합니다. 점 3개의 좌표가 들어있는 배열 v가 매개변수로 주어질 때, 직사각형을 만드는 데 필요한 나머지 한 점의 좌표를 return 하도록 solution 함수를 완성해주세요. 단, 직사각형의 각 변은 x축, y축에 평행하며, 반드시 직사각형을 만들 수 있는 경우만 입력으로 주어집니다. 제한사항 ▶ v는 세 점의 좌표가 들어있는 2차원 배열입니다. ▶ v의 각 원소는 점의 좌표를 나타내며, 좌표는 [x축 좌표, y축 좌표] 순으로 주어집니다. ▶ 좌표값은 1 이상 10억 이하의 자연수입니다. ▶ 직사각형을 만드는 데 필요한 나머지 한 점의 좌표를 [x축 좌표, y..

https://www.fun-coding.org/Chapter14-dp_divide.html 파이썬과 컴퓨터 사이언스(기본 알고리즘): 동적 계획법과 분할 정복 - 잔재미코딩 프로그래밍 연습 피보나치 수열: n 을 입력받아서 다음과 같이 계산됨 n 을 입력받았을 때 피보나치 수열로 결과값을 출력하세요 함수를 fibonacci 라고 하면, fibonacci(0):0 fibonacci(1):1 fibonacci(2):1 fibon www.fun-coding.org https://www.fun-coding.org/Chapter13-recursive.html 파이썬과 컴퓨터 사이언스(기본 알고리즘): 재귀 용법 (Recursive Call) - 잔재미코딩 프로그래밍 연습 숫자가 들어 있는 리스트가 주어졌을 때,..

문제 https://programmers.co.kr/learn/courses/30/lessons/42627?language=python3 소요시간 40~50분, 옛날에 한번 봤던 문제라 조금 수월 너무 이쁘게(?) 구현하려고 조금 삽질 해결이 먼저다 코드 import heapq def solution(jobs): q = [] for j in jobs: heapq.heappush(q, (j[0], j[1])) # 요청시간, 작업시간 now = 0 n = 0 # completed elpsTime = 0 # total time used for disk op while n now : now += 1 continue # next iteration tmp_heap = ..