Q www.acmicpc.net/problem/13706 13706번: 제곱근 첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다. www.acmicpc.net A n = int(input()) #정수 입력 import math print(math.isqrt(n)) #sqrt 사용시 overflowerror가 발생한다. 따라서 isqrt 사용하였다.
1. 다이나믹 프로그래밍 다이나믹 프로그래밍(Dynamic Programming)이란 큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때, 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자. ex) 피보나치 수열 피보나치 수열의 점화식은 다음과 같다. An = An-1 + An-2, A1 = 1, A2 = 1 (1) 피보나치 수열 재귀함수 코드 - 탑다운(Top-Down) 방식 d = [0] * 100 #한번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화 def fibo(x): if x == 1 or x == 2: #종료조건(1 또는 ..
1. 순차 탐색 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 하므로 데이터의 개수가 N개일 때, 최대 N번의 비교 연산이 필요하다. 따라서 최악의 경우 시간 복잡도는 O(N)이다. 2. 이진 탐색 (1) 이진 탐색 이진 탐색(Binary Search)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데, 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. 예를 들면 0, 2..
정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해 학습하겠다. 1. 선택 정렬 선택 정렬(Selection Sort) 알고리즘이란 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것을 의미한다. 코드는 다음과 같다. array = [7, 5, 1, 3, 0, 4, 2, 6, 9, 8] #리스트 선언 for i in range(len(array)): min_index = i #가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if array[min_index] >..
