개발/알고리즘

[Algorithm] 매개변수 탐색

매개변수 탐색 조건을 만족하는 최댓값을 찾을 수 있는 방법 최적화 문제를 결정 문제로 풀 수 있는 방법 최적화 문제 가능한 해들 중 가장 좋은 해를 찾는 것 결정문제 답이 이미 결정되어 있다고 보고 문제를 푸는 것 매개변수 탐색의 사용 결정문제로 풀면 쉽게 문제를 풀 수 있을 때 어떤 시점까지는 조건을 만족하지만 그 후로는 조건을 만족하지 않는 경우, 조건을 만족하는 최대값 찾기 어떤 시점까지는 조건을 만족하지 않지만 그 후로는 조건을 만족하는 경우, 조건을 만족하는 최소값 찾기 시간 복잡도 : O(logN) 이진 탐색을 하는데, 조건이 만족한다고 종료하는 것이 아니라 끝까지 탐색하여 조건을 만족하는 최대값 / 최소값 찾을 때 사용 예제 BOJ 1654 - 랜선 자르기 문제 집에서 시간을 보내던 오영식은..

[Algorithm] 이진탐색 (바이너리 서치)

이진탐색(Binary Search) 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘 정렬된 자료를 반으로 나누어 탐색하는 방법 시간 복잡도 : O(logN) 주의점 이진탐색에서 자료는 반드시 오름차순으로 정렬된 자료여야 한다 예제 BOJ 10815 - 숫자카드 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주..

[Algorithm] 그래프 탐색 - DFS & BFS

그래프 탐색 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 DFS (Depth First Search: 깊이우선탐색) 스택 사용 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 모든 노드를 방문하고자 하는 경우에 이 방법을 선택 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다 검색 속도 자체는 너비 우선 탐색(BFS)보다 느리다 순환 알고리즘(재귀 함수) 형태를 가지고 있다 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다 이 과정을 생략하면 무한루프에 빠질 수 있다 정점의 수: N, 간선의 수: E인 경우 시간 복잡도 인접 리스트로 표현된 그래프 : O(E+N) 인접 행렬로 표현된 그래프 : O(N^2) BFS (Breadth F..

[Algorithm] 리스트와 딕셔너리

알고리즘 문제를 풀다보면 리스트를 사용했는데 시간초과가 발생하는 경우가 있다. input을 sys.stdin.readline으로 바꿔봐도 시간초과가 난다. 이런 경우 리스트 말고 다른 방법을 찾아봐야 할 것이다. 1. 리스트 리스트란, 대괄호 사이에 쉼표로 구분된 값(항목)들의 목록이다. 쉽게 말해 서로 다른(대부분은 같은) 자료형을 포함하는 목록이라고 생각하면 된다. arr = [1, 2, 3, 4] # 1, 2, 3, 4로 이루어진 list 파이썬은 list에 대해 여러가지 연산을 제공해준다. 1.1 리스트 연산의 시간 복잡도 연산 설명 시간 복잡도 len(arr) arr의 길이 O(1) arr[i] i에 해당하는 value O(1) arr[i:j] i부터 j까지 슬라이싱 O(슬라이스하는 길이) it..