개발노트 개발노트

1. Operating System이란 컴퓨터가 잘 동작하도록 도와주는 프로그램이다. OS는 프로세스에게 H/W 자원을 '분배'하고, 프로세스들 사이의 '충돌'을 관리한다. 이를 위해, 프로세스들은 반드시 OS가 가진 '규칙'을 지켜야한다. 예를 들어, 프로세스가 System Call의 파라미터 형식을 지키면 해당 기능을 보다 손 쉽게 사용할 수 있다. 비유를 들어 설명해보자. 국가(OS)는 국민들에게(Process) 도로, 항공, 군대, 치안 등을(Resource) 제공함으로 국민들은 편리하게 그리고 충돌 없이 생활 할 수 있다. 하지만 국민들은 반드시 국가가 가진 법(규칙)을 준수해야한다. 2. Operating System이 하는 일 Resource Scheduling Process 관리 Memor..

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816..

- 이 문제의 경우 1~9999까지 p가 최대 5이기 때문에 아래의 그림과 같이 코드를 실행 할 경우 최대 값은 236196이다. 따라서 우리는 236196만큼의 배열 크기를 잡고 해당 인덱스에 접근 유무를 체크 해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include using namespace std; int check[236197]; // Values ​​mean length and 0 means no visit yetint length = 1; // The number that will remain in the sequence except for the repeated partint a[23619..

123456789101112131415161718192021222324252627282930313233343536373839#include #include using namespace std; int a[1001];bool check[1001]; void dfs(int x) { check[x] = true; int next = a[x]; if (check[next] == false) { dfs(next); }} int main() { int count, node, result; scanf("%d", &count); for (int i = 0; i

Bipartite Graph그래프를 아래의 그래프와 같이 나눌 수 있으면 이분 그래프라고 한다.즉, A에 포함되어 있는 정점끼리 연결된 간선이 없고 B에 포함되어 있는 정점끼리 연결된 간선이 없다.따라서 간선의 양 끝점이 다른지 체크 하면 된다. - 먼저 간선의 양 끝점의 위치를 check 배열에 표시를 하고, check 배열을 통해 양 끝점의 위치가 다른지를 확인한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include #include using namespace std; vector value[20001]..

Connected Component아래의 그림과 같이 나누어진 각각의 그래프를 연결 요소라고 한다. 아래 그래프는 총 2개의 연결 요소로 이루어져 있다. 연결 요소를 구하는 것은 dfS나 BFS 탐색을 이용해서 구할 수 있다. 시작점을 for문으로 이동하는 동시에 탐색 진행. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include #include using namespace std; vector a[1001];bool check[1001]; void dfs(int x) { check[x] = true; for (int i = 0; i

구현1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include #include #includeusing namespace std; vector a[1001];bool check[1001]; void dfs(int x) { check[x] = true; printf("%d ", x); for (int i = 0; i

목적모든 정점을 1번씩 모두 방문하자.탐색 방법Depth First Search(DFS), Breadth First Search(BFS)다음 정점을 찾는 것이 포인트Depth First Search(DFS)깊이 우선 탐색 : 최대한 깊숙히 많이하자.스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 갈 수 없으면 이전 정점으로 돌아간다. 구현1. 인접 행렬을 이용한 구현- 시간 복잡도 : 함수 길이 * 재귀 함수 파라미터 값 = O(V^2)이다. 없는 간선도 방문 하므로 시간 복잡도가 커진다.- 재귀 함수는 스택을 이미 구현 되어 있으므로 편리하다.- 해당 인덱스 방문체크 + 다음 정점을 찾는 동작 2가지로 구성한다. 123456789101112void dfs(int x) { check[x] = true..