본문 바로가기

Algorithm35

DP DP의 유래동적 계획법(dynamic programming)이라는 말은 최적화 문제을 연구하는 수학 이론에서 왔고, 전산학 전반에서 일반적으로 사용하는 동적, 혹은 프로그래밍이란 단어와는 아무련 관련이 없습니다. 즉, dynamic programming은 동적 프로그래밍이 아닌, 동적 계획법입니다. 중복되는 부분 문제동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미합니다.이 방식도 처음 주어진 문제들을 더 작은 문제들로 나눈 뒤 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문입니다. 동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식입니다.동적 계획법에서는 어떤 부분 문제는 2개 이상의 문제를 푸는 데 사용될 수 있기 때문에, 이 문제의 답을 .. 2025. 4. 25.
[개념 정리] 세그먼트 트리 세그먼트 트리가 뭘까요?   배열을 [0,1,2,3,4]라고 가정합니다.init() 메서드 과정public static long init(int start, int end, int node) { if(start == end) { return tree[node] = arr[start]; } int mid = (start + end) / 2; return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);} 1. 재귀 호출을 통해서 리프 노드까지 깊이 우선 탐색을 진행합니다.후위 순회를 통해서 리프 노드에 배열의 값을 저장하고, 부모 노드로 올라가면서 자식 노드들의 합을 구하는 과정입니다. .. 2025. 3. 13.
[개념 정리] 최단 거리 최단 거리는 어떻게 구할 수 있을까요? 이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다. 최단 거리최단거리 알고리즘은 그래프 상의 두 정점 사이의 거리가 최소가 되는 경로를 찾는 알고리즘입니다. BFS를 사용해도 최단 거리를 구할 수 있는거 아닌가요? BFS는 가중치가 같은 그래프에서 최단 거리 알고리즘으로 사용할 수 있습니다.가중치가 다를 경우엔 최단거리 알고리즘을 사용해야 합니다. 가중치가 다른 경우에 BFS로 최단거리를 찾을 수 없는 예시는 다음과 같습니다.A → C로 이동할 때, BFS로 하는 경우 14가 나오게 됩니다.하지만, 최단 거리는 A → B → D → C로 6이 나와야 합니다. 최단거리 알고리즘엔 어떤게 있을까요? 코딩테스트에선 .. 2025. 3. 12.
[개념 정리] DP DP가 뭘까요?  이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다. DP문제를 해결하기 위해 문제를 작은 하위 문제로 나누고, 그 결과를 저장해 동일한 하위 문제를 반복해서 풀지 않는 알고리즘 기법입니다.DP를 사용하기 위해서 충족되어야 하는 조건이 존재합니다. 조건은 다음과 같습니다. DP를 사용하기 위해 어떠한 조건들이 충족되어야 할까요? DP의 조건  1. 참조 투명성을 가져야 합니다.참조 투명성은 입력을 제외한 외적요소에 결과값이 영향을 미치지 않고, 동일한 입력에 대해 동일한 출력을 가지는 것을 의미합니다. 2. Optimal Substructure(최적 부분 구조)하위 문제들을 해결한 결과를 이용해서 전체 문제의 최적 해답을 구성할 수 .. 2025. 3. 11.
[개념 정리] 이분 탐색 이분 탐색이 뭘까요?  이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다. 이분 탐색정렬된 배열에서 탐색 범위를 절반씩 줄여가는 방식으로 특정 값을 찾는 알고리즘입니다.이진 탐색이라고도 불리면, 시간 복잡도는 O(log N)이 걸립니다. 주로 크기가 큰 배열에서 어떠한 값을 찾아야하는 경우에 해당 배열을 정렬하고 이분 탐색을 사용하면, O(logN)의 시간복잡도로 효율적으로 값을 찾을 수 있습니다. 이분 탐색 동작원리1. 가장 왼쪽 인덱스인 left와 가장 오른쪽 인덱스인 right를 설정합니다. 2. (left + right) / 2로 중간값인 mid를 계산합니다. 3. 값을 비교합니다.목표값과 중간값이 같은 경우, 탐색을 종료하고 mid를 반환합.. 2025. 3. 10.
[프로그래머스] Lv3. 봉인된 주문 풀이 방법 예를 들어, 주문서에서 "d", "e", "bb", "aa", "ae" 5개의 주문을 지웠을 때, 주문서에서 30번째 주문을 찾으려고 합니다.1~3번째 주문은 "a", "b", "c" 입니다."d"와 "e"는 삭제됐으므로 4~24번째 주문은 "f" ~ "z"입니다."aa"는 삭제됐으므로 25~27번째 주문은 "ab", "ac", "ad"입니다."ae"는 삭제됐으므로 28~30번째 주문은 "af", "ag", "ah"입니다.따라서 30번째 주문은 "ah"가 됩니다. 삭제된 주문 중 “bb”와 같이 n번째 주문보다 뒤에 위치해 있어서 n번째 주문을 찾는 데 영향을 주지 않는 주문도 존재할 수 있습니다.정수 n과 삭제된 주문들을 담은 1차원 문자열 배열 bans가 매개변수로 주어질 때, 삭제가 완료.. 2025. 3. 8.
[개념 정리] 투 포인터 투포인터가 뭘까요?  이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다. 투 포인터배열이나 리스트와 같은 선형 자료구조가 정렬된 상태에서 두 개의 포인터를 사용해 특정한 조건을 만족하는 부분 배열이나 원하는 값을 찾는 문제를 푸는데 사용되는 알고리즘 입니다. 일반적으로 정렬된 배열에서 두 수의 합 찾기, 연속된 부분배열의 합 찾기에 사용됩니다. 투 포인터 알고리즘은 어떤 원리로 동작하나요? 투 포인터 원리투 포인터 알고리즘은 이름처럼 2개의 포인터를 사용합니다.왼쪽 포인터 : 배열의 시작점에서 시작하여 오른쪽으로 한칸씩 이동하는 포인터오른쪽 포인터 : 배열의 끝지점에서 시작하여 왼쪽으로 한칸씩 이동하는 포인터투 포인터는 그림처럼 양 끝에서 시작해도 .. 2025. 3. 8.
[프로그래머스] Lv3. 코딩 테스트 공부 문제 풀이 방법당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요. 문제에서 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하라고 합니다.알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다. 각 문제마다 .. 2025. 3. 7.
[개념 정리] 라인 스위핑 라인 스위핑이 뭘까요? 몰라요..이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다. 라인 스위핑(Line Sweeping)가상의 수직선을 왼쪽에서 오른쪽으로 이동시키면서 각 지점을 처리해주는 알고리즘입니다.즉, 수직선을 기반으로 문제에서 주어진 정점을 하나씩 탐색하면서 계산을 수행합니다. 라인 하나를 빗자루 쓸 듯이 탐색한다고 해서, 라인 스위핑이라고 합니다. 라인 스위핑은 언제 사용할까요? 라인 스위핑은 점, 선, 구간이 정렬된 순서대로만 처리하면 되는 문제에서 아주 유용하게 사용이 됩니다.겹치는 구간 찾기, 최대 구간 길이, 가장 많이 겹치는 부분 찾기를 할때 유용합니다.보통 좌표 문제에서 많이 사용됩니다. 라인 스위핑을 사용하는 사용하는 간단한.. 2025. 3. 7.

티스토리툴바