본문 바로가기

전체 글

 (117)
유클리드 호제법 - 최대공약수 구하는 알고리즘, 최소공배수 def gcd(a, b): while b > 0: tmp = a a = b b = tmp % b return a 최소공배수는 두 수를 곱한 뒤 최대공약수로 나눠서 구할 수 있다. 예를 들어 18과 24의 최대공약수는 6이고 각각 6x3, 6x4로 나타낼 수 있다. 최소공배수는 6x3x4이므로, 18과 24를 곱한 뒤 최대공약수로 한 번 나눠주면 된다. def gcd(a, b): while b > 0: tmp = a a = b b = tmp % b return a 최소공배수 = a*b // gcd(a, b)
이진 탐색, 이진 탐색 트리. 이진 탐색 이진 탐색 = 반으로 쪼개면서 탐색하기. 시작점 인덱스, 끝점 인덱스를 입력 받아서 이 둘을 합쳐서 2로 나눈 값을 중간 값으로 설정한 후, 중간 값이 타겟 값보다 크면 중간값 이상의 값을 모두 버리고 중간값 이하 부분에서 똑같이 반복. 시간 복잡도는 O(logN). 탐색 범위가 2000만이 넘어가면 거의 무조건 이진 탐색을 써야한다고 보면 된다. 정말 중요한 코드이므로 꼭 암기해 두자!!!! ------------------------------------------------------------------------ 트리 자료구조 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있다. 트리 자료구조는 그래프 자료구조의 일종으로 데이터베..
정렬 알고리즘 1. 선택 정렬 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복. - 가장 원시적인 방법으로 매번 가장 작은 것을 선택한다는 의미에서 선택정렬 알고리즘이라고 한다. 선택 정렬의 시간 복잡도 선택 정렬은 n-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 따라서 약 n x (n + 1) / 2 번의 연산을 수행한다고 할 수 있다. - O(N**) = 매우 비효율적. 2. 삽입 정렬 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에..
set() set() 함수 안에 매개변수로 리스트나 문자열을 대입하면 모든 중복이 제거된 채로 정렬이 된다. 추가: add() 삭제: discard() 차집합: 집합1.difference(집합2) 교집합: 집합1.intersection(집합2) 합집합: 집합1.union(집합2)
dir(), zip(), copy() dir() 함수 안에 리스트 또는 딕셔너리, 튜플 등을 넣으면 해당 매개변수가 사용할 수 있는 메소드를 모두 출력한다. zip() 함수는 여러개의 리스트를 하나로 묶어준다. zip 객체를 반환하므로 리스트로 변환해주어야 한다. 여러개의 리스트를 묶을 때 리스트 원소의 수가 다르다면 가장 원소의 수가 작은 리스트의 크기만큼 리스트가 만들어진다. copy() 함수는 해당 리스트를 복사한다. 원본을 보존하면서 리스트를 사용하고자 할 때 유용하다.
sorted() 내장 함수 파이썬의 내장 함수인 sorted() 함수는 key라는 인수로 함수를 전달받아, 해당 함수를 실행한 결과값을 기준으로 정렬을 진행하게 된다. a = 'accdddcggaac' b = sorted(a, key = a.find) print(b) 결과: ['a', 'a', 'a', 'c', 'c', 'c', 'c', 'd', 'd', 'd', 'g', 'g']
백준 9095번 1, 2, 3 더하기
백준 10828 스택

티스토리툴바