점을 찍어가며

1. 그리디 알고리즘이란? 그리디 알고리즘이란 말그대로 Greedy(탐욕)이라는 이름과 같이 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘이다. 2. 예시 * 거스름돈 문제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야할 동전의 최소 개수를 구하라. 단 거슬러 줘야 할 돈 N은 항상 10의 배수이다. * 풀이 가장 큰 화폐 단위부터 돈을 거슬러 주는 아이디어로 해결한다. def solution(money): answer =0 change = [500, 100, 50, 10] remain = money for i in change..

1. 해시란? 해싱 = 해시 맵 = 해시 테이블 같은 용어로 key를 활용하여 value에 직접 접근 가능한 구조이다. 정렬보다는 검색이 유용하다. 파이썬으로 치면 딕셔너리가 이에 해당한다. 2. 해시 함수란? 해시와 해시테이블을 알기 전에 해시 함수라는 것을 알아야 한다. 자료구조를 배우는 이유는 원하는 값을 최대한 효율적으로 찾기 위해 여러가지 저장구조를 배우는 것이다. 데이터를 최대한 빠르게 찾기 위해서는 저장하는 위치도 잘 생각하여 저장해야 한다. 해시 함수는 key를 고정된 길이의 hash로 변경해주는 역할을 한다. 이 과정을 "해싱"이라고 말하기도 한다. key를 해시라는 함수에 input으로 넣고output으로 나오는 것이 해시이다. 3. 해시테이블? 해시 함수를 사용하여 키를 해시 값으로 ..

1) 선택 정렬 #임의의 배열 7개 array = [2,7,4,1,6,9,0] for i in range(len(array)): min = i for j in range(i+1, len(array)): if array[min] > array[j]: min = j array[i], array[min] = array[min], array[i] print(array) 2) 삽입 정렬 #임의의 배열 array = [2,7,4,1,6,9,0] #7개 for i in range(1, len(array)): for j in range(i, 0, -1): if array[j] < array[j-1]: array[j-1], array[j] = array[j], array[j-1] else: break print(arra..

1. 정렬 여러 개의 자료를 순서에 따라 나열하는 방법이다. 2. 정렬 알고리즘 선택 시 고려해야할 점 1) 정렬할 데이터 양 2) 데이터와 메모리 3) 이미 정렬된 정도 4) 필요한 추가 메모리의 양 5) 상대위치 보존여부 이 외에도 여러가지 요소가 있겠지만, 이러한 사항을 고려하여 정렬방법을 상황에 따라 적용해야 한다. 3. 정렬의 종류 정렬은 다음과 같이 8종류가 있다. 하나씩 구체적으로 살펴보면, 1) 선택 정렬 - 1번 값을 2번~마지막값 중 최솟값을 찾아 1번에 놓고, 2번값을 3번~마지막값까지 비교하여 최솟값을 찾아 2번에 놓는 과정을 반복하여 정렬하는 알고리즘이다. 2) 버블 정렬 - 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘이다. 3) 삽입 정렬 - 두 번째 값부터 시작해서 그 앞..

1. 이분탐색(Binary Search)란 ? 이분탐색 = 이진탐색 이며, 정렬되어 있는 배열에서 데이터를 찾으려 시도할 때, 범위의 가운데 값을 검사하여 원하는 값이 나올 때까지 반씩 줄여나가며 찾는다. 2. 예시 1, 2, 3, 4, 5, 6이라는 값에서 6을 찾고자 한다면 배열의 중간에 위치한 3이라는 값과 6을 비교한다. 6은 3보다 크므로, 3의 왼쪽에 위치하는 값들은 찾을 필요가 없어 3의 오른쪽에 있는 값을 대상으로 탐색을 재시도한다. 이제 4, 5, 6이 남았고 그 중 가운데 값인 5와 6을 비교한다. 6은 5보다 크므로 5의 오른쪽 값을 대상으로 탐색을 재시도한다. 6과 6을 비교하면 값이 일치하므로 탐색을 종료한다. 3. 시간복잡도 문제 처음부터 끝까지 원하는 값을 찾을 때까지 탐색을 ..

1. 동적 계획법이란? 동적 계획법(dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. - wikipedia *DP라고도 불림 2. 동적 계획법 등장 배경 동적 계획법 등장 배경은 피보나치 수열을 통해 알 수 있다. 제2항까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수로 정의된다. 제0항은 생략되기도 한다. (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89... 프로그래밍에서 피보나치 수열은 보통 재귀함수를 통해 표현한다. 아래는 피보나치 수열을 이용한 N번째 수를 구하는 함수이다. fibo(..

1. 완전탐색이란? - 모든 경우의 수를 고려하는 탐색 알고리즘 - 영어로는 Exhaustive Search라고 한다. 가능한 모든 경우의 수를 다 해보는 것이다. 알고리즘을 풀 때 가장 확실한 방법이지만 그만큼 가장 시간이 오래걸리는 기법이다. ex) 4자리 암호를 풀기 위해 0000~9999까지 모두 시도해보는 것 ( 가장 확실하지만, 가장 오래걸린다 ) - 해당 기법을 문제해결 알고리즘에 사용 할 때, 2가지 규칙을 적용한다. 1. 사용된 알고리즘이 해당 문제를 해결하기에 적절한가? 2. 효율적으로 작동하는가? 대부분의 경우 2번에서 미충족된다. 다양한 문제를 이 기법으로 해결 하기에는 비효율적이라는 것이다. 따라서 완전탐색 기법을 사용 시 그 문제에 대한 파악이 중요! 2. 완전탐색 기법의 종류 ..