CodingCredit

알고리즘 ... 😭 하루이틀만에 머릿속에 너무많이 입력한 것 같다... 정리하자. 탐욕 알고리즘 (Greedy Algorithm) 여러 경우 중, 그 '순간' 에 최적이라고 생각하는 것을 선택해 나가는 방식. '순간'이라고 정의하는 선택은 Local하게는 최적이지만, 그 선택이 계속되어 Global하게 해답을 만들었을 때, 그것이 최적이라는 보장은 없다. Greedy Algorithm이 최적의 결과를 보장하기위해서는, Greedy Choice Property 와 Optimal substructure라는 두 가지 속성을 만족해야한다. Greedy Choice Property : subproblem의 해답이 다음 subproblem에 영향이 가지 않는다는 독립적인 연산 속성 Op..

호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다. 유클리드 호제법 개념 알고리즘의 골자는 다음과 같다. 두 양의 정수 a, b (a>b)에 대하여 a = bq + r (0

시간복잡도 란? 시간복잡도를 한문장으로 정리하면 "입력값이 커짐에 다라 증가하는 시간의 비율" 이라고 할 수 있다. 이 시간 복잡도를 표기하는 방법은 여러가지가 있지만, Big-O 표기법 (빅오표기법) 이 가장 흔하게 사용된다. Big-O표기법은 최악의 경우 입력값이 증가함에 따라 시간복잡도가 얼마나 증가하는지 표기하는 방법이다. Big-O 표기법의 종류 아래는 빠른 시간복잡도 순으로 나열한 것이다. O(1) - O(logn) - O(n) - O(nlogn) - O(n^2) - O(2^n) - O(n!) 빅오표기법을 표기할 때는, 계수나 정수값들은 생략한다. 예를 들어, 입력값이 1 증가할때마다 코드의 실행시간이 2초씩 증가한다고 하면, '이 알고리즘은 O(2n) 이구나!' 라고 생각할 수..

프로그래머스 문제중 "멀쩡한 사각형" 문제의 내용이다. 너비가w 높이가h인 사각형을 대각선으로 접었을 때, 잘린 사각형의 개수를 구하면 해결할 수 있는 문제다. 잘린 사각형의 개수 w가 8, h가12인 사각형이 있다. 이때, 직선이 지나는 점의 개수(빨간 사각형의 개수)는 4개이다. 이는 8과 12의 최대공약수이다. 최대공약수가 1일때를 생각해보자. w가 2, h가 3일 때를 한번 살펴보자. 대각선이 점에 도착할때까지, 가로의 개수 + 세로의 개수만큼 사각형이 갈라진다. 다만, 위의그림에서 대각선이 점에서 시작할 때, 잘리는 사각형이 중복되므로 1을 빼줘야한다. 정리하면, 최대공약수가 1일때 잘라지는 사각형의 개수는 w+h-1이다. 그렇다면 최대공약수가 g일때는?? 앞서 말했듯이, 중복되는 사각형은 대각..