programmers.co.kr/learn/courses/30/lessons/60057?language=cpp 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자 programmers.co.kr 문제 설명 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라..

Spanning Tree란? 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree = 신장 트리 = 스패닝 트리 Spanning Tree는 그래프의 최소 연결 부분 그래프 이다. 최소 연결 = 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리 Spanning Tree의 특징 DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 특수한 형태이므로 ..

programmers.co.kr/learn/courses/30/lessons/62050# 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 문제 설명 N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다. 이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩..

programmers.co.kr/learn/courses/30/lessons/62049# 코딩테스트 연습 - 종이접기 직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다. 먼저 오른쪽 절반을 왼쪽으로 접습니다. 다시 오른쪽 절반을 왼쪽�� programmers.co.kr 문제 설명 직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 아래 그림과 같이 종이에 접은 흔적이 생기게 됩니다. 위 그림에서 ∨ ..

programmers.co.kr/learn/courses/30/lessons/12899# 코딩테스트 연습 - 124 나라의 숫자 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. programmers.co.kr 문제 설명 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. RULE 1. 124 나라에는 자연수만 존재합니다. 2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 접근 방법 저는 DP로 접..

다음 중 디지털 핑거프린팅 기술에 대한 설명으로 옮지 않은 것은? 3 1. 디지털 핑거프린팅 기술은 콘텐츠 내에 소유자 정보와 구매자 정보를 함께 포함하는 핑거프린트 경보를 사입하여 후에 불법으로 배포된 콘텐츠로부터 배포자가 누구인지를 역추적 할 수 있도록 해 주는 기술이다. 2. 핑거프린팅된 콘텐츠는 서로 다른 구매자 정보를 삽입하기 때문에 구매자에 따라 콘텐츠가 조금씩 다르다. 3. 공모공격 (collusion attack)이란 여러 개의 콘텐츠를 서로 비교하여 워터마킹된 정보를 제거하거나 혹은 유추하여 다른 워터마크 정보를 삽입할 수 있는 것을 의미하는 데, 이처럼 워터마킹은 공모공격에 취약하지만 디지털 핑거프린팅 기술은 이 공격에 매우 안전하다. 4. 디지털 핑거프린팅 기술은 워터마킹 기술과 같이..

리눅스를 설치하면 상당히 많은 디렉토리가 자동으로 생성됩니다. 이러한 디렉토리는 대부분 유닉스와 유사합니다. 파일 시스템의 구조는 유닉스의 종류(AT&T 계열과 BSD계열)에 따라 약간 차이가 있으며, 리눅스는 주로 AT&T를 중심으로 BSD가 섞인 형태입니다. 리눅스 연합에서는 이러한 배포판의 파일시스템 차이를 표준화하기 위해 FSSTND(File System Standard) 표준안을 마련해 놓고 있습니다.아래는 리눅스의 파일시스템 구조를 나타낸 것입니다. 파일과 디렉토리는 카테고리별로 조직화되어 있습니다. 위 그림에서 가장 분명하게 알 수 있는 카테고리는 고정(static)과 유동(dynamic)적인 파일들입니다. 또한 다른 카테고리로는 실행가능 여부, 환경설정, 데이터 파일들 등이 있습니다. 시스..

RAID Redundant Array Inexpensive Disk 혹은 Redundant Array Independent Disk 의 약자 처음 개념이 등장할 때는 여러개의 저렴한 디스크를 하나로 모아 고성능의 디스크처럼 사용하자는 생각에서 출발. 현재는 꼭 저렴한 디스크 라기 보다는 여분의 독립적인 디스크들을 하나로 모아 고성능 혹은 고가용성을 위한 개념이다. RAID는 구현 방법에 따라 여러개의 RAID LEVEL 로 표현된다. 단일 디스크 I/O 아래 그림은 단일디스크에서 I/O가 발생하는 상황이다. 모든 데이터는 조각(block 혹은 cluster로 표현됨)으로 나뉘어 디스크에 쓰여지기 때문에 아래와 같은 그림이 된다. 1번 조각이 디스크에 쓰여지고 있는 동안 나머지 조각들은 대기를 하게 되고,..