티스토리

쏘

검색하기

블로그 홈

쏘

jingyoioi.tistory.com/m

_윤 님의 블로그입니다.

구독자: 0

방명록 방문하기

반응형

주요 글 목록

[Algorithm] 슬라이딩 윈도우 (Sliding Window) 슬라이딩 윈도우란? 고정 사이즈의 윈도우가 이동하며, 윈도우 내 데이터를 이용해 문제를 풀이하는 알고리즘 핵심 개념 윈도우란?? : 전체 데이터에서, 이번에 탐색할 특정 구간의 데이터를 의미 한 번 구했던 값을 재활용하는 알고리즘 윈도우의 크기(너비)는 변하지 않음 즉, 언제나 고정된 폭을 가지고 있음 교집합의 정보를 가지고, 윈도우가 이동할 때 변경되는 양쪽 끝 원소만 갱신하는 방법 리스트나 배열에서 일정 범위의 값을 비교할 때 유용 투포인터 알고리즘과 결합해 자주 사용됨 알고리즘 설명 윈도우의 크기 결정 윈도우를 데이터의 첫 부분에 위치 윈도우 내의 데이터 연산 처리 윈도우를 다음 방향으로 한 칸 이동 끝 데이터에 도달할 때까지 위의 3~4번 반복 시간 복잡도 평균, 최악, 최선 O(N) 적절한 활용.. 공감수 1 댓글수 4 2024. 2. 25.
[Algorithm] 병합 정렬, 합병 정렬 (Merge Sort) 병합 정렬, 합병 정렬이란? 데이터를 정확히 정확히 반으로 나누고, 분할된 부분에 대해 정렬 핵심 개념 분할 정복 알고리즘 > 분할 부분과 정복 부분으로 나뉨 재귀 활용 정렬 과정 모든 데이터가 한 개씩 남을 때까지 정확히 절반으로 나눔 (분할) 다시 데이터를 합치면서 정렬시작, 이때 배열 크기는 2의 배수로 커짐 ( 1 > 2 > 4 > 8 ) (정복) 두 배열의 0번 인덱스부터 비교하며 더 작은 수를 먼저 결과 배열에 넣음 -> 두 배열을 모두 순회할때까지 반복 만든 배열을 원래 배열에 복사 배열 크기가 원본 크기가 된다면 종료 시간 복잡도 O(NlogN) 항상 데이터를 절반으로 나누기 때문에 O(NlogN)을 보장 구현 import java.util.*; public class MergeSort {.. 공감수 0 댓글수 0 2024. 2. 18.
[Algorithm] 삽입 정렬 (Insertion Sort) 삽입 정렬이란? 앞에서부터 차례대로 이미 정렬된 부분과 비교해 자신의 위치를 찾아냄으로써 정렬 핵심 개념 정렬할 자료를 두 개의 부분 집합 S, U로 가정 부분집합 S : Sorted, 정렬된 앞 부분 원소 부분집합 U : UnSorted, 아직 정렬되지 않은 나머지 원소들 이때, 반드시 S는 U보다 앞에 위치해야 함 정렬 과정 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내, 이미 정렬된 부분집합 S의 마지막 원소부터 비교하며 위치 찾아 삽입 삽입 정렬을 반복하며 부분집합 S의 원소는 하나씩 늘리고, 부분집합 U의 원소는 하나씩 감소 부분집합 U가 공집합이 되면 삽입 정렬 종료 왜 마지막 원소부터 비교할까? 반드시는 아니지만 특정 케이스에서 연산 횟수를 줄일 수 있는 장점이 있기 때문에 어떤 케이스? .. 공감수 0 댓글수 0 2024. 2. 16.
[Algorithm] 그리디 탐욕 (Greedy) 그리디 알고리즘(Greedy), 탐욕법이란? 선택의 순간마다 당장 눈앞에 보이는 최적의 답을 골라 최종 해답에 도달하는 방법론 아래의 사진에서 가장 큰 값을 구해야 한다면? 그리디는 현재 상황에서 최적의 답을 구할 뿐, 최종 해답에 도달한 답이 가장 좋은 답임을 보장하지는 않음 그렇다면 그리디 알고리즘을 어떻게 믿고 쓸 수 있지? 이를 위해서 문제가 아래 활용 조건 2개를 만족하는지를 따져보고, 적용 가능한 문제에서만 활용 아래의 조건 2개가 만족된 구조를 매트로이드라고 함. 어떤 문제가 매트로이드 구조라는 것은 최종 해답에 도달한 답이 가장 좋은 답임을 보장함 따라서 그리디를 적용할 수 있는 문제는 항상 최적해를 구하는 문제가 됨 등장 배경 : 동적 계획법 간단한 문제의 경우, 동적 계획법은 지나치게 .. 공감수 0 댓글수 0 2024. 2. 4.
[Algorithm] 동적 계획법 (Dynamic Programming : DP) 동적 계획법 (Dynamic Programming)이란? 큰 문제를 작은 문제로 나누고, 작은 문제들의 답을 이용해 큰 문제의 답을 구하는 방법론 등장 배경 : 피보나치 수열 f(n-2) + f(n-1) = f(n) 피보나치 수열 알고리즘은 재귀 함수 알고리즘을 활용 항이 커져갈수록 굉장히 많은 중복 호출이 발생한다는 문제점 발생 재귀 : 자기 자신을 호출하는 함수 [활용 조건] 어떤 경우에서 활용할 수 있을까? DP를 사용하기 위해서는 아래 두 가지의 조건이 만족되어야 함 최적 부분 구조 (Optical Substructure) 작은 문제들의 최적의 답을 이용해 큰 문제의 최적의 답을 구할 수 있어야 함 즉, 큰 문제의 답에 작은 문제의 답이 포함되어 있음 부분 문제 반복 (Overlapping Sub.. 공감수 0 댓글수 0 2024. 2. 4.

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.