본문 바로가기

Study/Algorithm Study

 (12)
[Algorithm] 정렬: 힙 정렬 + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 힙 정렬 (Heapsort) 버블 정렬과 비슷하게 1등을 뽑아내고, 나머지 원소에서 1등을 계속 뽑아내면서 정렬한다. 버블 정렬: 남은 원소에서 1등을 다시 비교를 통해서 찾는다. 힙 정렬: 힙을 이용하면, 1등을 뽑아낸 뒤 나머지 원소에서 1등을 뽑을 때, 다시 비교할 필요 없이 2등이 자동으로 1등이 된다. => 힙 생성 -> 루트 원소 제거 -> 힙을 유지 힙 (Heap) - 완전 이진 트리이다. + 원소가 n개인 힙의 모양은 1개이다. (높이는 logn) 최대 힙: 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전 이진 트리 최소 힙: 부모 노드의 키 값이 자식 노드보다 작거나 같은..
[Algorithm] 정렬: 병합 정렬, 퀵 정렬 + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 분할 정복 기법 (Divide-and-Conquer) 문제의 크기가 커지면 더 풀기가 어렵다. => Divide: 원래 문제를 독립적으로 풀 수 있는 작은 문제로 나눈다. => Delegate: 각각의 문제를 푼다. => Combine: 각각의 문제의 답을 이용하여 원래 문제의 답을 만든다. 정렬 문제에 대한 분할 정복 기법 1. 병합 정렬 (Mergesort) 2. 퀵 정렬 (Quicksort) 병합 정렬 Divide: 정렬할 리스트를 앞쪽 반, 뒤쪽 반으로 나눈다. Delegate: 앞쪽 반을 정렬한다. Delegate: 뒤쪽 반을 정렬한다. Combine: 이 둘을 합쳐서 하나의 정렬된 리스트를 만든다. - 앞쪽 반..
[Algorithm] 정렬: 버블 정렬, 삽입 정렬 + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 정렬 문제 => n개의 서로 다른 수가 주어졌을 때, 이들을 이동하여 점점 커지게(오름차순), 또는 점점 작아지게(내림차순) 만드는 문제 ex) 9, 3, 5, 7 => 3, 5, 7, 9 - 한 문제를 풀기 위해서 여러가지 방법이 가능하다. - 방법마다 특징이 다르다. - 기본적인 문제이면서, 실생활에 자주 쓰인다. - 시간 복잡도, 최적성에 대해서 증명이 쉽다. 정렬할 데이터가 담긴 배열의 각 원소를 O(1) 시간에 접근 가능하다고 가정한다. (데이터가 메인 메모리에 저장되어 있다고 가정한다.) 버블 정렬 1. 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환한다. 2. 맨 끝까지 ..
[Algorithm] 알고리즘 기초 (3) + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 탐색 문제 1 정렬되지 않은 배열 E[1...n]에서, 어떤 값 k가 있는지 찾으시오. 만약 있다면 E[i]=k인 i를, 없으면 -1을 출력하라. ans = -1 E = list(map(int, input().split())) k = int(input()) for i in range(len(E)): if k == E[i]: ans = i break print(ans + 1) => 모든 원소를 하나씩 k 값인지 탐색 비교를 한 번 할 때마다, 원소 한개가 답인지 아닌지를 알 수 있다. 따라서 총 n번의 비교가 필요하다. - 비교를 하지 않으면 답인지 아닌지 알 수 없다. - n번 비교를 하지 않으려면 공짜로는 되지 않는다...
[Algorithm] 알고리즘 기초 (2) + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 알고리즘 설계 과정 - 크고 복잡한 문제의 해법을 바로 설계하는 것은 어렵다. => 문제를 분석하여, 풀 수 있는 크기의 작은 문제들로 나누고, 이 문제들을 푼 후, 각 문제들 간의 관계를 이용하여 해법을 연결한다. 하노이 탑 문제 기둥 1에 있는 n개의 원반을 어떻게 규칙을 만족하면서 기둥 3으로 옮길 것인가? 규칙 1. 언제나 원반은 1개씩 옮길 수 있다. 규칙 2. 작은 원반위에 큰 원반은 옮길 수 없다. n = 1, 2인 경우에는 쉽게 풀 수 있으나 조금만 커지면 직접 푸는 것은 어렵다. => 알고리즘 설계 기법 중 되부름(recursion, 재귀)을 이용한다. n = 1인 경우, 그냥 ..
[Algorithm] 알고리즘 기초 (1) + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 알고리즘의 정의 - 어떤 문제를 푸는 알고리즘: 어떤 입력에도 정확한 출력을 유한한 시간에 내는 프로그램 1. 어떤 입력: 문제가 풀기 쉽든, 어렵든, 입력의 크기가 작건, 크건 문제를 풀 수 있다. => 어떤 경우에는 정답을 내지 못한다면, 우리는 그 프로그램을 믿고 쓸 수 없다. 2. 정확한 출력: 문제가 요구하는 조건을 만족한다. => 정답이 요구하는 조건이 무엇인지를 명시할 수 있다. (무엇이 정답이고, 오답인지 알 수 있어야 한다) 3. 유한한 시간: 무한 루프에 빠지지 않고 납득할 수 있는 시간에 종료한다. + 튜링: 어떤 문제가 무한 루프에 빠질지 아닐지를 판단할 수 없다. (살아 생전에 답을 볼 수 없다.)..

티스토리툴바