본 게시글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)"의 내용을 참고하여 기재하였습니다. 동적 계획법이란 ? 동적 계획법은 분할 정복과 유사하지만, 이미 계산한 값을 중복해서 계산하지 않기 위해 따로 저장하는 메모이제이션 기법을 사용했다는 것이 주요 특징이다. 이 기법은 참조적 투명성을 가지고 있는 함수에 대해서 적용된다. 같은 입력이 들어왔을 때 항상 같은 출력을 반환한다는 것이다. 유의사항 (1) 입력이 정해진 범위를 벗어난 경우 등을 기저 사례로 처리하여 cache에 저장하기 (2) cache의 초기값을 -1과 같은 수로 두고 -1이 아니라면 이미 계산된 값이라 생각한다. (3) 저장된 값을 반환하여 담는 ret변수는 &를 사용해서 “별칭”으로 선언한다. 이는 cache의..
본 게시글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)"의 내용을 참고하여 기재하였습니다. 분할 정복 부분 문제의 답으로부터 전체 문제의 답을 도출한다. (1) 문제를 더 작은 문제로 분할하는 과정 (Divide) (2) 부분 문제를 원래 문제로 병합하는 과정(merge) (3) 더이상 답을 분할하지 않고 바로 푸는 문제 (base case) ex) 행렬의 거듭제곱 행렬의 곱셈은 주어진 행렬의 모든 원소를 가로 세로를 곱해줘야하므로 O(n^3) 의 시간 복잡도를 가진다. 이를 분할 정복을 이용해서 풀어보자. class SquareMatrix; SquareMatrix identity(int n); SquareMatrix pow(const SquareMatrix& A, int m) ..
본 게시글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)"의 내용을 참고하여 기재하였습니다. [06] 무식하게 풀기 (Brute-Force) 재귀호출 재귀호출의 기저 사례 : 더 이상 쪼개지지 않는 마지막 조각에 도달했을 때 답을 반환하는 조건문을 작성하여야 함. 이 마지막 조각을 기저 사례라고 한다. 4중 for문을 통해 4가지 원소를 고르는 사례에서, 원소들의 총 개수 더 골라야 할 원소들의 개수 지금까지 고른 원소들의 번호 이 세가지를 함수의 인자로 넣어 재귀호출을 수행할 수 있다. 따라서 재귀호출로 완전탐색 문제를 풀 때는 아래의 프로세스를 사용한다. (1) 문제의 분할 (2) 기저 사례의 선택 (3) 구현 (4) 시간복잡도 분석 문제1 : 소풍 #include using ..
A와 B 사이에 겹치는 건물이 있는지 확인하는 과정에서 "두 점 사이의 직선" 공식을 이용해서 A와 B사이에 있는 모든 건물의 높이를 계산하여 푸는 과정을 이용했다. 여기서 (double) 범벅을 한 이 코드에서 j가 자꾸 잘 못 구해지는 버그가 있었다. A와 B건물 사이의 i번째 건물의 높이가 A와 B의 지붕을 연결한 선에 겹치지 않는지 검사하기 위해서 아래 공식을 사용한 것인데, j의 계산이 잘 되지 않았다 . #include #include using namespace std; // 고층 빌딩 /* 15 1 5 3 2 6 3 2 6 4 2 5 7 3 1 5 */ vector height ; // 빌딩 A(x1, y1)이 빌딩 B(x2, y2)를 볼 수 있는 지 확인하는 함수 bool isOverla..
총 일할 수 있는 N일 중에서 연속된 M일을 선택했을 때 그 부분합이 최대가 되는 경우를 계산하는 문제이다. 구간을 정해서 부분합을 구하는 슬라이딩 윈도우 혹은 투포인터 알고리즘을 적용할 수 있고, 여기서는 M이라는 일정한 크기의 윈도우가 정해져있으므로 슬라이딩 윈도우 알고리즘을 사용하여 풀이한다. https://ji-musclecode.tistory.com/37 슬라이딩 윈도우 알고리즘(Sliding Window) (feat. 투 포인트) 1. 슬라이딩 윈도우 알고리즘 (Sliding Window) ( 슬라이딩 윈도우 알고리즘 간단 예제 ) 1, 2, 3, 4, 5, 6, 7 로 이루어진 숫자 배열에서 A[i] + A[i+1] + A[i+2] 형식으로 연속적인 3개의 숫자의 합의 최댓값을 ji-musc..
해당 리스트의 연속 수열의 합이 특정 값보다 이상이 되는 것 중 가장 짧은 것의 길이를 확인하는 문제이다. https://butter-shower.tistory.com/226 [Algorithm] 투포인터(Two Pointer) 알고리즘 알고리즘 문제를 풀다보면 종종 나오는 투포인터 알고리즘! 막 꼬여가지고 ㅋㅋㅋ 저도 중간에 제대로 못짜고 그러는 경우가 많은데요, 많은 코딩테스트 문제에 등장하는 것은 아니지만 잊을만 butter-shower.tistory.com 투포인터 알고리즘은 병합정렬에서 사용한 Conquer 방식과 유사하게 start와 end 지점에서의 부분합을 계산하는 알고리즘이다. 이 문제에서는 특정값 S의 이상이 되는 값들 중 가장 짧은 것을 구하라고 하였으니, 아래의 방법들로 소스코드를 ..
(1) BubbleSort ExchangeSort라고도 함.6t 배열을 쭉 순회하면서 현재 인덱스의 요소를 기준으로 뒤에 있는 요소들을 한 번씩 순회 큰 요소(내림차순), 작은 요소(오름차순) 이 있다면 swap하며 정렬을 수행한다. void bubbleSort(int* a, int size) { int i, j; for (int i = 0; i a[i]) { swap(a[j], a[i]); } } } } if문에서 a[j]가 더 크면 내림차순 정렬이다. 왜냐하면 큰 요소를 앞으로 가져온다는 뜻이기 때문이다. (2) Insertion Sort Sorting되고 있는 구간, Sort되지 않..
다익스트라 알고리즘 : 그래프에서 꼭짓점 간의 최단 경로를 찾을 수 있는 알고리즘이다. 한 꼭짓점을 고정하고, 그래프의 다른 꼭짓점까지 최단 경로 트리를 만들며 이동하는 방식으로 구현한다. 다이나믹 프로그래밍의 한 종류인데, 최단거리를 구하는 매 과정에서 이전 단계에서 구한 최단거리를 사용하기 때문이다. https://m.blog.naver.com/ndb796/221234424646 23. 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐... blog.naver.com 1) 이차원 배열의 형태로 n행 m열의 값을 n번에서 m번 노드로 가는 비용을 저장한다. 2) 시작 노드(방문 처리)에서 인접 노드..
