기초
-
그림으로 개념을 이해하는 알고리즘: 04. 퀵 정렬책 공부/그림으로 개념을 이해하는 알고리즘 2023. 12. 6. 00:01
📖 책 정보 1. 분할 정복 문제 해결 방법 중에서 가장 유명한 재귀적 기술인 분할 정복 dividid and conquer 전략! 분할 정복 전략은 문제에 바로 적용할 수 있는 단순한 알고리즘이 아니다. 문제를 풀기 위한 방법론에 가깝다. 문제를 분할 정복 전략으로 풀기 위해서는 다음의 두 가지 단계를 거쳐야 한다. 기본 단계를 해결한다. 이 부분은 가능한 한 간단한 문제이어야만 한다. 문제가 기본 단계가 될 때 까지 나누거나 작게 만든다. 2. 퀵 정렬 선택 정렬보다 훨씬 빠르고, 실제로 자주 사용되는 정렬 알고리즘이다. 예를 들면, C언어에는 qsort라는 함수가 있는데, 바로 퀵 정렬을 구현한 함수이다. 퀵 정렬도 마찬가지로 분할 정복 전략으로 만들어진 알고리즘이다. 배열을 정렬 해본다고 가정해보..
-
그림으로 개념을 이해하는 알고리즘: 02. 선택 정렬책 공부/그림으로 개념을 이해하는 알고리즘 2023. 12. 6. 00:01
📖 책 정보 선택 정렬 아래와 같은 표가 있을 때, 🎶 PLAY COUNT PADIOHEAD 156 KISORE KUMAR 141 THE BLACK KEYS 35 NETURAL MILK HOTEL 94 BECK 88 THE STROKES 61 WILCO 111 해당 표를 선택 정렬 해본다면? 1. 리스트의 모든 항목을 살펴보고 가장 많이 연주된 가수를 찾아 새로운 리스트에 기록한다. SORTED PLAY COUNT PADIOHEAD 156 2. 그 다음으로 많이 들은 가수를 찾아서 반복한다. SORTED PLAY COUNT PADIOHEAD 156 KISORE KUMAR 141 이런식으로 반복하면 정렬 된 리스트를 얻을 수 있다. SORTED PLAY COUNT PADIOHEAD 156 KISORE KU..
-
그림으로 개념을 이해하는 알고리즘: 03. 재귀책 공부/그림으로 개념을 이해하는 알고리즘 2023. 12. 6. 00:01
📖 책 정보 1. 재귀 재귀는 풀이를 더 명확하게 만들어 준다. 재귀를 쓴다고 성능이 더 나아지지는 않는다. 사실 반복문이 더 성능이 좋은 경우가 많다. 이에 대해 스택 오버플로우에 있는 레이 케드웰의 말을 인용해보면 다음과 같이 이야기 할 수 있다. " 프로그램에 반복문을 사용하면 프로그램의 성능을 향상시킬 수 있지만, 재귀를 사용하면 프로그래머의 능력을 향상시킬 수 있습니다. 상황에 따라 적절한 방법을 골라 사용하세요. " 대부분의 중요한 알고리즘들이 재귀를 사용하므로, 개념을 잘 이해하는 것이 중요하다. 2. 기본 단계와 재귀 단계 재귀 함수를 만들 때는 언제 재귀를 멈출지 알려줘야 한다. 그래서 모든 재귀 함수는 기본 단계 base case 와 재귀 단계 recursive case 라는 두 부분으..
-
그림으로 개념을 이해하는 알고리즘: 01. 이진 탐색, 빅오 표기법책 공부/그림으로 개념을 이해하는 알고리즘 2023. 12. 6. 00:01
📖 책 정보 모바일 가이드 01. 이진 탐색 코드로 구현해보기 실행 시간 02. 빅오 표기법 많이 사용하는 빅오 실행 시간의 예 외판원 문제 이진 탐색 입력 : 정렬된 원소 리스트 반환 : null 또는 원소 인덱스 원소 리스트의 중간 값과 찾을 값을 비교하여 중간 값이 더 작으면 왼쪽 구간을 탐색, 중간 값이 더 크면 오른쪽 구간을 탐색 한다. 찾을 값이 나올 때 까지 반복하는 방법! 42개의 원소가 들어있는 리스트에서 7을 찾고자 할 때 맨 처음 원소부터 하나씩 확인한다면 찾는데 7번의 탐색을 하겠지만, 이진 탐색을 사용한다면 4번의 탐색으로 찾을 수 있다. 1. 코드로 구현해보기 public Integer binarySearch(int[] arr, int item) { int low = 0; int..