반응형 알고리즘/Do it! 알고리즘 코딩테스트 C++10 섹션 9. 동적 계획법(Dynamic Programming) 동적 계획법(dynamic programming)은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다. 동적 계획법의 원리와 구현 방식 큰 문제를 작은 문제로 나눌 수 있어야 한다. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야한다. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 DP 테이블을 이용한다. 이를 메모이제이션(memoization) 기법이라고 부른다. 동적 계획법은 톱-다운(top-down) 방식과 바텀-업(button-up) 방식으로 구현 할 수 있다. 피보나치 수열 공식 ex) 1, 1, 2, 3, 5 D[N] = D[N -1] + D[N - 2].. 2023. 4. 3. 섹션 8. 조합(Combination) 자주 출제되는 유형인 그래프, DP, 인덱스트리 중 동적계획법(DP)를 이해하는데 도움이 된다. 조합 점화식 도출 방법을 잘 기억하자 조합(combination)은 nCr로 표현하고, n개의 숫자에서 r개를 뽑은 경우의 수를 뜻한다. 순열은 nPr로 표현되고, n개의 숫자중 r개를 뽑는 순서를 고려해 나열할 경우의 수를 이야기한다. 코딩 테스트에서는 순열보다 조합의 출제 빈도가 높고, 응요할 수 있는 문제도 많다. 조합은 순열과 비슷하게 분모에 r!만 추가되어 있는 것을 확인 할 수 있다. 순서가 다른 경우의 수를 제거하는 역할을 한다. 특정 문제를 가정하기 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기 조합 점화식 D[i][j].. 2023. 4. 3. 섹션 7. 트리(Tree) 트리 알아보기 트리(tree)는 노드와 에지로 연결된 그래프의 특수한 형태이다. Tip) 그래프의 표현으로도 tree를 표현할 수 있다. 트리의 특징 순환 구조(cycle)를 지니지 않고, 1개의 루트 노드가 존재한다. 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다. 트리의 부분 트리(subtree)역시 트리의 모든 특징을 따른다. 트리에서 임의의 두 노드를 이어주는 경로는 유일하다. 트리의 핵심 이론 트리의 구성 요소 노드 : 데이터의 index와 value를 표현하는 요소 에지 : 노드와 노드의 연결 관계를 나타내는 선 루트 노드 : 트리에서 가장 상위에 존재하는 노드 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 해당.. 2023. 4. 2. 섹션 6. 그래프(Graph) 그래프의 기본 유니온 파인드 : 그래프의 사이클이 생성되는지 판별되는 알고리즘 위상 정렬 조건 사이클이 없다 방향이 있는 그래프이다. 노드를 정렬해줌, 정렬 결과가 꼭 1개가 아니다. 사용 예시) 수강신청, 롤 아이템 트리등 방향이 있어야 한다. 다익스트라 : 시작점이 있고 다른 모든 노드로 가는 최단거리 알고리즘 단, 음수 간선이 있으면 안된다. 벨만-포드 : 음수 간선이 있어도 괜찮다. 주로 음수 사이클이 있는지 구할때 사용 ex) 시간 여행, 웜홀등 워프 플로이드-워셜 : 시작점이 없는 임의의 모든 노드에서의 최단거리 알고리즘 ex) 모든 도시간의 최단거리를 구하기, 모든 도시를 가는데 최소 시간 최소 신장 트리(MST) : 그래프에서 최소의 가중치 합으로 노드를 연결 할 수 있게 해주는 알고리즘으.. 2023. 3. 31. 이전 1 2 3 다음 반응형
