CS & AI/Algorithm

보호되어 있는 글입니다.

import math# 이 함수는 오직 M 값을 출력하는 역할만 담당합니다.def linearSelect_wrapper(A, i): try: # 실제 계산은 select 함수가 수행하며, 최종 결과는 무시합니다. # select 함수 내부에서 print가 호출됩니다. select(A, i) except Exception as e: # 재귀 깊이 등 일부 예외가 발생할 수 있으나, # 문제의 출력 요구사항은 만족하므로 무시합니다. pass# 실제 로직을 수행하고, M을 출력하며, 값을 반환하는 함수def select(A, i): """ 배열 A에서 i번째 작은 원소를 찾습니다. (i는 1-based index)..

RadixSort def radix_sort_debug(arr, t): max_val = max(arr) if arr else 0 k = 1 if max_val == 0 else len(str(max_val)) base = 1 steps = max(t, k) for i in range(1, steps + 1): buckets = [[] for _ in range(10)] for x in arr: d = (x // base) % 10 buckets[d].append(x) p = 0 for b in buckets: for v in b: arr[p]..

보호되어 있는 글입니다.

Quick Sort n = int(input())arr = list(map(int, input().split()))def partition(arr, p, r, swap_count): pivot = arr[r] i = p - 1 for j in range(p, r): if arr[j] Heap Sort def heapSort(arr, n): buildHeap(arr, n) cnt = 0 k = n while k > 1: k = deleteMax(arr, k, cnt_only=True) cnt += deleteMax.swaps print(cnt)def buildHeap(arr, n): fo..

점화식(Recurrence Relation = Recurrence Relation)Recurrence : 우리가 아는 자료구조의 리커전의 그 단어가 맞다. 재귀. 재귀적 함수의 복잡도를 구하는 데에 유용하다. 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것이다.n번째 항의 값을 n보다 작은 항의 값으로 표현등차수열, 팩토리얼, 피보나치 수열, Merge Sort 등이 있다. 재귀적 용법=> 큰 문제를 푸는데 작은 문제로도 바꿔서 표현이 가능할 때, 또는 작은 문제들을 쭉 풀어왔을 때, 똑같은 포맷으로 풀어왔지만 들어가는 argument, 즉 data 개수 등을 변경해서 모아봤을 때 문제가 풀릴 때 이를 재귀적 용법이라 할 수 있다. 왜 알고리즘 분석에서 점화식이 중요한가?컴퓨터 자..

본 게시글은 학부 강의 '알고리즘(Algorithm)' 을 바탕으로 이해한 내용을 정리하였습니다. 알고리즘 분석 같은 문제를 해결하는 다양한 알고리즘 간 효율성 효율성에 대해 극명한 차이를 보인다.정렬(Sorting)을 예를 들면, O(n²) 와 O(n log n) 사이에 입력이 커질수록 성능 격차가 매우 증가함을 볼 수 있다.실무 영역에서 보면 Human Genome Project(40억 염기서열), 딥러닝 모델 경량화 등에서 이를 잘 보여준다. 알고리즘 수행 시간 시간 복잡도(Trime Complexity)측정원칙연산 횟수 기반 - 실제 시간이 아닌 기본 연산(덧셈, 비교 etc.) 횟수 계싼하드웨어 독립적 : CPU 성능과 무관한 절대적 척도입력 크기 함수 : n에 대한 함수 f(n..

알고리즘 정의특정한 문제를 풀기 위해 주어진입력을 정해진 출력으로 바꾸는 일련의 단계적 절차어떤 작업을 수행하기 위한 과정을 애매하지 않게 기술한 것어떤 작업을 수행하기 위해 입력을 받아 출력을 만들어 내는 과정을 애매하지 않게 기술한 것 바람직한 알고리즘명확성이해하기 쉽고 간결하게 기술지난친 기호적 표현은 명확성을 떨어뜨리기도 함명확성을 해치지 않는 경우 일반언어로 작성해도 무방 효율성같은 문제를 해결하는 서로 다른 알고리즘들의 수행 시간이 수백만배 이상 차이날 수 있음가능한 효율적인 알고리즘을 개발 입출력과 알고리즘의 예 Question : 학생 100명의 시험 점수 중 최댓값을 찾아라 Input : 100개의 점수Output : 입력된 100개의 점수 중 최댓값 알고리즘maxScore(x[..

Selection Sort import sysread = sys.stdin.readlinen = int(read())a = list(map(int, read().split()))count = 0for k in range(n - 1, 0, -1): max_idx = 0 max_val = a[0] for i in range(1, k + 1): if a[i] >= max_val: count += 1 max_val = a[i] max_idx = i a[k], a[max_idx] = a[max_idx], a[k]print(count) Bubble Sort n = int(input())arr = list(map..