Passwd

개요2025.05.26-[알고리즘] 최장 증가 수열(LIS) - DP에서 최장 증가 수열을 동적 계획법으로 찾는 방법을 정리했었다. 다만 동적 계획법의 경우에는 O(n^2)의 시간 복잡도를 가진다. 때문에 배열의 길이가 아주 큰 경우에는 보다 효율적인 방법을 사용할 필요가 있다.이 글에서는 최장 증가 수열을 O(log n)의 시간 복잡도로 찾을 수 있는 이분 탐색을 사용한 방법을 정리해 본다. 최장 증가 부분 수열이분 탐색을 활용할 때는 LIS를 기록하는 배열을 하나 생성한 뒤, 주어진 배열을 하나씩 살펴보면서 각 숫자가 증가수열에 들어갈 위치를 찾는 방식이다. 상세한 과정은 다음과 같다. 구현1. 이분 탐색숫자가 들어갈 위치를 찾는 이분 탐색 함수는 아래와 같다.증가수열의 숫자가 들어갈 위치는 현재..

문제최근 알고리즘 문제를 풀던 중 증가수열과 관련된 문제를 발견했다. 완전 탐색으로도 구현할 수 있지만 비효율적으로 보여 좀 더 좋은 방법을 정리해 본다. 최장 증가 부분 수열최장 증가 부분 수열(Longest Increasing Subsequence) 문제는 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제이다. 부분 수열이 연속적이거나 유일할 필요는 없다. 예로 들어, 아래 그림과 같은 수열이 있다고 하자.이 수렬의 증가 부분 수열은 [1, 5], [1, 4], [2, 3, 8] 등 여럿 존재하지만, 그중 길이가 가장 긴 최장 증가수열을 찾으면 아래와 같다. 접근최장 증가 수열을 구현하는 대표적인 방법은 완전 탐색, DP를 이용하는 방법이다.수열의 한 원소 K에 대해, K에서 끝..

개요알고리즘 문제를 풀어내다 보면 간혼 투 포인터 알고리즘이라는 단어를 접할 때가 있다. 배열을 순회할 때 사용하는 것 같은데, 이번 글에서는 투 포인터 알고리즘에 대한 개념을 알아본다 투 포인터 알고리즘1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해 가면서 원하는 값을 찾을 때까지 탐색하는 알고리즘으로, 보다 쉽게 표현하면 리스트에 순차적으로 접근할 때 두 점의 위치를 기록하면서 처리하는 알고리즘이라고 할 수 있다.특정 조건을 만족하는 부분 구간을 효율적으로 탐색할 수 있기 때문에 이중 for문으로 처리해 시간복잡도가 O(N^2)인 작업을 O(N)으로 줄일 수 있다. 일반적으로 배열이나 리스트가 정렬되어 있을 때 사용한다. 구현 방식일반적으로 투 포인터 알고리즘은 다음과 같이..

깊이 우선 탐색깊이 우선 탐색(Depth First Search)이란 그래프 탐색 방법 중 하나로, 최근에 방문한 정점을 선택한 뒤, 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 주로 깊이 우선 탐색과 같이 언급되는 알고리즘이다.단순 검색 속도는 BFS보다 느리기 때문에 검색이 아닌 순회할 때 많이 사용한다. 즉, 방문할 수 있는 모든 정점을 확인해야 할 때 깊이 우선 탐색을 사용한다. 또한 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법인 백트래킹, 그리고 자동 미로 생성에서 많이 사용한다. 참고로 깊이 우선 탐색으로 찾은 결과는 최단 경로가 된다는 보장은 없다. 또한 해가 없을 경우를 고려하여 탐색할 깊이를 미리 지정할 필요가 있다.   동작 방식임의..

너비 우선 탐색너비 우선 탐색(Breadth First Search)이란 그래프 탐색 방법 중 하나로, 임의의 시작 정점을 방문한 후 인접한 모든 정점을 우선 방문하는 방법이다. 갈림길에 연결되어 있는 모든 길을 탐색한 뒤, 다시 연결되어 있는 모든 길을 넓게 탐색하는 방법이다.그래프 내 모든 간선의 가중치가 같으면 너비 우선 탐색으로 찾아낸 두 점 사이의 경로는 최단 경로에 해당한다. 따라서 두 점 사이의 최단 경로 또는 임의의 경로를 찾고 싶을 때 너비 우선 탐색을 사용한다. 보통 너비 우선 탐색에 대해 찾아보면 트리 형태의 그래프 탐색이 가장 흔하게 보이는데, 트리 형태가 아닌 그래프에도 사용할 수 있다. 또는 미로 찾기와 같은 이차원 배열에도 사용할 수 있다.   동작 방식너비 우선 탐색은 방문한..

동적 계획법 동적 계획법 (Dynamic Programming)이란 복잡한 문제를 간단한 여러 문제로 나누어 푸는 방법을 말한다. 부분 문제가 반복(Overlapping Subproblem)되거나 최적 부분 구조 (Optimal Substructure)를 가진 알고리즘을 효율적으로 해결할 때 사용한다. 최적 부분 구조 (Optimal Substructure) 답을 구하기 위해 수행한 계산을 반복해야 하는 문제의 구조 동적 계획법은 알고리즘이라기보다는 어떤 문제를 풀 때 그 문제를 더 작은 문제의 연장선으로 생각하고 기존에 구한 해를 활용하는 방법을 총칭한다고 이해하는 편이 좋다. 접근 방식 1. 큰 문제를 작은 문제로 표현할 수 있다. 예로 들어 피보나치는 아래와 같이 표현할 수 있다. $$ \begin..

개요 2022.06.18 - [Algorithm] 에라토스테네스의 체에서 정리한 에라토스테네스의 체 알고리즘은 소수를 찾는 방법으로 유명하다. 다만 범위 내의 모든 소수를 찾는 방법이기 때문에, 어떤 수가 소수인지 아닌지를 확인할 때는 효율적이지 않을 수 있다. 이 글에서는 어떤 수를 입력으로 받아, 그 수가 소수인지 아닌지를 판별하는 방법을 적어둔다. 접근 소수는 1과 자기 자신을 제외한 어떤 수로도 나누어 떨어지지 않는 수를 말한다. 어떤 수가 소수인지 아닌지 판별하기 위해서는 약수의 성질을 먼저 생각해봐야 한다. 약수는 제곱근을 기준으로 대칭을 이룬다. 따라서 어떤 수의 약수를 찾을 때 제곱근까지만 확인하면 나머지 약수는 자연스럽게 구할 수 있다. 즉, 어떤 수가 소수인지 아닌지를 판별하고 싶을 때..

개요 중복을 허용하고 반복 가능한 데이터에서 특정 데이터 기준으로 등장한 순서를 확인하고 싶다. 예로 들어 실행할 로직명과 설정값이 정의되어 있는 데이터가 있다고 할 때, 각 실행을 구분할 수 있도록 구분자를 추가해야 하는 상황이다. 추가할 구분자는 '실행 로직명_로직 등장 순서' 정도의 형식이면 충분할 것 같다. 반복 가능한 데이터에서 특정 데이터의 수를 세는 것이 아니라서 count 등의 함수는 사용할 수 없을 것 같아, 구현한 내용을 간단히 정리해 둔다. 사용한 프로그래밍 언어는 Python이다. 값 예시 처리할 데이터 예시는 아래와 같다. 실행할 로직명과 처리 데이터의 시작 시점, 처리 데이터의 종료 시점으로 구성되어 있다. washer_filter, 2023-11-17 03:00:00, 2023..

개요 수학에서 약수(divisior)란 어떤 수를 나누어 떨어지게 하는 수를 말한다. 알고리즘 문제를 풀다 보면 약수를 다룰 일이 많다. 보통 어떤 수의 모든 약수를 찾는다던가, 약수의 개수를 찾게 되는데 이 글에서는 어떤 수의 모든 약수를 찾는 방법을 적어둔다. 일반적인 방법 약수를 찾을 때 가장 단순하게 접근하는 방법은 반복문을 활용하는 것이다. 예로 들어 100의 모든 약수를 찾는다고 가정할 때 1부터 100까지의 모든 수에 대해 100을 나누어 떨어지게 하는 수를 찾는 것이다. def get_divisior(num): result = [] for i in range(1, num + 1): if num % i == 0: result.append(i) return result if __name__ =..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/132267 다음과 같은 콜라 문제가 있다. 콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가? 단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다. 상빈이는 그림과 같은 방법으로 콜라 문제를 풀어냈다. 빈 콜라병 20병을 가져가서 10병을 받는다. 받은 10병을 비우고 5병을 받는다. 5병 중 4병을 비우고 2병을 받고, 또 2병을 비우고 1병을 받는다. 받은 1병과 5병을 받았을 때 남은 1병을 비워서 1병을 또 받는다. 따라서 총 10 + 5 + 2 + 1 + 1 = 19병의 콜라를 받는다. 만약 빈 병 a개를 가져다..