Computer Science/알고리즘

IMOS (いもす法, imos法) 정의 누적합 문제에서 쓸 수 있는 개념 정해진 구간 내에 시작과 끝이 포함된 부분 집합에 대한 명령이 여러개 들어올 때, 반복적으로 연산하게 되면 연산 시간이 매우 커질 수 있다. 예시문제) 도서관 좌석 예약된 수time[0]~time[100000] 의 시간이 있다.입력으로는 각 개개인의 좌석예약시작시간과 종료시간이 들어온다.이를 time[i]+=1로 수행하면 정확도는 통과하지만 속도가 무지하게 느려질 수 있다.이때 효율적으로 사용할 수 있는 것이 imos알고리즘이다. Imos의 시간복잡도는 배열의 길이이다. 1차원: O(H), 2차원: O(HW) (H:가로, W:세로) 1차원에서의 구현 방법 시작시간과 끝시간을 기록하여 준다. 먼저 각 시간에 대한 1차원 배열을 생성하..

투포인터의 정의 및 장단점 Two Pointers 는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘 여기서 두 개의 포인터를 사용하여 기존의 방식보다 시간을 개선할 수 있습니다. 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다. 투 포인터 알고리즘은 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘을 뜻한다. 보통 lt(left), rt(right)나 s(start), e(end) 같은 식으로 포인터의 이름을 붙인다. 예제 문제 - 특정한 합을 가지는 부분 연속 수열 찾기 투포인터 알고리즘의 대표적인 문제입니다...

최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립되어 있다. 예를 들면 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 등의 다양한 사례가 존재한다. 상황에 맞는 알고리즘을 알고 있다면 문제를 좀 더 쉽게 풀 수 있다. 대표적으로 사용하는 최단 거리 알고리즘은 3가지인데 다익스트라(데이크스트라), 플로이드 워셜, 벨만 포드 알고리즘 이다. 이중 다익스트라와, 플로이드 워셜은 꼭 알아야 한다. 이 두가지에 대해서 설명을 하고 추후에 벨만 포드 알고리즘에 대해서 포스팅하겠다. 다익스..

다이나믹프로그래밍의 정의 및 장단점 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경 쓰지 않아도 된다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. '기억하며 풀기'라고 부르기도 한다. DP를 쓰는 이유 왜 DP를 사용할까? 사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번..

정의 및 장단점 순차탐색(일반적인 탐색)과 달리 이진 탐색은 배열내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이진 탐색은 매우 빠른 탐색이다. 탐색범위를 절반씩 좁혀가며 데이터를 탐색한다. 이진탐색은 위치를 나타내는 변수3개를 사용하는데 탐색하고자 하는 범위의 시작점(low),중간점(middle),끝점(high)이다. 찾으려는 데이터와 중간점(mid)위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다. log2N의 시간이 걸리고 빅오 표기법에 따라 간단하게 표현하면 O(logN)이다. 탐색대상의 데이터가 큰 문제의 경우 이진탐색을 이용하여 풀어야 한다. 문제조건을 잘 살피자. 이진탐색문제의 경우 이진탐색코드형식을 미리 암기 해놓으면 아주 쉽게 구현할 수..

정의 및 장단점 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열 하는 것을 말한다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 있어야 한다. 정렬 알고리즘은 굉장히 다양한데 대표적인 몇가지만 설명하겠다. 여러정렬은 각각의 장단점이 존재한다. 각 상황에 맞는 정렬을 선택하여야한다. 일반적으로 라이브러리에서 제공하는 정렬은 퀵소트 또는 변형된 퀵소트이다. 평균 nlogn에서 n^2의 시간복잡도를 가진다. 기수정렬: O(N) 또는 O(N+K) N은 개수, K는 숫자범위크기 (ex. 0~99면 100) 계수정렬: O(N) 또는 O(N+K) N은 개수, K는 최대자리수 선택 정렬(selection) 선택정렬은 앞에서부터 차례대로 정렬하는 방법입니다. 먼저 주어진 리스트 중에 최소값을 찾..

정의 및 장단점 BFS는 Breadth First Serach로 너비우선탐색이다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리있는 노드를 찍고 돌아오고 멀리갔다가 돌아로는 탐색이다. BFS는 그 반대이다. 구현방법 BFS는 큐 자료구조를 이용한다. 큐를 이용하면 자연스럽게 먼저들어온것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 된다. 파이썬에서는 deque라이브러리를 이용한 큐 자료구조를 사용하는 것이 보편적이다. 시간복잡도는 O(N)의 시간이 소요된다. 일반적인 경우 실제 수행시간이 DFS보다 좋은편이다. 문제에 따라 DFS의 경우 무한굴레에 빠져 시간이 엄청 길어 질수 있다. 하지만 BFS는 가까운노드에서부터 점차적으로 넓혀가기 때문에 보다 안정적이다. 모든 경우의..

정의 및 장단점 DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 연결되어 있는 노드를 깊숙히 바고 들어간다. 그 노드의 끝을 보고 다시 돌아오면서 연결되어있는 다른 노드를 찾을시 이번엔 그 노드를 끝까지 파고든다. 스택을 기초로 하고 있다. 구현방법 스택, 재귀함수를 이용하여 구현한다. 스택을 기초로 하지만 직접적으로 사용하지는 않음. O(N)의 시간이 소요. 문제 예시 NxM의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구머이 뚫려 있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크..