헬창 개발자

알고리즘 리벤 슈테인 알고리즘 사용 두 개의 문자열 A, B가 주어졌을 때 두 문자열이 얼마나 유사한 지를 알아낼 수 있는 알고리즘입니다. 문자열 A가 문자열 B와 같아지기 위해서는 몇 번의 연산을 진행해야 하는 지 계산할 수 있습니다. 여기서의 연산이란, 삽입(Insertion), 삽입(Deletion), 대체(Replacement)를 말합니다. 점화식 두 문자가 같은 경우 : dp[i][j] = dp[i - 1][j - 1] 두 문자가 다른 경우 : dp[i][j] = 1 + MIN(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) 입력 데이터가 다음이라고 생각해보자 str1 = 'saturday' str2 = 'sunday' S 를 가지고 SA 를 만들기 위한 최소 ..

소스코드 def quick_sort(arr): if len(arr) pivot: big_arr.append(num) else: equal_arr.append(num) return quick_sort(small_arr) + equal_arr + quick_sort(big_arr) if __name__ == "__main__": n = int(input()) arr=[] for i in range(n): input_num = int(input()) arr.append(input_num) arr = quick_sort(arr) for i in arr: print(i, end=" ") 알고리즘 설계 알고리즘 설명 결과화면

소스코드 시뮬레이션

브릿지란 단절선, 절단선을 의미하며 그래프가 2개로 나눠지는 간선을 의미한다. 다음과 같은 그래프가 있다. 이 그래프에 단절선은 어떻게 찾을까?? 우리가 필요한 자료구조는 순회 체크 리스트, 현재 정점, 부모 정점, 브리지를 담을 리스트, 우회로 변수, (a, b) = (본인 순번, 주변 최소 순번)이다. 이제 알고리즘을 살펴보자 요약은 다음과 같다. # 자식 노드에서 부모 노드로 역으로는 검사 불가 (a, b)=(순번, 주변 최소 순번)를 비교하여 탐색하고 자식 노드의 b가 부모 노드의 a와 같으면 다른 노드를 통해 부모로 갈 수 있기 때문에 우회로가 있다고 판단하여 브리지가 아니게 되고 자식 노드의 b가 부모 노드의 a 보다 크면 우회로가 없기 때문에 브리지라고 판단한다. 정점 1에서 탐색을 시작한다..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. ..