Python

빅오 표기법 (Big-O)

Big-O 수학에서 빅오란 입력값이 무한대로 향할 때 함수의 상한을 설명하는 표기방법을 말합니다. 컴퓨터과학에서 빅오는 어떤 알고리즘을 수행하는 데 걸리는 시간 또는 공간 복잡도를 표기하는 방법입니다. 그렇다면 왜 컴퓨터과학에서 빅오 표기법이 필요할까요?? 보통 일반 컴퓨터의 경우 1초에 억단위의 연산을 수행하기 때문에 작은 입력에 대해서는 효율적인 알고리즘과 비효율적인 알고리즘의 수행 시간의 차이를 확인하기 어렵습니다. 또한 그래프에서 볼 수 있듯이 작은 값에서는 빨리 동작하는 알고리즘도 충분히 큰 값에서는 매우 느리게 동작할 수도 있기 때문에 보통 알고리즘의 효율성을 나타내는 시간 복잡도를 표기하기 위해 빅오 표기법을 사용합니다. 시간복잡도 대부분의 알고리즘은 아래 시간 복잡도 중 하나에 속합니다. ..

Decorator

데코레이터 클래스에서 메서드를 만들 때 @staticmethod, @classmethod, @abstractmethod처럼 @로 시작하는 것들이 데코레이터 데코레이터는 함수를 수정하지 않은 상태에서 추가 기능을 구현할 때 사용한다. 예를 들어 함수의 시작과 끝을 출력하고 싶은 경우 아래와 같이 작성할 수 있다. def trace(func): # 호출할 함수를 매개변수로 받음 def wrapper(): # 호출할 함수를 감싸는 함수 print(func.__name__, '함수 시작') # __name__으로 함수 이름 출력 func() # 매개변수로 받은 함수를 호출 print(func.__name__, '함수 끝') return wrapper # wrapper 함수 반환 def hello(): print..

21940 가운데에서 만나기

문제 https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 접근 모든 도시 간의 거리가 필요하므로 플로이드-워셜을 이용했다. 플로이드-워셜로 모든 도시 간의 거리를 구한 후, 각 도시에 대해 왕복시간의 최댓값을 계산했다. 풀이 주의할 점은 도시 a에서 도시 b로 가는 경로가 여러번 입력될 수 있으므로, 입력받을 때 경로의 최솟값으로 갱신해주어야 한다. n, m = map(int, input().split()) dist = [[1e9] * (n + 1) for _ in range(n + 1)] for..

19844 단어 개수 세기

문제 https://www.acmicpc.net/problem/19844 19844번: 단어 개수 세기 첫째 줄에 “문장”을 나타내는 문자열이 주어진다. 이 문자열은 영어 소문자, 띄어쓰기, -(하이픈), '(어포스트로피)로만 이루어져 있다. 이때 띄어쓰기, 하이픈, 어포스트로피 중 어느 것도 인 www.acmicpc.net 접근 전체 문자열을 띄어쓰기와 하이픈으로 구분한 다음, 각 문자열이 어포스트로피를 포함한다면 문제에서 주어진 합쳐지는 조건을 만족하는지 확인한다. 풀이 s = input().replace("-", " ").split(" ") vowel = ["a", "e", "i", "o", "u", "h"] prefix = ["c", "j", "n", "m", "t", "s", "l", "d", ..

다이나믹 프로그래밍 (DP)

다이나믹 프로그래밍 전체 문제를 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성되는 문제, 즉 최적 부분 구조를 가지는 문제에 대해 적용 가능하다. DP 가정 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다. DP, 그리디, 분할정복 참고로 그리디는 항상 그 순간에 최적이라고 생각되는 것을 선택하면서 풀이해 나가는 것이고, 다이나믹 프로그래밍은 중복된 하위 문제들의 결과를 저장해뒀다가 풀어나간다는 차이점이 있다. 또한 분할 정복으로 분류되는 병합 정렬과 퀵 정렬은 중복된 하위 문제들을 푸는 것이 아니기 때문에 다이나믹 프로그래밍으로 분류하지..

투 포인터와 슬라이딩 윈도우

투 포인터 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제풀이 전략 일반적으로 배열이 정렬되어 있을 때 유용하며, 2개의 포인터가 좌우로 자유롭게 움직이면서 문제를 풀이한다. 대표적인 문제로 배열의 구간합과 관련된 문제나 수열의 연속합과 같은 문제에서 사용한다. 예제 배열에서 구간합이 m 이상인 구간의 최소 길이 찾기 n, m = map(int, input().split()) a = list(map(int, input().split())) left, right = 0, 0 ans = n + 1 sum = a[0] while left = m: ans = min(ans, right - left + 1) sum -= a[left] left += 1 if left > right a..

그래프 관련 알고리즘

위상정렬 그래프 이론에서 사용하는 정렬 방식으로 주로 사이클이 없는 방향 그래프에서, 정점들을 방향을 거스르는 간선없이 나열한다. 여러 작업들이 주어질 때 그 중 특정 작업을 마치기 위해 선행되어야 하는 작업들을 모두 정렬하는 테크닉 from collections import deque v, e = map(int, input().split()) # 모든 노드에 대한 진입 차수는 0으로 초기화 indegree = [0] * (v + 1) graph = [[] for _ in range(v + 1)] for _ in range(e): a, b = map(int, input().split()) graph[a].append(b) # 진입차수를 1 증가 indegree[b] += 1 # 알고리즘 수행 결과를 담을..

버블 정렬, 선택 정렬, 삽입 정렬

버블 정렬 배열의 첫 원소부터 순차적으로 진행하며, 현재 원소가 그 다음 원소의 값보다 크면 두 원소를 바꾸는 작업을 반복한다. 정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간이 필요하지 않고 (제자리 정렬), 중복된 값을 입력 순서와 동일하게 정렬한다. (안정 정렬) 시간 복잡도는 최악, 최선, 평균 모두 O(n^2)으로 비효율적이며, 정렬되지 않은 원소가 정렬됐을 때의 자리로 가기 위해서 스왑 연산이 많이 일어난다. 알고리즘 def bubble_sort(arr): for i in range(len(arr) - 1, 0, -1): for j in range(i): if arr[j] > arr[j - 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] 조금 더 ..

22943 수

문제 https://www.acmicpc.net/problem/22943 22943번: 수 0부터 9까지 $K$가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 중 아래 조건을 모두 만족하는 수들의 개수를 구해보자. 단, 수의 맨 앞에는 0이 올 수 없다. 즉, 0143는 불가능하다. 서로 다른 www.acmicpc.net 접근 문제에서 어떤 k와 m이 주어지든지 간에 소수, 소수의 합으로 만들 수 있는 수, 소수의 곱으로 만들 수 있는 수는 정해져 있으므로 에라토스테네스의 체를 이용하여 소수를 구한다. 구해진 소수들을 이용해서 덧셈과 곱셈으로 만들 수 있는 수들을 미리 구해놓고 백트래킹으로 해당 수가 조건을 만족하는지 확인했다. 풀이 def solve(num): global ans if len(num..