이진 탐색 알고리즘 Q www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net A 이진 탐색 알고리즘과 이중반복문 두가지 방법으로 풀었다. 다만, 이중반복문의 경우 시간초과 가능성이 높다. 1) 이진 탐색 알고리즘 코드 n = int(input()) array = list(map(int, input().split())) m = int(input()) target_list = list(map(int, input().sp..
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] >..
1. 자료구조 자료구조(Data Structure)란 데이터를 표현, 관리, 처리하기 위한 구조를 의미한다. 스택(Stack)은 박스 쌓기에 비유할 수 있다. 후입선출 구조이다. 따라서 기본 리스트에서 append()와 pop()을 이용하면 스택 자료구조와 동일하게 동작한다. 큐(Queue)는 대기줄에 비유할 수 있다. 선입선출 구조이다. 따라서 collections 모듈에 있는 deque 라이브러리를 활용하여 append()와 popleft()를 사용하여 동작할 수 있다 deque 객체를 리스트 자료형으로 변경하고자 한다면 list() 메서드를 이용하면 된다. 2. 재귀함수(Recursive Function) 재귀함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다. e..