Computer Science & Engineering

    이번에는 저번 파일처리와 파일구조에 대하여 설명한 글에서 설명한 sequential access, simple index 방법에 이어서 BST와 B-Tree(B+Tree)에 대하여 알아보자.

    우선 잘 알려진 BST인 이진탐색 트리에 대하여 설명하자면 한 노드로부터 왼쪽에는 그 노드보다 작은 값, 오른쪽에는 큰 값이 있는 트리를 말한다. 아래의 그림과 같이 삽입 순서대로 노드를 탐색하며 해당 리프노드까지 비교한 다음 추가된다. BST는 평균적으로 O(logN)의 시간 복잡도를 가지며 레코드를 삽입, 삭제가 쉽다는 장점이 있다. 하지만 아래의 오른쪽 그림과 같이 한 쪽 방향으로 치우치며 트리가 형성되는 skew현상이 발생할 수 있다. 이 경우에는 시간 복잡도가 O(N)으로 순차처리와 같게 된다. 

이러한 문제점이 발생하기 때문에 이를 보완한 방법으로 AVL 트리가 나타났다. AVL 트리는 일정한 k값을 정하여 임의의 한 노드로부터 왼쪽 SubTree와 오른쪽 SubTree의 높이가 같게 유지하는 방법이다. 하지만 이 방법을 사용하더라도 파일처리에서 BST를 사용한다는 점은 이전 글에서 말했듯이 Secondary Storage로부터 적은 비용에 많은 정보를 얻어오기에 한계가 있다. 예를 들어 1000번째 있는 레코드를 탐색한다고 생각해보자 이 경우 BST를 사용했을 때 9번~10번의 디스크 접근이 필요하다(2^10이 1024이므로). 약 10번의 디스크 접근도 상당히 부담스러울 수 있다. 이를 보완한 방법으로 B-Tree가 나왔다.

    B-Tree 전에 B+Tree를 설명하겠다. B+Tree는 BST와 달리 한 노드에 하나의 키값이 아니라 여러개의 키값을 가진다. 또한 트리를 balance한 상태로 유지할 수 있기 때문에 skew가 발생하지 않는다. 따라서 모든 리프노드들이 같은 레벨을 가지고 있다. BST와의 또다른 차이점은 트리의 모양이다. BST의 경우 아래 그림의 왼쪽과 같이 좁은 너비에 큰 높이를 가지고 있지만 B+Tree의 경우 오른쪽 그림과 같이 형성되기 때문에 넓은 너비에 낮은 높이를 가지고 있다. 이러한 특징은 파일처리에서 상당히 중요하다. 그만큼 적은 디스크 접근이 발생하기 때문이다. 

아래 그림은 B+Tree 예시이다.

    이 B+Tree에서는 한 노드에 최대로 들어갈 수 있는 key의 개수가 3인 B+Tree이다. 여기서 리프노드가 아닌 non-leaf 노드의 키 왼쪽, 오른쪽에는 다음 노드를 가리키는 포인터가 존재한다. 실제 구현에서의 포인터는 주소이다. 그리고 leaf노드에서는 simple index 방식에서 주소를 가지는 것과 같이 각 key마다 실제 레코드파일의 포인터가 존재한다 위 그림에서는 빨간색 화살표 표시로 표현했다. 그리고 leaf노드는 다음 노드에 대한 포인터를 가진다(파란색 화살표). 이 포인터를 이용해 B+Tree에서는 순차탐색을 할 수 있는 장점이 있다. 또 하나의 특징은 임의의 노드에서 하나의 키값은 그 키 값의 오른쪽 SubTree의 가장 왼쪽 leaf node와 같다. 즉 루트노드인 60의 오른쪽 서브트리에서 가장 왼쪽에 있는 값이 60이라는 말이다. 다음 B-Tree에 대하여 설명하겠다. 아래 그림은 위 그림을 B-Tree로 나타낸 것이다.

    전체적인 구조는 B+Tree와 동일하다. 하지만 큰 차이점들이 있다. 우선 리프노드들이 서로 링크드리스트로 이어져있지 않다. 즉 순차탐색이 불가능하다는 단점이 있다. 하지만 B-Tree의 장점도 있다. 각 노드에서 레코드 파일에 대한 포인터가 존재한다(빨간 화살표). 즉 B+Tree와 달리 B-Tree는 리프노드까지 탐색하지 않고도 레코드파일의 주소를 알 수 있다. 또 하나의 차이점은 B+Tree와 달리 트리에 중복된 키가 존재하지 않는다. B+Tree에서는 임의의 노드에서 키값과 그 키값의 오른쪽 서브트리의 가장 왼쪽 키값이 같다는 특징이 있었다. 즉 중복된 키가 트리에 존재한다는 것이다. 하지만 B-Tree에서는 각 노드에서 곧바로 포인터를 가지기 때문에 중복된 키를 가지지 않게 된다.

    우선 File에 대하여 설명하자면 파일이란 secondary memory(HDD, SSD, CD, tape 등)에 저장된 같은 형식을 가진 record들의 집합이다. 그렇다면 File Structure는 무엇인가? 파일 구조란 File Structure는 데이터를 표현하는 representation과 그 데이터를 접근하는 operation의 조합이다. 여기서 representation의 예시로는 C언어의 구조체가 있고 operation은 삽입(insert), 삭제(delete), 검색(search) 등이 있다. 우리가 좋은 파일 구조를 만들기 위해서는 데이터로부터 정보를 얻을 때 가장 적은 비용이 들어야한다. 파일처리에서 가장 많이 드는 비용은 디스크 접근이다. 그렇기 때문에 좋은 File Structure를 만들기 위해서는 Disk I/O를 줄여야한다. 앞의 내용을 요약해보면 따라서 파일처리란 파일에 접근하여 직접 구현한 연산들로 데이터를 다루는 것이라고 할 수 있다.

    우리가 앞서 말한 Disk I/O를 줄이기 위해서는 어떻게 해야할까? 얘를 들어 하드디스크(HDD)에 저장된 100명의 사람들 중에 홍길동씨의 정보를 찾는다고 생각해보자. 인간이 아니라 컴퓨터가 홍길동씨를 찾기 위해서는 가장 쉬운 방법으로 첫 번째 사람부터 차례대로 비교해보는 것이다. 이런 방식을 썼을 때 만약 홍길동씨가 77번째 record에 존재한다면 컴퓨터는 77번의 비교를 해야 찾을 수 있을 것이다. 이러한 방식을 Sequential access 순차접근이라고 한다. 그렇다면 빠른 방법은 어떤 것이 있을까? 우선 Simple index 방식을 알아보자 아래 그림과 같이 HDD에 저장된 모든 record파일을 읽어오기엔 파일이 너무 클 수가 있다. 따라서 index file을 따로 만들어 그림 왼쪽과 같이 이름과 record의 주소만 정렬하여 저장한다. 이 index file은 크기가 작기 때문에 main memory인 RAM에 모두 올릴 수 있다. 그 다음 RAM에서 이진탐색과 같은 방식으로 홍길동을 찾아 HDD의 해당 위치부터 record를 읽어오면된다.

따라서 순차처리의 경우 record파일을 한 줄씩 읽어온다면 총 3번의 Disk I/O가 발생하지만 Simple index 방식의 경우 index file을 읽어오는 비용 1번과 알아낸 주소로 접근하여 홍길동의 record를 읽어오는 1번으로 총 2번의 Disk I/O가 발생한다. 위 그림의 경우는 작은 크기이기 때문에 큰 차이가 있지 않지만 만약 record의 수가 굉장히 많은 경우 그 비용의 차이가 굉장히 커질 것이다.

   이렇게 simple index 방식은 Random access가 가능하기 때문에 시간적인 비용이 줄어든다. 하지만 record가 추가될 경우 index file도 같이 수정해야하는 번거로움이 존재한다. 이 외에도 Binary Search Tree, B-Tree, B+Tree 등 많은 방식이 존재하지만 다른 글에서 설명하도록 하겠다.

Flash memory의 Software의 구성 방식은 다음과 같이 계층적 구조로 이루어져 있다.

우리가 사용하는 Application에서 발생하는 read, write와 같은 연산들은 우리에게는 보이지 않지만 아래의 layer에 의해 투명하게 처리된다.

    우선 Flash File System은 대표적으로 FAT(file allocation table) file system이 있다. 이 계층에서는 application layer에서 호출한 read, write 연산을 수행하는 일반적인 파일 시스템이다.

    FTL(Flash Translation layer)는 우리가 사용하는 NAND 플래시 메모리를 일반 하드디스크와 같은 블록장치와 같이 행동하기 위해 논리주소를 물리주소로 mapping하는 기능을 수행한다. 이때 논리주소와 물리주소를 mapping되어 있는mapping table을 사용한다. Flash memory는 덮어쓰는 overwrite 기능을 제공하지 않기 때문에 out-of-place update를 사용한다. 따라서 block mapping table에는 항상 overwrite를 할 때 사용하는 free block을 두어 out-of-place update이 이루어질 때 사용한다. 또 하나의 block에 많은 erase, write가 이루어지는 bad block이 발생하지 않도록 하는 wear-leveling 기능도 제공한다.

    Flash Device Driver는 직접 NAND 플래시 메모리에 물리적으로 접근하여 데이터를 읽고 쓰는 역할을 수행하는 계층이다. 또 bad block와 ECC(Error Correction Code)를 처리한다.

    위와 달리 Flash File system 계층과 FTL 계층을 하나의 계층인 Dedicated Flash File System도 존재한다. 그러한 구조는 플래시 메모리 전용으로 설계된 파일 시스템에서 사용된다.

    FTL에서 논리주소와 물리주소를 mapping하는 방법에는 여러가지가 있다. 대표적으로 sector mapping, block mapping, hybrid mapping이 존재한다. 글쓴이가 구현한 방식은 block mapping 기법을 사용하였다. 이 세가지 기법을 간단히 설명하자면 sector mapping은 lsn(logical sector number)와 psn(physical sector number)가 1대1로 mapping되어 있는 방법이다. 이 경우 mapping table이 굉장히 커질 수 있는 단점이 존재한다. block mapping table 기법은 lsn을 블록당 페이지의 수로 나눈 몫을 block번호로 사용하고 나머지를 page번호로 사용하는 방법이다. 예를 들어 lsn이 9이고 한 블록당 page의 수가 4개인 경우 9/4 = 2가 블록 번호(pbn), 9%4 = 1이 블록의 page번호(ppn)인 것이다. 이 경우에 한 블록에 4개의 page가 존재하므로 sector mapping 방식에 비해 mapping table이 1/4로 줄일 수 있는 이점이 있다. 마지막으로 hybrid mapping 방식은 block mapping과 굉장히 유사하지만 나머지인 offset을 ppn으로 사용하는 것이 아닌 pbn의 비어있는 곳에 순서대로 할당한 후 page의 spare영역에 메타데이터인 lsn을 저장하여 어디서 저장된 데이터인지 알 수 있게한다.

    아래 링크는 C언어를 활용해 구현한 FTL의 block mapping table이다.

https://github.com/Seo-sang/file_processing_FTL

programmers.co.kr/learn/courses/30/lessons/64064#

처음 문제를 잘 이해하지 못하여 접근방법을 잘못 알았고 아래에 첨부한 풀이도 비효율적이지만 오랜 시간을 들여 풀었기 때문에 그대로 첨부하였다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int answer;
bool visit[9];
set<string> rst;
void dfs(int n, vector<string> &user_id, vector<string> &banned_id, string s) {
    if(n == banned_id.size()) {
        sort(s.begin(), s.end());
        rst.insert(s);
        return;
    }
    string now = banned_id[n];
    for(int i = 0; i < user_id.size(); i++) {
        if(visit[i] || now.size() != user_id[i].size()) continue;
        int chk = 0;
        for(int j = 0; j < now.size(); j++) {
            if(now[j] == '*') continue;
            if(user_id[i][j] != now[j]) {
                chk = 1;
                break;
            }
        }
        if(!chk) {
            visit[i] = 1;
            dfs(n+1, user_id, banned_id, s + to_string(i));
            visit[i] = 0;
        }
    }
    return;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    dfs(0, user_id, banned_id, "");
    answer = rst.size();
    return answer;
}

처음에는 그래프를 그려 2-sat으로 이분매칭을 이용하여 풀려고 했으나 뜻대로 되지 않아 백트래킹을 이용하여 풀었다. 

ban사용자를 하나씩 선택하여 방문하지 않은 user중 일치하는 것이 있는지 확인한 후 재귀적으로 반복한다. dfs함수의 맨 마지막 인자인 string은 지금까지 일치된 사용자의 인덱스 번호이다. 사용자를 모두 찾은 경우 string s를 정렬하여 set에 집어 넣는다. 이 과정은 중복이 일어나지 않게 하기 위해서이다. 모든 과정을 끝낸 후 set의 사이즈를 리턴하면 된다.

programmers.co.kr/learn/courses/30/lessons/64065

이 문제에서는 각 집합을 탐색하며 숫자인지를 판별하고 검색될 때마다 검색된 횟수를 1씩 올려주는 방식으로 풀이했다.

#include <string>
#include <vector>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
using namespace std;

bool cmp(pair<int,int> a, pair<int,int> b) { //sort 비교 함수
    return a.second > b.second; //검색횟수가 많은 순서대로 저장
}

vector<int> solution(string s) {
    vector<int> answer;
    char num[100001] = {0}; //숫자를 만들 배열
    vector<int> arr;
    vector<pair<int,int>> tmpans;
    bool visit[501]; //탐색한지 확인
    int cnt = 0;
    int idx = 0;
    for(int i = 0; i < s.length(); i++) {
            if(s[i] == '{') { //시작시 메모리 초기화
                idx = 0;
                memset(visit, 0, sizeof(visit));
                memset(num, 0, sizeof(num));
            }
            else if(s[i] == '}') {
                if(num[0] != 0) { //숫자생성
                    int n = atoi(num);
                    memset(num, 0, sizeof(num));
                    arr.push_back(n);
                    cnt++; //한 집합에서 숫자의 개수 추가
                }
                else {//입력의 마지막 '}'인 경우
                    continue;
                }
                if(arr.size() != 0) { //집합에 숫자가 있는 경우
                    if(cnt < tmpans.size()) { //만약 지금까지 탐색한 튜플의 원소가 더 많은 경우 검색횟수만 +1
                        for(int j = 0; j < tmpans.size(); j++) {
                            for(int k = 0; k < arr.size(); k++) {
                                if(tmpans[j].first == arr[k]) {
                                    tmpans[j].second++;
                                }
                            }
                        }
                    }
                    else { //새로운 튜플 원소가 나타난 경우
                        for(int j = 0; j < arr.size(); j++) {
                            int chk = 0;
                            int k;
                            for(k = 0; k < tmpans.size(); k++) {
                                if(visit[k]) { //탐색한 튜플 원소 건너뜀
                                    continue;
                                }
                                if(tmpans[k].first == arr[j]) { //이미 검색된 원소는 검색횟수 1추가
                                    tmpans[k].second++;
                                    visit[k] = 1;
                                    chk = 1;
                                    break;
                                }
                            }
                            if(!chk && (k == tmpans.size())) { //새로운 원소 추가하고 검색횟수 1로 설정
                                tmpans.push_back({arr[j], 1});
                            }
                        }
                    }
                    memset(visit, 0, sizeof(visit));
                }
                else continue;
                cnt = 0;
                arr.clear();
                idx = 0;
                memset(num, 0, sizeof(num));
            }
            else if(s[i] ==  ',') {
                if(num[0] != 0) { //집합을 구분 짓는 ','이 아닌 경우
                    int n = atoi(num);
                    arr.push_back(n);
                    memset(num, 0, sizeof(num));
                    cnt++;
                }
                memset(num, 0, sizeof(num));
                idx = 0;
                continue;
            }
            else { //10진수 숫자 생성
                num[idx++] = s[i];
            }
    }
    sort(tmpans.begin(), tmpans.end(), cmp); //검색 횟수 순으로 정렬
    for(int i = 0; i < tmpans.size(); i++) { //정답 옮겨 저장
        answer.push_back(tmpans[i].first); 
    }
    return answer;
}

임시 정답 vector를 선언하고 원소와 검색된 횟수를 저장한다. 모든 집합을 탐색하며 기존에 검색된 원소 수보다 많은 경우 모두 1씩 증가하고 없는 원소는 추가하여준다. 입력값을 모두 탐색한 후 가장 많은 빈도의 원소 순으로 정렬되므로 정답에는 원소만 옮겨 저장해준다. 

programmers.co.kr/learn/courses/30/lessons/64061

이 문제에서는 vector로 입력이 주어진다. 주의해야할 점은 주어진 NxN 행렬에서 탐색하려는 행만 접근하는 것이 아닌 0번 행부터 N-1번 행까지 0이 아닐 때 까지 열을 모두 탐색해야한다는 점이다. 즉 한 행은 뽑기 기계의 깊이를 나타낸다. 아래는 풀이한 코드이다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    vector<int> arr;
    int answer = 0;
    for(int i = 0; i < moves.size(); i++) { 
        int idx = moves[i]-1; //탐색하고자 하는 열
        int doll = 0;
        for(int j = 0; j < board.size(); j++) { //해당 각 행에서 인형이 있는지 확인
            if(board[j][idx] != 0) { //인형이 발견한 경우
                doll = board[j][idx];
                board[j][idx] = 0;
                break;
            }
        }
        if(doll == 0) continue; //인형을 발견하지 못한 경우
        if(arr.size() == 0) { //뽑은 인형을 담는 바구니가 비어있는 경우
            arr.push_back(doll);
            continue;
        }
        else if(arr.back() == doll) { //바구니 맨 위에있는 인형과 뽑은 인형이 같은 경우
            arr.pop_back();
            answer+=2; //이미 있는 인형과 발견한 인형 모두 사라지므로 +2
        }
        else arr.push_back(doll); //바구니 맨 위에있는 인형과 뽑은 인형이 다른 경우
        
    }
    return answer;
}

뽑으려고하는 열들은 move라는 vector로 주어진다. 뽑기를 진행하며 주어진 행렬 board의 해당 열에 인형이 있는지 확인한다. 인형이 있는 경우 바구니인 arr의 마지막 값과 비교한다. 만약 arr가 비어있는 경우 push_back을 하고 arr의 마지막 값이 인형과 같은 경우 두 인형 모두 터져서 사라지고 인형 2개가 사라지므로 answer를 2 올려준다. 마지마으로 인형이 다른 경우 마지막에 push_back해준다.

최단 경로를 탐색하는 알고리즘에서 한 정점에서 다른 모든 정점까지 탐색하는 알고리즘에는 대표적으로 두 가지가 있다. 하나는 다익스트라 알고리즘이고 다른 하나는 벨만-포드 알고리즘이다. 두 알고리즘의 차이점은 대부분 알다시피 간선의 가중치에 음수가 있느냐(벨만-포드) 없느냐(다익스트라)이다.

이 점은 누구나 알고 있지만 실제로 코드에서 어떠한 차이점이 있는 지는 설명만 보고 알기 어려워 비교를 해보려고 한다.

우선 대표적인 다익스트라 알고리즘 문제인 백준 1753번 문제를 푼 알고리즘이다.

www.acmicpc.net/problem/1753 

다익스트라 알고리즘

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

int INF = 2123456789;

struct edge { //간선의 가중치와 목적지 구조체
	int w, v;
};

vector<edge> g[20001]; //그래프 간선 구조체
int dist[20001]; //시작점에서 모든 정점까지의 최단 경로를 저장할 dp배열

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
	int V, E, K; cin >> V >> E >> K;
	for(int i = 0; i < E; i++) {
		int u, v, w; cin >> u >> v >> w;
		g[u].push_back({w, v}); //그래프의 간선 정보 입력
	}

	fill(dist + 1, dist + 1 + V, INF); //시작점에서 모든 정점은 아직 방문하지 않았으므로 INF로 초기화

	using P = pair<int,int>; //pair 표현 간소화
	priority_queue<P, vector<P>, greater<P>> pq; //최소힙 구현
	pq.push({0, K}); //처음 시작점 push
	dist[K] = 0; //시작점은 최단 경로 0으로 초기화
	while(!pq.empty()) { //더 이상 갱신할 최단 경로가 없을 때까지
		P tmp = pq.top(); pq.pop(); //새로 뻗을 수 있는 간선 중에 가중치가 가장 작은 값
		int cur_w = tmp.first;
		int cur = tmp.second;

		if(dist[cur] < cur_w) continue; //최소값 아닐 경우 건너뛰기

		for(edge next : g[cur]) { //새로 뻗은 간선에서 뻗을 수 있는 모든 간선에 대하여
			if(dist[next.v] > dist[cur] + next.w) { //최소값을 갱신할 수 있으면 갱신하고 우선순위 큐에 push
				dist[next.v] = dist[cur] + next.w;
				pq.push({dist[next.v], next.v});
			}
		}
	}
	for(int i = 1; i <= V; i++) {
		if(dist[i] == INF) //최단 경로가 없으면 INF
			cout << "INF" << '\n';
		else
			cout << dist[i] << '\n'; //최단 경로가 있으면 최단 경로 출력
	}
	return 0;
}

www.acmicpc.net/problem/11657

벨만 포드 알고리즘

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

struct edge { //간선의 정보를 저장할 구조체
    long long w, v;
};

int INF = 987654321;
vector<edge> g[501]; //그래프 간선 표현 vector배열
long long dist[501]; //최소값을 저장할 dp배열

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; cin >> N >> M;
    for(int i = 0; i < M; i++) {
        long long a, b, c; cin >> a >> b >> c;
        g[a].push_back({c, b}); //간선 정보 저장
    }
    fill(dist, dist+N+1, INF); //모든 정점까지 최단 경로 INF로 초기화
    dist[1] = 0; //시작점 최단 경로 0으로 초기화

    for(int i = 1; i <= N; i++) { //N번 반복
        for(int j = 1; j <= N; j++) { //j에서 다른 정점으로 뻗을 수 있는 간선의 정점 최솟값 갱신
            if(dist[j] == INF) continue; //최단 경로가 없는 경우 건너뛰기
            for(edge next : g[j]) { //j에서 뻗을 수 있는 간선에 대하여
                if(i < N) { //모든 정점 갱신할 수 있는 N-1번 반복까지는 최단 경로 갱신
                    if(dist[next.v] > dist[j] + next.w) { //최단 경로 갱신
                        dist[next.v] = dist[j] + next.w;
                    }
                }
                else { //만약 모든 최단 경로를 갱신한 다음 N번째에도 최솟값을 갱신하는 경우
                    if(dist[next.v] > dist[j] + next.w) { //무한히 최단 경로를 갱신하므로 -1출력하고 프로그램 종료
                        cout << -1 << '\n';
                        return 0;
                    }
                }
                
            }
        }
    }
    for(int i = 2; i <= N; i++) {
        if(dist[i] == INF) cout << -1 <<'\n'; //최단 경로가 없는 경우 -1 출력
        else cout << dist[i] <<'\n'; //최단 경로 출력
    }

}

위와 같이 두 가지 알고리즘을 작성해보았다.

간선에 음의 가중치가 없는 다익스트라의 경우 최솟값이 무한히 갱신되는 경우가 없기 때문에

우선순위 큐를 이용하여 갱신할 최단 경로가 존재하지 않을 때까지만 반복하면 된다.

하지만 음의 가중치가 있는 벨만 포드의 경우 다익스트라처럼 우선순위 큐를 사용할 경우

최단 경로를 갱신하는 경우 우선선위 큐에 push하고 큐가 모두 빌 때까지 반복하므로 아래 그림과 같이 1에서 4까지의 경로가 2-3-4를 순환하면서 최단경로가  -1씩 무한히 갱신될 수 있다.

따라서 정점의 수 N에 대하여 간선의 수는 최대 N(N-1)이므로 모든 정점에 대하여 N-1번 반복하면 모두 갱신할 수 있게 된다. 따라서 N번째 반복에서 최단 경로가 또 한 번 갱신된다면 이는 위의 그림처럼 무한히 갱신되는 경우가 된다.

이러한 이유가 벨만 포드에서 우선순위 큐가 빌 때까지가 반복문의 조건이 아닌 이유이다.