알고리즘
탐욕 알고리즘
최적해를 구할 때, 지금 당장에 할 수 있는 최선의 선택을 해나가는 방식입니다.
가능한 해들 중 최대 또는 최소의 해를 찾는 문제를 최적화 문제라고합니다.
탐욕 알고리즘은 최적화 문제를 푸는 과정에서 여러 경우 중 하나를 선택할 때마다 그 순간 최적이라 생각되는 것을 선택해 나가는 방식으로 진행해 최종적인 답에 도달하는 방식을 의미합니다.
각 선택 지점마다 내리는 결정은 당시에는 최적인 결정처럼 보이지만 최종 결과가 최적이라는 보장을 내리기는 어렵습니다. 그렇기 때문에 그리디하게 구한 해가 최적인지 아닌지는 항상 확인해 봐야합니다.
그 기준은 탐욕 알고리즘의 필수 요소들을 생각하면서 찾아볼 수 있습니다.
1. 탐욕적 선택 속성
항상 최적의 선택을 한다고 생각하면서 진행합니다.
2. 최적 부분 구조
하나의 선택을 하면 하위 문제가 하나 남고, 그 문제에서 하나의 선택을 하면 또 하나의 문제가 남으면서 모든 선택을 해나가는 방식으로 정형화합니다.
원래 구해야할 문제의 최적해 = 탐욕적 선택(1) + 하위 문제의 최적해(2)임을 증명하면 그리디하게 구한 해가 최적인지 증명할 수 있습니다.
유명한 그리디 알고리즘 중 하나인 다익스트라 알고리즘을 통한 예시를 보겠습니다.
먼저 다익스트라 알고리즘은 당시에 최적인 해를 뽑아서 결론적으로 최단거리를 구할 수 있는 알고리즘입니다.
다익스트라 알고리즘 탐욕 알고리즘 증명
증명에 앞서 용어에대한 정의를 먼저하겠습니다.
length[v] - 최단 경로의 길이
distance[w] - 시작점에서부터의 최단 경로의 길이
S - 시작점을 포함해서 현재까지 최단 경로를 발견한 점들의 집합
u = min{distance[w], w 는 V-S의 원소} - u까지의 최단 거리의 길이는 distance[u] 와 같다.
둘이 같다는 것은 다음처럼 증명할 수 있습니다.
distance[u] > length[u]라고 가정해보겠습니다.
P를 시작점부터 u까지의 최단 경로라고 하면
P의 길이 = length[u]입니다.
P는 S에 속하지않는 최소 1개의 정점을 가집니다.
그렇지않다면 P의 길이 = distance[u]가 됩니다.
P의 경로에 속하면서 S에 속하지않는 시작점에서 가장 가까운 점을 w라 하겠습니다.
그렇게 된다면 distance[u] > length[u] >= length[w] 가 성립하고,
length[w] = distance[w]이기 때문에 이로부터
distance[u] > distance[w]를 유추해낼 수 있습니다.
이는 다익스트라 알고리즘은 아직 최단경로가 찾아지지않은 정점들만 선택한다는 정의에 어긋납니다.(지금 보는 점보다 가까운 경로가 존재한다면 이전 탐색에서 걸러져서 S에 포함되어있기 때문입니다.)
그렇기 때문에 distance[u] = length[u]입니다.
분할 정복
큰 문제를 작은 문제로 만들어서 각각 해결하고 해결된 답을 모으는 방법입니다.
분할 정복을 이해할 때, 고기를 굽는 과정을 생각하면 이해가 잘 됩니다.
고기가 크면 잘 익지않아서 적절한 크기로 잘라주고(분할)
적절히 자른 고기를 맛있게 구워서(정복)
뱃속으로 모은다.(통합)
분할 정복의 설계 전략
- 분할
해결할 문제를 여러 개의 작은 부분으로 나눕니다. - 정복
분할된 작은 문제를 각각 해결합니다. - 통합
필요에 따라 해결된 해답을 모읍니다.
이진 검색
이진 검색은 대표적인 분할 정복 문제입니다.
제일 먼저 이진 검색을 사용하기 위해서는 자료는 정렬된 상태여야합니다.
정렬된 자료에대해서 문제의 크기를 절반씩 줄여나가면서 문제 풀이를 진행해 최종적으로 찾으려는 값을 찾는 검색 방법입니다.
웹 개발
프로젝트에서 기획자가 요구사항을 이야기하면 그에대한 설계를 진행해서 개발하는 것이 개발자의 업무 중 하나입니다. 그렇다면 이런 요구사항들은 어떻게 대응하면 좋을까요??
요구사항과 설계
역할과 구현을 구분
요구사항을 보고 역할과 구현을 구분해야합니다. 인터페이스를 만들고 구현체를 언제든지 갈아끼울 수 있도록 설계해야합니다. 다르게 말하면 역할과 구현을 분리해서 자유롭게 구현 객체들 간의 관계를 맺을 수 있도록 설계해야합니다. 이렇게하면 역할들의 협력관계를 그대로 유지할 수 있습니다.
클래스는 정적으로, 객체는 동적으로
설계 단계에서 클래스 다이그램과 객체 다이어그램을 그려서 진행하는데, 클래스 다이어그램은 정적이고 객체 다이어그램은 동적으로 그려집니다.
서비스 인터페이스의 구현체가 리파지토리 인터페이스를 바라보는 형태로 개발을 하는데, 서버가 뜨면 실제로 참조하는 주소값에는 서비스의 구현체가 들어가 있다고 생각하시면 됩니다.
실제 코딩을 할 때, 클래스와 인터페이스는 같은 패키지에 두지않는 것이 좋습니다.
불가피하게 같이 있어야한다면 설계상의 문제가 있는 것이기 때문에 문제점을 파악해야합니다. 이때 주로 문제가 되는 부분이 의존성에 관한 부분이기 때문에 주의깊게 보는 것이 중요합니다.
그 때 가장 주의할 것이 단일책임의 원칙입니다.
단일책임의 원칙을 잘 지키면서 역할을 잘 분리해야하는 이유는 하나의 객체가 여러 역할을 담당하면, 이후에 다가올 변화가 있을 때, 변화에 해당하는 부분 이외의 부분까지도 수정을 해야하는 일이 생기기 때문입니다.
요구사항의 변경
위에서 언급했던 단일책임의 원칙을 잘 지켜서 설계한 경우, 요구사항에 변경이 생기면 변경된 부분에 관련된 역할을 수정해주면됩니다.
하지만 클라이언트 코드인 구현체 코드를 고쳐야하는 경우가 있습니다.
또한, 역할과 구현을 충실하게 분리하고, 다형성도 활용하고 인터페이스와 구현 객체를 분리해서 구현해도 고쳐야하는 경우가 있습니다.
그 이유는 무엇일까요??
DIP나 OCP와 같은 객체지향 설계 원칙을 지킨 것 처럼 보이지만 사실은 그렇지않기 때문입니다.
클래스 의존관계를 분석해보면 클라이언트가 인터페이스에만 의존하는 것이 아니라 인터페이스의 구현 클래스에까지 의존합니다. 그렇기 때문에 기능을 확장해서 변경하는 경우, 클라이언트에 영향을 주게되고, 이는 OCP를 위반하게 됩니다.
그렇다면 이를 어떻게 해결할 수 있을까요??
다음과 같은 과정을 통해서 해결할 수 있습니다.
인터페이스에만 의존하도록 설계와 코드를 변경
-> 구현체가 사라짐. 그런데 구현체가 없는데 어떻게 코드를 실행할 수 있을까??
-> 누군가가 객체를 대신 생성해서 주입해주면된다.
이때 사용되는 것이 DI입니다. DI에 관련된 내용은 추후에 다루겠습니다.
