학습 목표
알고리즘이 무엇인지 설명할 수 있다.
알고리즘 문제를 이해하고 전략을 세울 수 있다.
알고리즘 풀이에 필요한 의사 코드를 작성할 수 있다.
의사 코드에서 세운 전략을 코드로 구현할 수 있다.
내가 구현한 알고리즘을 자바 언어로 설명할 수 있다.
👻의사코드(pseudocode)
프로그래밍 언어로 코드를 작성하기 전에 우리가 쓰는 일상 언어로 프로그램이 작동하는 논리를 먼저 작성하는 것을 말
의사코드의 장점
1. 시간이 단축된다.
2. 디버깅에 용이하다.
3. 프로그래밍 언어를 모르는 사람과 소통할 수 있다.
👻시간복잡도(Time Complexity)
시간 복잡도를 표기하는 방법
Big-O(빅-오)
Big-Ω(빅-오메가)
Big-θ(빅-세타)
위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법인데 예를들어 최악의 경우를 고려하는 빅오 표기법의 경우
"최소한 특정 시간 이상이 걸린다" 혹은 "이 정도 시간이 걸린다"를 고려하는 것보다 "이 정도 시간까지 걸릴 수 있다"를 고려해야 그에 맞는 대응이 가능하다.
👻Big-O 표기법
Big-O 표기법은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기하는 방법이다.
👻O(1)
F(int[] n {
return (n[0] == 0)? true:false;
}
O(1)은 위와같이 입력값이 증가하더라도 시간이 늘어나지 않는다.
👻O(n)
F(int[] n {
for i = 0 to n.length
print i
}
위와 같이 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
빅오 표기에서 상수는 과감하게 버린다.
ex) O(2n) => O(n)
👻O(log n)
BST와 같은 로직이다.
O(1) 다음으로 빠른 시간 복잡도를 가진다.
👻O(n^2)
입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
F(int[] n {
for i = 0 to n.length
for j = 0 to n.length
print i = j;
}
👻O(2^n)
Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
public int fibonacci(int n) {
if(n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci (n - 2);
}
재귀로 구현하는 피보나치 수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘이다.
👻탐욕 알고리즘(Greedy)
Greedy Algorithm(탐욕 알고리즘)은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
탐욕 알고리즘(Greedy)로 문제를 해결하는 방법은 다음과 같이 구분할 수 있다.
1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.
👻탐욕 알고리즘의 예
형준이는 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 준형이는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 준형이는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다.
위와같은 경우 500원 동전 1개, 100원 동전 4개, 50원 동전과 0원 동전 각각 1개씩 선택할 것이다.
1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
3. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 부족하면 1번 과정부터 다시 반복한다.
👻마시멜로 실험이란?
지금 마시멜로를 받겠다고 말하면 1개를 받을 수 있지만, 1분을 기다렸다가 받는다면 2개를 받을 수 있다.
greedy는 "현재"에 최선인 선택을 하기 때문에 마시멜로를 당장 받아내어 1개를 받게 되지만,
전체적으로 보게 되면 1분 뒤에 받는 2개가 최적의 선택이 된다.
위에서 알 수 있듯이 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립해야 한다.
* 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
* 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.
탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.
👻구현 시뮬레이션, 완전 탐색 알고리즘
구현 능력을 보는 대표적인 사례에는 완전 탐색(brute force)과 시뮬레이션(simulation)이 있다. 완전 탐색이란 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식을 뜻하고, 시뮬레이션은 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션을 하는 것과 동일한 모습을 그린다.
👻시뮬레이션
시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형이다.
보통 문제에서 설명해 준 로직 그대로 코드로 작성하면 되어서 문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있다.
👻완전 탐색 알고리즘(Brute-Force Algorithm)
0-9 사이의 4자리 숫자로 된 자물쇠가 있다고 가정해보자
이 자물쇠의 비밀번호를 잊어버려 0000 0001 … 9999와 같이 대입할 수 있는 모든 값을 대입하는 방법을 암호학 에서는 Brute Force Attack이라고 하는데, 완전 탐색 알고리즘(Brute-Force Algorithm)또한 비슷한 맥락이다.
Brute Force Algorithm은 모든 가능성을 시도하여 문제를 해결하는 무차별 대입 방법이 있는 알고리즘이다.
최적의 방법은 아니며, 공간복잡도와 시간복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법을 의미한다.
Brute Force Algorithm은 크게 두 가지 경우에 사용된다.
* 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때
* 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때
Brute Force Algorithm은 문제가 복잡해질수록 기하급수적으로 많은 자원을 필요로 하는 비효율적인 알고리즘이 될 수 있기 때문에 일반적으로 문제의 규모가 현재 자원으로 충분히 커버가 가능한 경우에만 사용된다.
👻동적 프로그래밍 - DP(Dynamic Programing)
하나의 문제를 단 한번만 풀도록 하는 알고리즘을 동적 프로그래밍 - DP(Dynamic Programing)이라고 한다.
예를 들어 피보나치 수열의 문제를 풀 때 이미 구한 값이지만 중복해서 연산을 하게된다.
이러한 경우에 Dynamic Programing을 사용하면 편리하게 해결할 수 있다.
👻이진 탐색 알고리즘(Binary Search Algorithm)
Binary Search Algorithm은 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘이다.
1. 정렬된 배열의 가장 중간 인덱스를 지정한다.
2. 찾으려고 하는 값이 지정한 중간 인덱스의 값이라면 탐색을 종료한다. 아니라면 3단계로 이동한다.
3. 찾으려고 하는 값이 중간 인덱스의 값보다 큰 값인지, 작은 값인지 확인한다.
4. 값이 있는 부분과 값이 없는 부분으로 분리한다.
5. 값이 있는 부분에서 다시 1단계부터 반복한다.
탐색을 반복할 때마다 탐색 범위가 절반으로 줄어들게 되는 이 알고리즘은 데이터 양이 많을수록 더 높은 효율을 가지게된다.
하지만 Binary Search Algorithm의 한계 또한 존재한다.
* 배열에만 구현할 수 있다.
* 정렬되어 있어야만 구현할 수 있다.
* 규모가 작은 배열이라도 정렬이 되어 있지 않다면 정렬을 한 후 Binary Search Algorithm을 사용해도 효율이 높지 않다.
👻이진 탐색 알고리즘(Binary Search Algorithm) 사용 예
* 사전 검색
* 도서관 도서 검색
* 대규모 시스템에 대한 리소스 사항 파악
* 반도체 테스트 프로그램은 디지털, 아날로그 레벨을 측정하는데 Binary Search Algorithm을 사용한다.
Binary Search Tree(BST)와의 차이점?
Tree는 자료구조를 나타내고 Algorithm은 해결 방법을 나타낸다.
또한 BST는 아래와 같은 규칙이 있다.
* 부모노드는 왼쪽 자식노드보다 큰 값을 가진다.
* 부모노드는 오른쪽 자식노드보다 큰 값을 가진다.오늘은 의사코드, 시간복잡도 등에 대해 학습했다.
요즘들어 의사코드를 사용하려고 노력하고 있는데, 확실히 의사코드를 사용하니 코딩을 할 때 편리하다는 느낌을 많이 받았다.
또한 백준 브론즈 문제들을 통해 논리적 사고를 키우려고 노력하고 있다.
하지만 아직 브론즈5~4 수준인 나에게 알고리즘 자료 구조는 정말 어렵게 느껴졌다.
그렇기에 오늘 학습하는 동안 예제를 볼 때마다 저걸 내가 할 수 있을까란 생각이 많이 들었다.
알고리즘 자료구조에 대해서는 지속적으로 학습을 해야할 것 같다.
오늘도 고생했고 내일도 파이팅!
개발 공부