1. Spanning Tree란? : 그래프 내의 모든 정점을 포함하는 트리를 뜻한다. N개의 정점을 가지는 그래프의 최소 간선의 수는 N - 1개이고, N - 1개의 간선으로 연결되어 있으면 필연적으로 트리 형태를 갖게 되고 이것이 바로 Spanning Tree가 된다. 2. Spanning Tree의 특징 - DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다.(탐색 도중에 사용된 간선만 모으면 만들 수 있다.) - 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. - Spanning Tree는 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다. 3. MST : Minimum Spanning Tree의 약자로 간선의 가중치를 고려하여 최소 비용의 Span..

1. OAuth 1) OAuth의 흐름 예시 1) 군부대 가족이 김 일병을 면회 온 상황 군부대는 기본적으로 보안을 매우 중요시하고, 특별한 목적 없이는 들어갈 수 없다. 또한 들어간다 하더라도 신분에 따라 머무를 수 있는 시간과 공간이 제약된다. A. 김 일병의 가족이 면회를 온다. B. 김 일병의 가족은 위병소(출입을 통제하는 곳)에 도착하면, 어떤 목적으로 부대에 방문하려고 하는지, 방문자는 누구인지를 명확하게 밝혀야 한다. C. 위병소에서는 김 일병에게 가족이 면회 왔다는 소식을 알리고, 실제 가족이 맞는지를 체크한다. 실제 가족이 맞다면 김 일병은 위병소에 가족이 맞다고 전달한다. D. 위병소에서는 김 일병의 가족에게 면회가 허용된 장소로 안내하고, 그 장소에서만 머무를 수 있는 임시 출입증을 ..

접근법 - 그리디 알고리즘 위주로 연습을 하려다 쉬운 문제로 먼저 그리디 알고리즘의 감을 찾기 위해서 풀어보았다. - 간단하게 로프를 이용하여 최대로 들 수 있는 중량을 구하는 문제로, rope가 [15, 1]이라면 로프를 1개만 사용한다고 가정하면 15의 무게를 들 수 있지만, 로프를 다 사용하면 2번째 로프때문에 2밖에 들 수 없게 된다. - 이러한 점을 고려하여 높은 무게의 로프를 순서대로 정렬하여 (i + 1) * rope[i]가 가장 클 때의 값을 출력하도록 했다. 이때의 i는 인덱스이므로 0부터 시작하기 때문에 + 1을 하고 계산을 했다. 풀이 N = int(input()) rope = [] for _ in range(N) : rope.append(int(input())) result = 0 ..

파일 시스템 파일: 의미 있는 정보를 담는 논리적인 단위, 레코드 혹은 블록 단위로 보조 기억장치에 저장 � 파일 시스템 등장 배경 파일은 정보를 저장할 수 있는 기억 장소 공간이 디스크에 할당되어 있으며 디스크에 존재하는 다른 파일들과 구별할 수 있는 고유의 이름이 존재한다. 디스크에 저장된 파일은 프로세스가 수행을 완료하고 파괴된 후에라도 여전히 남아있게 된다. 이렇게 저장되는 데이터가 점점 많아지면서 그 데이터를 관리하지 않으면 파일을 읽고 쓰는데 많은 자원을 사용하게 되고, 다른 작업에 부하가 걸리게 된다. 그래서 파일 시스템이 효율적으로 파일을 관리할 필요가 생겼다. � 파일 시스템의 종류 1. FAT(File Allocation Table) : 파일을 할당한 정보를 테이블로 표현한 것이다. 구..

접근법 - 이분 탐색에 대해서 개념을 확실히 짚고 넘어가고 싶어 이 문제를 골랐다. 하지만 처음에 직관적으로 본 방법은 이분 탐색은 아니었다. - 첫 번째로 푼 방법은, 그냥 N_list와 M_list에 각각 입력을 받아 넣어주고, M_list를 for문을 돌리면서 M_list의 원소가 N_list에 있는지를 in을 통해서 검사하는 방법이었다. - 당연하게도 M_list의 크기(for i in M_list) x N_list의 크기(i in N_list)로 시간 복잡도가 커져서 시간 초과가 발생하였다. - 그래서 두 번째로 푼 방법은, 배열의 값을 미리 계산하고 인덱스를 통해서 결과값에 접근하는 방식이다. l이라는 배열에 [False] * 20000001(총 가능한 숫자의 가짓수)를 넣어준다. N_list..

메모리 : 운영체제에서 메모리 관리란 컴퓨터의 메인 메모리 관리를 담당하는 기능이다. 이 역할을 담당하는 장치가 MMU이다. MMU란 CPU 코어 안에 탑재되어 가상 주소를 실제 메모리 주소로 변환해주는 장치이다. 가상 주소(논리 주소) - 프로세스마다 독립적으로 가지는 주소 공간 - 각 프로세스마다 0번지부터 시작 - CPU가 보는 주소는 logical address 물리 주소 - 메모리에 실제 올라가는 위치 MMU 동작 원리 1) CPU가 프로세스 P1의 논리 주소 346을 요청 2) P1은 물리 주소 14000 – 17000에 올라가 있음 3) P1이 자신의 메모리 범위(3000)를 벗어나는 주소를 요청할 경우를 막기 위해 limit register의 값과 비교를 한다. 3-1) limit regi..