본문 바로가기

컴퓨터공학기초 개념/알고리즘 개념38

Advanced Algorithm - 이진 탐색(Binary Search) 1. 시작하기 전에 - 아래와 같은 문제가 있을 때, 어떤 방법(=알고리즘)을 사용하는 것이 가장 효율이 좋을지 생각해보자. 생각의 과정 1. 조건 점검하기 - 1~100 사이의 난수가 30개의 병뚜껑에 적혀있고 이 중에 70이 있는지 찾아야 한다. - 30개의 병뚜껑에는 오름차순으로 숫자가 정렬되어 있다. - 가장 적은 수의 병을 따서 70을 찾아야 한다. 2. 가장 적은 수의 병을 따는 방법 - 1~30번 후보군의 중간에 위치한 15번 병뚜껑을 확인하여 후보군을 반으로 줄인다. - 15번 병뚜껑의 숫자가 70보다 작다면 우측(16 ~ 30번 병뚜껑), 70보다 크다면 좌측(1~14번 병뚜껑)을 후보군으로 선정한다. - 좌측 또는 우측의 후보군이 선정되면 위의 과정을 반복한다. - 최종적으로 숫자 70.. 2020. 9. 18.
Advanced Algorithm - 병합 정렬 (Merge Sort) 1. 병합 정렬이란? - 분할 정복 알고리즘을 기반한 정렬이다. - 재귀용법을 사용한다. a) 병합 정렬의 동작 방식 1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 2. 어떻게 구현할까? 필요한 기능 1. 단위 데이터까지 나누는 기능 * 단위 데이터: 더 이상 분리될 수 없는 데이터 2. 나눠진 데이터를 정렬하면서 합치는 기능 3. 재귀 용법을 활용하여 1번과 2번 기능을 구현 3. 코드 구현 1) 리스트를 분리하는 기능 def split(data): medium = int(len(data) / 2) #리스트의 중간위치 left = data[:medium].. 2020. 9. 17.
Advanced Algorithm - 퀵 정렬(Quick Sort) 1. Quick 정렬이란? - 정렬 알고리즘의 꽃! 파이썬과 만나면 아름다운 코드가 탄생한다. - 데이터에서 기준점(pivot)을 정하여 pivot보다 작다면 좌측(left)에, 크다면 우측(right)에 정렬한다. - 좌/우측으로 1차 정렬된 데이터에서 좌/우측 각각의 pivot을 다시 선정하고 정렬을 수행한다. - 이 과정을 재귀함수를 사용하여 반복한다. - 최종적으로 정렬된 데이터를 반환한다. 예시) Quick 정렬의 동작과정 index 0 1 2 3 4 5 data 55 13 45 88 76 59 이와 같은 데이터가 있을 경우, 1) 55를 pivot으로, 좌/우측으로 정렬 index 1 2 0 3 4 5 data 13 45 55 (pivot) 88 76 59 2) 좌/우측에서 각각 pivot을 .. 2020. 9. 15.
Advanced Algorithm - 동적 계획법(DP) & 분할정복(Divide&Conquer) 1. 정의 1) 동적 계획법(Dynamic Programming, DP) - 정의: 하나의 큰 문제를 해결하기 위해, 큰 문제를 작은 문제들로 나누어 부분적으로 해결한 후 그로부터 파생된 값인 해를 이용하여 최종적으로 전체 문제를 해결하는 방식의 알고리즘 - 상향식 접근법: 가장 최하위 문제의 해답을 구한 후, 이를 이용하여 상위 문제를 풀어나가는 방식 - 메모이제이션(Memoization) 기법: 프로그램 실행 시 이전에 계산한 값을 저장하여 동일한 연산/계산에 대해서 다시 수행하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 - 왜 이런 기법들을 사용하는가? → 큰 문제를 작게 쪼개어 풀다보면 중복되는 부분이 발생한다. 동일한 연산에 대해서는 1번의 연산을 수행하여 저장하는 방식을 통해 이를 재활.. 2020. 9. 15.
Algorithm - 재귀함수/호출 연습 (recursion practice) 문제 1) 재귀함수를 이용하여 1부터 n까지의 곱셈을 구현하라. 1) for문을 이용한 코드 def multiple(num): return_value = 1 for index in range(1, num+1): return_value = return_value * index return return_value [결과] 2) 재귀함수를 이용한 코드 def multiple(num): if num 2020. 9. 12.
Algorithm - 재귀 호출(Recursive Call) 1. 재귀 호출(recursive call) - 재귀 호출이란, 함수 안에서 해당 함수가 호출되는 형태를 말한다. - 고급 알고리즘을 이해하기 위해 반드시 이해해야 하는 개념이다. 1) 팩토리얼 알고리즘을 재귀호출을 이용하여 구현 a) 간단한 경우부터 생각해보기 * 2! = 1 X 2 * 3! = 1 X 2 X 3 * 4! = 1 X 2 X 3 X 4 = 4 X 3! b) 규칙이 보임: n! = n X (n - 1)! 1. 함수를 하나 만든다. 2. 함수(n) 은 n > 1 이면 return n X 함수(n - 1) 3. 함수(n) 은 n = 1 이면 return n c) 검증 (코드로 검증하지 않고, 직접 간단한 경우부터 대입해서 검증해야 함) 1. 먼저 2! 부터 - 함수(2) 이면, 2 > 1 이므.. 2020. 9. 11.
Algorithm - 공간복잡도(Space Complexity) 1. 개요 알고리즘의 성능을 평가하는 계산 복잡도는 두 가지로 표현된다. 1) 시간 복잡도(Time Complexity) - 얼마나 빠르게 실행되는가 2) 공간 복잡도(Space Complexity) - 얼마나 많은 저장공간을 필요로 하는가 통상적으로 두 가지 계산 복잡도를 모두 만족시키기는 어렵다. 그 이유는 다음과 같다. - 시간과 공간은 반비례적 경향이 있다. - 최근 대용량 시스템이 보편화되면서, 공간보다 시간 복잡도가 우선적이다. 그러므로 알고리즘은 시간복잡도가 우선이다. 2. 공간 복잡도(Space Complexity) - 프로그램을 실행 및 완료하는데 필요한 저장 공간의 양/크기를 의미한다. 2-A) 총 필요 저장공간 계산법 - 고정 공간(알고리즘과 무관): 코드, 단순 변수 및 상수의 저장.. 2020. 9. 11.
Algorithm - 삽입 정렬(Insertion Sort) 1. 삽입 정렬(Insertion Sort) - 두번째 인덱스에 위치한 데이터를 기준으로 해당 데이터의 앞 쪽에 위치한 데이터와 비교하여 더 큰 값을 갖고 있다면 더 큰 값을 가진 데이터를 뒤로 밀어내는 방식이다. 삽입된 데이터보다 작은 데이터를 만날 때까지 반복한다. (아래 사진참고) 1-A) 어떻게 구현할까? ex) 5, 3, 2 [풀이] 1) 두번째 인덱스에 위치한 3을 기준으로 5와 비교한다. → 3, 5, 2 2) 2를 기준으로 5와 비교한다. → 3, 2, 5 → 자신보다 작은 데이터를 만나지 못해 다시 비교한다. 3) 2를 기준으로 3과 비교한다. → 2, 3, 5 4) 5를 기준으로 3과 비교한다. → 2, 3, 5 → 자신보다 작은 데이터를 만났으니 더 이상 비교할 데이터가 없다. [규칙.. 2020. 9. 10.
Algorithm - 선택 정렬(Selection Sort) 1. 선택 정렬(Selection Sort) 이란? - 주어진 데이터 중, 최소값을 찾아 순서대로 나열하는 정렬방법 - 찾아낸 최소값을 데이터의 맨 앞에 위치한 값과 교체한다. - 교체된 맨 앞의 최소값을 제외한 나머지 데이터를 대상으로 이전의 작업을 반복한다. - 최종적으로 정렬된 데이터의 구조를 갖는다. 1-A. 어떻게 구현할까? ex) 5, 4, 3, 2, 1 [풀이] 1. 5와 4를 비교하여 더 작은 값을 찾는다. → 4 2. 4와 3을 비교하여 더 작은 값을 찾는다. → 3 3. 3과 2를 비교하여 더 작은 값을 찾는다. → 2 4. 2와 1을 비교하여 더 작은 값을 찾는다. → 1 5. 최소값이 1이므로 맨 앞에 위치한 5와 교체(swap)한다. → 1, 4, 3, 2, 5 6. 위의 동작을 .. 2020. 9. 10.

티스토리툴바