알고리즘

[알고리즘] LIS, LCS (링크)

LIS의 길이를 구하는 3가지 알고리즘 LIS, 최장 증가 수열의 길이를 구하는 3가지 알고리즘을 살펴봅니다. shoark7.github.io LIS의 최적화 \(lis(i):=A_i\)를 마지막 원소로 갖는 LIS의 길이 \[lis(i)=\max_{j 단순 DP로 \(O(n^2)\)에 문제를 해결할 수 있다. 그런데 다음 함수 \(f\)를 이용하면 정말로 필요한 최적의 지점만을 \(O(\log n)\)에 찾을 수.. mathsciforstudent.tistory.com [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니..

[알고리즘] CheatSheet - python

다익스트라 import heapq def dijkstra(n): # O(ElogV) hq = [(0, n)] dis[n] = 0 while hq: cur_dis, cur_x = heapq.heappop(hq) if cur_dis > dis[cur_x]: continue for i, w in graph[cur_x]: new_dis = cur_dis + w if dis[i] > new_dis: dis[i] = new_dis heapq.heappush(hq, (new_dis, i)) 벨만 포드 def bellman_ford(n): # O(VE) min_d = [float('inf')] * (v + 1) min_d[n] = 0 for i in range(v): for j in range(e): a, b, w =..

[Python] 백준(BOJ) 9663번 N-Queen(백트래킹)

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입력 1 8 예제 출력 1 92 코드 n = int(input()) arr = [0] * n cnt = 0 def det(num): # 검증 함수 for v in ..

[Python] 백준(BOJ) 10989번 수 정렬하기 3 (계수 정렬)

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입력 1 10 5 2 3 1 4 2 3 5 1 7 예제 출력 1 1 1 2 2 3 3 4 5 5 7 코드 import sys input = sys.stdin.readline print = sys.stdout.write arr = [0]*10000 for i in range(int(input())): # 1~10000까지 각 숫자의 개수 구하기 arr[int(input..

[Python] 백준(BOJ) 9020번 골드바흐의 추측

9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이..

[알고리즘] 소인수분해

n = int(input()) while n % 2 == 0: # 2로 나누어지면 n에 2를 나누고 2를 출력 n //= 2 print(2) for i in range(3, int(n ** .5) + 1, 2): # 3부터 루트n까지 2씩 증가 while n % i == 0: # i로 나누어지면 n에 i를 나누고 i를 출력 n //= i print(i) if n == 1: break # n == 1 이면 for문 탈출 if n != 1: print(n) # 입력받은 n이 소수이면 아무런 계산도 하지 않고 그대로 나옴 #입력값 72 #출력값 2 2 2 3 3 # 입력값 9991 # 출력값 97 103

[알고리즘] 특정 구간 소수 ( 에라토스테네스의 체 )

m, n = int(input()), int(input()) # 구간을 입력받는다 bool = [False, False] + [True]*(n-1) # 0과 1은 소수가 아니므로 False를 넣어둔다 for i in range(2, int(n**.5)+1): if bool[i]: for index in range(i*2, n+1, i): bool[index] = False # i의 배수에 False를 넣어준다 print([i for i in range(m, n+1) if bool[i]]) # m부터 n까지의 구간에서 bool[i]가 True인 값만 출력 # 입력값 3 20 # 출력값 [3, 5, 7, 11, 13, 17, 19]

[알고리즘] 소수 판정

p = int(input()) # p에 값을 입력받는다 bool = True if p 2 and p % 2 == 0: # p가 2보다 크고 짝수면 소수가 아니다. bool = False else: for i in range(3, int(p ** .5) + 1, 2): # 3부터 p의 제곱근까지 홀수만 나누어 본다 if p % i == 0: bool = False # p가 나누어떨어지면 소수가 아니다 break if bool: print('소수가 맞다') else: print('소수가 아니다') # 입력값 2 # 출력값 소수가 맞다