[Algorithm] DP (Dynamic Programming) : 동적 계획법

중복되는 연산을 줄인다 우선 다이나믹 프로그래밍의 다이나믹은 사실 간지를 위해 사용한 이름으로 동적인 의미와는 상관이 없다... 다이나믹 프로그래밍은 약간 더 메모리를 사용하면 연산속도를 비약적으로 증가시킬 수 있는 방법으로 두가지 조건을 만족할 때 사용할 수 있다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 두 조건을 만족하는 가장 대표적인 예시는 피보나치 수열이다. 피보나치 수열은 점화식을 가지고 있다. 이전 2개의 항의 값에 영향을 받는다는 점을 이용해 재귀함수로 구현할 수 있다. 아래는 점화식을 재귀함수로 구현한 코드이다. #include using namespace std; intfibonacci(int n) { if (..

[Algorithm] 탐색 알고리즘 DFS/BFS

DFS (Depth-First-Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 이다. DFS의 장점 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다. 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다. DFS의 단점 해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색합니다. 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용한다. DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없습니다. DFS는 해에 도착하면 탐색을 종료하기 때문이다. BFS (Breadth-First-Search) 너비 우선 탐색이라고도 부르며 가까운 노드부터 탐색하는 알..

[Algorithm] 구현(Implementation)

아이디어를 코드로 바꾸는 구현 코딩 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 완전 탐색은 모든 경우의 수를 다 계산하는 해결방법을 의미하고. 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형을 의미한다. 상하좌우 n * n 크기의 정사각형 공간을 입력 받고 다음 라인에 L, R, U, D 중 하나의 문자를 연속적으로 입력받는다. 시작하는 포인트는 (1, 1) 이며 n * n 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 해당 계획서가 주어졌을 때 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하는 문제이다. L : 왼쪽으로 한 칸 이동 R : 오른쪽으로 한 칸 이동 U : 위로 한 칸 이동 D : 아래로 한 칸 이동 n ..

[Algorithm] 그리디(Greedy) : 탐욕법이란?

당장 좋은 것만 선택하는 그리디 그리디(Greedy) 알고리즘은 국내에서 단어 그대로 번역하여 탐욕법으로 소개된다. 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 현재 상황에서 지금 당장 좋은 것만 고르는 방법 을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘의 문제 유형은 앞으로 다루게 될 알고리즘과 비교했을 때 사전에 외우고 있지 않아도 풀수 있을 가능성이 높은 문제 유형이라는 특징이 있다. 자바코드와 새로 배우고 있는 파이썬 코드로 풀어보았다. 큰 수의 법칙 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번..

[Algorithm] 알고리즘의 복잡도와 Big-O 란?

알고리즘이란 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들의 집합을 의미한다. 가는 루트는 다양하며 여러가지 상황에 따른 알고리즘은 모두 다르다. 따라서 시간복잡도가 가장 낮은 알고리즘을 선택하여 사용한다. 복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도 특정한 크기의 입력에 대하여 알고리즘을 수행할 때 연산이 몇번 이루어지는 지를 표기 공간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 빅오 표기법(Big O Notation) 복잡도를 표현할때에는 빅오 표기법을 ..