알고리즘 (18) 썸네일형 리스트형 펜윅 트리(Fenwick tree, Binary Indexed Tree) 변경되는 데이터 속에서 구간 합을 구하거나 최대/최소, 구간 곱 등을 구할 때 세그먼트 트리(링크)를 사용하였다. 하지만 세그먼트 트리는 N개의 배열이 있을 때 4*N개의 공간을 할당해야했기 때문에 많은 메모리를 필요로 하였다. 세그먼트 트리와 비슷한 역할을 하면서 N개의 공간을 사용하는 자료 구조가 있다면..? 그렇다. 그것이 바로 펜윅 트리이다. 펜윅 트리 펜윅 트리 또는 Binary Indexed Tree(BIT)라고 부른다. Binary Indexed Tree라는 이름에서 알 수 있듯이 인덱스로 이진수를 사용한다. 이것이 무슨 말이냐 하면, (그림 출처) n = 16인 위와 같은 배열이 있다고 가정하면, 각각의 수가 2진수로 나타냈을 때 어디에 마지막 1이 있는지를 알아야 한다. 1 = 0001(.. 백준 9251번 LCS C/C++ 풀이 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net DP 문제, 그 중에서도 2차 배열을 이용하면 쉽게 풀 수 있다. 각각의 string 글자 수를 가진 2차 배열을 만들어서 각각의 cell을 채워나간다. 각각의 글자가 같지 않을 때는 왼쪽이나 위(i나 j가 같은) 중에서 크기가 큰 열을 선택하고, 같은 상황이 온다면 왼쪽 위에서 1을 더한 뒤 왼쪽이나 위 열과 크기를 비교해서 합친다. string 입출.. 백준 5535번 패셔니스타 C/C++ 풀이 https://www.acmicpc.net/problem/5535 DP 문제 전의 선택한 옷의 화려함 정도와 현재의 날짜를 요소로 두고 동적계획법을 사용하였다. 어렵지 않기 때문에 나머지는 코드로 설명 #include #include #include #include using namespace std; #define MAX 201 FILE* in = fopen("input.txt", "r"); int n, d; int tmp[MAX]; int min_tmp[MAX]; int max_tmp[MAX]; int cool[MAX]; int cache[101][MAX]; //재귀를 사용한 DP int dp(int coolness, int day) { //d 날짜가 됐다면 return if (day == d) re.. 백준 2240번 자두나무 C/C++ 풀이 https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net DP 문제이다. DP는 메모이제이션을 위해 어떤 요소들을 저장할지가 가장 중요한데, 해당 문제에서는 3가지를 꼽을 수 있다. 현재 나의 위치, 현재 시각, 이동한 횟수 이에 따라서 현재 나의 위치와 떨어지는 자두의 위치에 따라 크게 4가지 선택이 가능한데, If(현재 나의 위치에서 자두가 떨어진다면) { 1. 현재 위치에서 움직이지 않고 자두를 먹는다 2. 현재 위치에서 움직이고 다음턴의 반전을 노려본다... 백준 5557번 1학년 C/C++ 풀이 https://www.acmicpc.net/problem/5557 DP 문제. 해당 idx에 어떤 sum을 가지고 있는가를 저장해나가며 함수를 진행시켜나간다. 계산 중간에 0~20을 넘어가는 경우 더이상 진행하지 않기 때문에 이를 저장하지 않는다. #include #include #define MAX 101 FILE* in = fopen("input.txt", "r"); int n; int array[MAX]; long long int cnt; long long int cache[MAX][21]; int dst; //재귀로 구현한 dp long long int dp(int idx, int sum) { //계산 값이 범위를 벗어나는 경우 return if (sum 20) return.. 백준 1633번 최고의 팀 만들기 C/C++ 풀이 https://www.acmicpc.net/problem/1633 1633번: 최고의 팀 만들기 문제 꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 �� www.acmicpc.net 전형적인 동적계획법 문제. 재귀함수와 메모이제이션을 이용해서 문제를 풀었다. #include #include #include using namespace std; FILE* in = fopen("input.txt", "r"); int white[1001]; int black[1001]; int cache[1001][16][16]; int n; int dp(int w, int b, int.. 백준 14502번 연구소 C/C++ 풀이 acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 문제에서 사용하는 범위의 크기가 크지 않아서 전체 map 안에서 벽과 바이러스가 없는 부분 재귀함수를 이용해서 3가지를 선택하고 그에 따라 안전 범위가 몇 개 생기는지를 구했다. #include #include using namespace std; FILE* in = stdin; #define MAX 8 int n, m; int map[MAX][MAX]; int cnt; int max = 0; int path[3]; bool c.. 백준 14501번 퇴사 C/C++ 풀이 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 동적계획법으로 풀었다. 배낭 알고리즘을 응용해서 풀었다. #include #include using namespace std; FILE* in = fopen("input.txt", "r"); #define MAX 15 int n; int time[MAX]; int pay[MAX]; int cache[MAX+1][MAX * 1000]; int dp(int idx, int cost) { //메모이제이션 if (cache[idx][cost] != 0) return cache[idx][cost]; if (idx == n) return cos.. 이전 1 2 3 다음
