Data Makes Our Future

# Divide & Conquer ## about- 가장 유명한 알고리즘 디자인 패러다임- 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산, 각 부분 문제의 답으로부터 전체 문제의 답을 계산- 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머니 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눔- 일반 재귀 호출은 항상 문제를 한 조각과 나머지로 쪼개는 방식, 분할정복법은 항상 문제를 절반씩으로 나누는 분할 정복 알고리즘출처 : https://kugistory.net/76 ## 구성 요소- 문제를 더 작은 문제로 분할(Divide)- 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합(Merge)- 더이상..

#. 문제 https://algospot.com/judge/problem/read/CLOCKSYNC* 이 문제의 저작권은 Algospot에 있습니다. 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다. 시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같다. 시계들은 맨 윗줄부터, 왼쪽에서 오른쪽으로 순서대로 번호가 매겨졌..

#. 재귀 호출 ㅇ 재귀 호출(=재귀 함수) recursion(=recursive function) - 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수 - 다양한 알고리즘을 구현하는데 매우 유용하게 사용할 수 있는 도구 - 문제의 특성에 따라 재귀 호출은 코딩을 헐씬 간편하게 해 줄 수 있는 강력한 무기 - 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성 - 완전 탐색을 구현할 때 아주 유용한 도구 ㅇ 완전 탐색으로 해결하기 위해 필요한 과정 1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수가 정확히 비례 - 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두..

참고글 : [Algorithm] 프로그램 수행 시간 짐작하기 #. 알고리즘 ㅇ 알고리즘 - 어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법 - 주관적이거나 모호한 것은 알고리즘이라고 할 수 없음 ㅇ 알고리즘이 사용하는 시간과 공간 - 시간 : 알고리즘이 적은 시간을 사용한다는 것은 더 빠르게 동작한다는 이야기 - 공간 : 알고리즘이 적은 공간을 사용한다는 것은 더 적은 용량의 메모리를 사용한다는 이야기 ㅇ 알고리즘 시간 분석도 분석 - 프로그램의 실행 시간을 알고리즘의 속도를 일반적으로 이야기하는 기준이 되기에는 부적합 - 이유 1. 프로그램의 수행 시간은 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러까지 수많은 요소에 의해 바뀔 수 있음 - 이유 2. 프로그램의 실제 수행 시간이 다..

#. 좋은 코드를 작성하기 위한 원칙 ㅇ 간결한 코드 작성하기 - 가장 간결한 코드, 읽기 쉬운 코드 작성 ㅇ 적극적으로 코드 재사용하기 - 코드의 모듈화 - 코드가 세 번 이상 등장한다면 항상 해당 코드를 함수로 분리해 재사용한다는 기본 원칙을 세우기 - 항상 코드를 깔끔하게 작성하고 유지하는 데 신경을 써보기 - 간결한 코드가 디버깅 시간에 엄청난 차이를 가져다 줌 - 이상적인 세계에서는 한 함수가 두 가지 이상의 일을 해서는 안 된다고 말함 ㅇ 표준 라이브러리 공부하기 - 표준 라이브러리의 사용 - 언어의 문자열, 동적 배열, 스택, 큐, 리슽, 딕셔너리 등의 자료 구조, 정렬 등의 표준 알고리즘 구현 사용법을 반드시 잘 알아 두기 ㅇ 항상 같은 형태로 프로그램 작성하기 ㅇ 일관적이고 명료한 명명법..