분류 전체보기243
[알고리즘] Quick sort는 왜 빠를까? (3) : 비교 실행의 개수 계산
비교의 수 가 곧 시간이다 전 게시물까지 내린 결론은 퀵 소트의 실행 시간은 서로 다른 두 원소가 얼마나 직접적으로 비교가 되느냐에 직결된다는 것이었다. 퀵 소트의 피벗은 랜덤으로 결정된다고 가정하였으므로, 랜덤 피벗에 따라 서로 다른 두 원소가 얼마나 비교되는지가 결정된다! 비교될 확률 i~j 까지 원소들 Z_ij 가 있을 때 원소 , z_i 와 z_j 가 비교될 확률을 구해보자. 만약 피벗이 i < p < j 인 p로 설정이 된다면, i 와 j 는 p 랑만 비교가 된 후 서로 다른 두 하위문제로 넘어가는 경우이다. 따라서 피벗이 i 혹은 j 로 설정 돼었을 때 X_ij = 1 이다. 따라서 Pr{z_i is compared to zj} = 2 / j-i+1 (i~j 까지의 개수) 이다. 최종 비교시간..
[Python] 파이썬 유용한 함수들 1탄 / 코딩 테스트에 유용한 함수들
1. zip - 두 iterable 을 한 인자씩 묶어서 튜플 배열로 반환한다. Big = ['A','B','C','D','E'] small = ['a','b','c','d','e'] Big_and_small = list(zip(Big,small)) print(Big_and_small) ↓ [('A', 'a'), ('B', 'b'), ('C', 'c'), ('D', 'd'), ('E', 'e')] * String 2개를 zip 할 수도 있다. Big = "ABCDE" small = 'abcde' Big_and_small = list(zip(Big,small)) print(Big_and_small) ↓ [('A', 'a'), ('B', 'b'), ('C', 'c'), ('D', 'd'), ('E', 'e'..
[알고리즘] Greedy strategy / 그리디 알고리즘 전략, 구성
그리디 알고리즘 구성하기 1. 문제의 최적의 부분구조를 만든다. (문제를 잘 이해하고 어떻게 해결할지 구성하라는 의미이다.) 2. 재귀적으로 해결책을 도출한다. 3. 재귀 내부의 어느 단계이든, 최적의 선택 중 하나는 반드시 greedy choice 임을 증명한다. 4. greedy choice 를 했을 때, 하나의 부분문제만 남는 것을 보인다. (계속해서 greedy choice를 해야되기 때문에) 5. 그리디 알고리즘을 완성시킨다. 6. 재귀적인 알고리즘을 iterative 하게 변환한다. * 재귀적인 알고리즘 -> iterative 알고리즘 과정을 거치는 이유는 생각하는데에 있어서 편하기 때문이지 바로 알고리즘을 구현할 수 있다면 굳이 거치지 않아도 된다. 출처 : 고려대학교 정순영 교수님 알고리즘..
[알고리즘] Activity-selection-problem / 그리디 알고리즘
Activity-selection-problem이란? Expo 전시회에 놀러간 당신. Expo에는 여러 activity(활동) 들이 있다. activity들은 각각 시작시간과 종료시간이 다르고, 먼길 걸어 온 전시회이므로 당신은 최대한 많은 활동들을 즐기고 돌아가고 싶다. activity들의 정보(activity의 시작 시간, 종료 시간) 를 보고 최대 몇개의 활동을 할 수 있을지 어떻게 구할까?? Input : activity 집합 의 시작 시간, 종료 시간. (s_i, f_i) *조건 : 종료 시간은 오름차순 정렬이 되어 있다! (정렬 안되어있으면 직접 정렬하면 됨) 예시) 예를들어 3번째 activity 는 0분에 시작하여 6분에 끝난다. ( 시간은 분이라고 치자) 활동들을 즐기는 방법은 다양하다...
[프로그래머스💯] 코딩테스트 연습 > 스택,큐 > 기능개발
스택, 큐는 이용하지 않고 풀었습니다! time 변수를 만들어서 시간 초를 고려하며 큐 형태로 풀 수 도 있습니다~ 참고만 하시길! 정답) * 다른 사람들의 풀이를 보니 이차원 배열을 이용하여 짧고 깔끔하게 풀 수도 있더라구요. 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
[파이썬] from import / 모듈 가져오기
import 패키지 - 패키지.변수 - 패키지.함수() - 패키지.클래스() 등으로 사용할 수 있다. *패키지 앞에 . 을 붙여주면 그 폴더 내에 있다는 뜻이다. 예시) import requests URL = "www.programming119.tistory.com" res = requests.get(URL) requests.get(URL).text requests.get(URL).status_code 이런식으로 requests를 써주고 뒤에 . 을 통해 변수,함수, 클래스 등을 이용할 수 있다. from 패키지 import 변수or함수 -패키지 명 없이 바로 변수와 함수를 쓸 수 있다. 예시) from requests import get URL = "www.programming119.tistory.co..