자료구조 및 알고리즘 스터디 (4) 썸네일형 리스트형 4. 분할정복과 이분탐색 Divide and Conquer: 분할정복1. 분할: 큰 문제를 잘게 쪼개고2. 정복: 쪼개진 작은 문제를 해결하고3. 병합: 결과를 합쳐서 큰 문제를 해결하자 큰 문제와 작은 문제가 "같은 구조" 로 이루어져 있을 때 적용하기 좋다.따라서 분할정복도 "재귀"를 이용하여 구현하는 경우가 많다. 색종이문제https://www.acmicpc.net/problem/2630#색종이를 4등분해도 여전히 정사각형 형태 유지.#부분문제가 전체 문제와 같은 구조. 재귀함수가 생각나지 않는가?n= int(input())board= [list(map(int,input().split())) for _ in range(n)]#1. 4등분한다#각각 쪼갠 색종이에 대해 solve 적용# 각 색종이의 개수를 활용하여 원래 사이즈.. 0. 시간복잡도와 정렬 시간복잡도와 공간복잡도 백준에는 시간제한과 메모리제한이 있는데 시간제한은 시간복잡도, 메모리제한은 공간복잡도. 시간복잡도는 보통 "최악의" 시간복잡도 Big-O(빅오)로 나타낸다.ex) O(nlogn)빅 오 계산법은1. 알고리즘 자체의 시간복잡도를 학습하거나2. 계산하면 된다.n이라는 입력이 주어졌을 때 이를 활용해 문제를 풀 때 필요한 코드 실행 횟수를 f(n)이라 하자.이때 어떤 특정 n₁ 이후의 모든 n에 대해, (즉, n₁ ≤ n)f(n) ≤ c*g(n) 을 만족하도록 하는 (n₁, c) 쌍이 존재하면(c는 양의 상수)• 이때의 g(n)에 대해 O(g(n)) 이라고 쓸 수 있다쉽게 말해n개 데이터로 구성된 문제를 푸는 연산량이 f(n) 일 때,일반적으로 n이 증가하면 연산량 f(n)도 같이 증가.. 1. 정렬, 그리디 알고리즘: 컴퓨터가 따라할 수 있도록 문제를 해결하는 절차 방법을 자세히 명시한 것 그리디greedy 알고리즘.탐욕법이라고 부른다. 어떠한 문제의 최적해를 찾고자 할 떄 눈앞의 최적을 탐욕스럽게 골라 전체의 최적해를 찾아보자.왜 탐욕적인가? "매 순간 가장 좋아보이는 선택(최선의 선택)"을 반복해서 문제를 해결함. 왜 이게 되냐면 각 단계에서의 최선의 선택이 전체 문제에 대해서도 최선의 결과가 나온다고 믿기 때문. 그러나 모든 문제에 해당하진 않는다.쉽게 설명하자면:그리디 알고리즘은 한 번 결정하면 다시 돌아보지 않습니다. 현재 상황에서 가장 좋다고 생각되는 선택을 반복합니다.이 선택이 쌓이고 쌓여서 최적해(가장 좋은 결과)가 되는 것이 목표입니다. *최적해란?제약 조건이 있을 경우 이를 만족하고, .. 1. 자료구조 stack 자료구조란?대량의 데이터를 효율적으로 관리하기 위함. 여러 알고리즘들을 효율적으로 구현하기 위함.수학(소수, 최댓값 등) -> 자료구조 -> 재귀 -> DP -> 그래프(DFS/BFS) -> 최단경로 -> 이분탐색 -> 분할정복 -> 그리디-> 완전탐색, 시뮬레이션, 구현-> 문자열 -> 투 포인터, 슬라이딩 윈도우 -> 백트랙킹배열(array)같은 종류의 데이터를 순차적으로 저장하는 자료구조index를 통해 접근 가능하며, 빠르게 접근 가능하다는 장점데이터 추가 및 삭제시 비용이 많이 사용되는 단점이 존재큐(Queue)가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조 (선입선출FIFO)시분할시스템 등 운영체제에서 많이 쓰임기능enqueue : 큐에 데이터를 넣는 기능을 의미 (append와 유사)dequ.. 이전 1 다음
