이중 연결 성분(Biconnect Component)란? 이중 연결 성분이란, 무방향 그래프의 연결 성분에서 임의의 두 점 사이에 적어도 두 개의 단순 경로가 존재하는 연결 성분을 뜻한다. 이때, 연결 성분이란 그래프에서 서로 연결되어 있는 정점들을 말한다. 예를 들어, [1, 2, 3, 4, 5], [6, 7], [8, 9, 10]는 3개의 연결 성분으로 구성되었다고 볼 수 있다. 또한 단순 경로란, 경로 상의 정점이 모두 다른 경로를 말한다. 즉, 이중 연결 성분이란, 무방향 그래프의 연결되어 있는 정점 리스트인데, 이 리스트의 임의의 두 점 간의 경로 상에 있어서 정점이 중복되지 않는 경로가 두 개이상 존재하다는 것을 의미한다. 아래 예시와 함께 그 의미를 한 번 더 살펴보자. 위 그래프는 지금까지..
분할 정복 알고리즘은 반으로 나누는 것이 핵심이었다. 정확히는 분할할 수 없을 때까지 분할하여 간단한 문제부터 접근하였다. 굉장히 자주 사용하며, 좋은 알고리즘이다. 하지만, 분할하며 생기는 부분 문제들이 중복되어도 다시 사용하지 않는다. 이미 구한 문제를 또 푸는 것은 지루하고 시간이 드는 일이다. 유형마다 다르겠지만, 분할정복도 마찬가지일 것이다. 따라서 중복된 문제를 굳이 다시 풀지 않는 테크닉이 필요하다. 그리고 그 방법이 바로 "DP 알고리즘", Dynamic Programming 인 것이다. DP 알고리즘은 미리 최소 부분 문제들의 해를 구한다. 이는 논리적으로 생각했을 때 매우 당연하다고 여겨지는 것들이다. 또한 이 해를 이용하여 최소 부분 문제보다 더 큰 부분 문제를 풀어야 한다. 즉, 부..
파일 시스템에서의 Data Blcok 파일에서는 Block이라고 하는 것을 저장단위로 사용한다.이 Block 하나의 크기는 4096바이트이다. 디스크에서 파일을 저장할 때, Block을 무작위로 저장하지는 않는다. 어떻게 배치하느냐에 따라 그 전략이 달라진다.우선, 지금은 잘 사용하지 않는 _Contiguous Allocation_에 대해 알아보자. Contiguous Allocation 이름을 보고 유추할 수 있듯이, _Contiguous Allocation_방식은 파일을 저장할 때 연속적으로 Block을 배치한다.이 방식을 사용하면 File Allocation Table을 사용하는데, 여기에 파일의 시작 Block과 Block의 길이를 저장한다. 물론 파일의 FCB에서도 파일의 시작 Block..
Process Context 컨텍스트란 프로그램의 실행 환경을 의미한다. 그리고 Process Context는 컴퓨터가 실행되는 데 필요한 구성 요소들의 집합을 말한다. 컨텍스트에는 두 가지로 나뉘는데 하나는 User Context, 다른 하나는 System Context이다. User Context 코드 : 유저 프로그램 코드 데이터 : 프로세스의 전역 변수 User Stack : LIFO 자료구조 지역 변수, 함수의 파라미터, 리턴 정보 등을 저장하기 위함이다. System Context 운영체제가 만든 것이다. Kernel Stack(System Stack) 커널 코드 내에 있는 함수 호출을 위한 인자, 지역 변수를 저장한다. 커널 영역에 존재 Process Control Block(PCB) 프로세..
* 공부를 하며 정리한 글입니다. 수정할 점이 있다면 댓글 남겨주세요. 선택(Selection) 문제 주어진 수들 중 k 번째로 작은 수를 찾아야 하는 문제는 꽤나 자주 등장한다. 실제로 이러한 문제를 해결하는 알고리즘도 간단한 것이 많다. 예를 들어 최소 숫자를 k번 찾는 방법, 숫자를 정렬하고 k번째 숫자를 찾는 방법 등이 있다. 하지만, 앞서 말한 알고리즘의 시간 복잡도를 고려해보자. 각각 최악의 경우 O(kn)과 O(nlogn)이 소요된다. 그렇다면 이보다 더 효율적인 시간으로 k 번째 작은 수를 찾을 수 있을까? 여기에 있어 우리는 "Selection" 알고리즘을 사용할 수 있다. 미리 말하자면 선택(Selection) 알고리즘은 이진 탐색 알고리즘과 매우 유사하다. 이진 탐색은 원하는 수를 찾..
