알고리즘 (15) 썸네일형 리스트형 BFS 너비 우선 탐색 너비 우선 탐색이란? 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘 방법? 각 정점을 방문할 때마다 모든 인접 정점들을 검사 이 때 처음 보는 정점을 방문하면 이 정점을 방문 예정이라고 기록해 둔 뒤, 별도의 위치에 저장 인접한 정점을 모두 검사하고 나면, 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문 즉, BFS의 방문 순서는정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정 수행 예 C++ 코드 #include #include #include using namespace std; vector adj; // 너비 우선 탐색 구현 // start에서 시작해 그래프를 너비 우선 탐색하고 각 정점의 방문 순서를 반환 vector bfs(int start) { // 각 정점의 방문 여부 v.. 펜윅 트리(fenwick tree) 펜윅 트리 바이너리 인덱스 트리(binary indexed tree)라고도 함 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결할 수 있음 0이 아닌 마지막 비트를 찾는 법 : 특정 숫자 K의 0이 아닌 마지막 비트를 찾기 위해서는 K & -K 계산하면 됨 트리 구조 만들기 : 0이 아닌 마지막 비트 = 내가 저장하고 있는 값들의 개수 업데이트 : 0이 아닌 마지막 비트만큼 더하면서 구간들의 값 변경 (예시 = 3rd) 3번째 값이 변경되었다면, 3, 4, 8, 16이 3번째 인덱스에 대한 합 정보를 가지고 있는 인덱스이기 때문에 해당 인덱스들의 값을 업데이트 하면 됨 -> 시간 복잡도가 최악의 경우에도 O(logn)을 보장 1부터 N까지 누적합 구하기 : 0이 아닌 마지막 비트만큼 빼면서 구.. 탐욕법(Greedy) 탐욕법이란? 원하는 답을 재귀 호출처럼 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어감 모든 선택지 중 가장 좋은 답을 찾는 완전탐색/동적 계획법과 달리 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택 즉, 탐욕법은 지금의 선택이 앞으로 남은 선택에 어떤 영향을 미칠지 고려하지 않음 탐욕 알고리즘을 이용할 경우 알고리즘의 정당성을 증명하는 과정이 필요함 탐욕법이 적용되는 사례 탐욕법을 사용해도 항상 최적해를 구할 수 있을 경우 (동적 계획법보다 수행시간이 훨씬 빠름) 시간/공간적 제약으로 인해 다른 방법으로는 최적해를 찾기 어려울 경우(최적해 대신 근사해 찾는 것으로 타협) [예제] 회의실 예약 회사에 회의실이 하나밖에 없는데, n개의 팀이 각각 회의하고 싶은 시간을 제출했다... 우선순위 큐 우선순위 큐 ADT (키, 원소) 쌍의 형태로 저장 예시 : 탑승 대기자(ex. 키: 예약 시간, 원소: 승객), 경매(ex. 키: 가격, 원소: 가격을 제시한 사람), 주식 시장 등 주요 메쏘드 insertItem(k, e) : 키 k인 원소 3를 큐에 삽입 element removeMin() : 큐로부터 최소 키를 가진 원소를 삭제하여 반환 일반 메쏘드 integer size() : 큐의 항목 수를 반환 boolean isEmpty() : 큐가 비어있는지 여부를 반환 접근 메쏘드 element minElement() : 큐에서 최소 키를 가진 원소 반환 element minKey() : 큐에서 최소 키를 반환 예외 emptyQueuException() : 비어있는 큐에 삭제/접근 시도할 경우 full.. [C++]백준 2630 색종이 만들기 문제 링크 : https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종.. [C++]algospot FENCE 문제 링크 : https://www.algospot.com/judge/problem/read/FENCE algospot.com :: FENCE 울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체 www.algospot.com 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. .. [C++]algospot QUADTREE 문제 링크 : https://www.algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 www.algospot.com 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드.. 분할 정복 분할 정복이란? 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤, 각 부분 문제에 대한 답을 재귀 호출을 이용(basecase : 상수 크기의 부문제들)해 계산하고, 그 답으로 부터 전체 문제의 답을 계산 일반적 재귀 호출과의 차이점 ? 문제를 나누는 크기 ! 재귀 호출은 문제를 한 조각과 나머지 전체로 나누지만, 분할 정복은 거의 같은 크기의 부분 문제로 나눔 예제 1) 분할 정복을 이용한 수열의 합 구하기 fastSum(n) = 1+2+3+...+n = (1+2+3+..+n/2) + ((n/2+1)+...+n) = (1+2+3+..+n/2) + (n/2+1) + (n/2+2) + ... + (n/2 + n/2) = (1+2+3+..+n/2) + n/2 * n/2 + (1+2+...+n/2) = fast.. 이전 1 2 다음
