나다김강니

1.2.1 프로세스와 스레드프로세스  컴퓨터에서 실행 중인 하나의 프로그램을 의미프로그램은 특정 작업을 수행하기 위한 명령어의 집합OS는 프로그램을 실행하면서 디스크에 저장된 데이터를 메모리로 로드한다.프로세스는 독립된 메모리 영역을 할당받고, 다른 프로세스의 메모리 영역에는 접근 불가능하다. 💡  프로세스의 메모리 영역 구조스택(stack)지역변수, 함수의 매개 변수, 반환되는 주소 값 등이 저장되는 영역영역 크기는 컴파일 때 결정된다.LIFO(후입선출) : 높은 주소 값에서 낮은 주소 값으로 메모리가 할당힙(heap)사용자에 의해 동적 메모리 할당이 일어나는 영역영역 크기는 런타임 때 결정된다.FIFO(선입선출) : 낮은 주소 값에서 높은 주소값으로 메모리가 할당데이터(data)전역 변수, 정적 변..

1.1.1 운영체제란?운영체제(OS)란 하드웨어 위에 설치되어 하드웨어 계층과 다른 소프트웨어 계층을 연결하는 소프트웨어 계층이다.컴퓨터 시스템의 자원을 관리하고, 사용자가 컴퓨터를 사용할 수 있는 환경을 제공사용자와 컴퓨터 간 인터페이스를 제공 -> 사용자가 컴퓨터를 편리하게 사용윈도우, 맥OS, 리눅스, 유닉스1.1.2 운영체제의 목적  1. 처리 능력      자원 관리를 통해 일정 시간 내에 시스템이 처리하는 일의 양을 향상시킴   2. 반환 시간      요청한 작업을 완료할 때까지 소요되는 시간을 단축시킴   3. 사용 가능도      시스템 자원을 얼마나 빨리 제공할 수 있는가 -> 사용자가 컴퓨터를 사용해야할 때 자원을 즉시 사용할 수 있어야함.   4. 신뢰도      시스템이 주어진 문..

위상 정렬위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.사이클이 없어야한다.시간복잡도는 O(V+E)항상 유일한 값으로 정렬되지 않는다.💡  위상 정렬의 원리 이해하기1. 진입 차수 배열을 만들어준다.    진입 차수는 자기 자신을 가리키는 에지의 개수이다.    예를 들어 첫번째 리스트를 보면 D[2]++, D[3]++ 계산을 할 수 있다. 2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택한 보드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입차수를 1씩 뺀다.0인 노드를 선택할 때 3을 먼저 선택할 수도 2를 먼저 선택할 수도 있다. 이러한 이유로 위상정렬은 유일한 값으로 정렬되지 않는 것이다.    2252 : 줄 세우기..

유니온 파인드(Union-Find)유니온 파인드는 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 잡합으로 묶는 union연산과 두 노드가 같은 집합에 속해있는지를 확인하는 find연산으로 구성되어있다. 💡  유니온 파인드의 핵심 이론 - union연산과 find연산1. 일반적으로 1차원 배열을 사용한다. 처음에는 노드가 연결되어있지 않으므로 각 노드가 대표노드가 된다. 2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union연산을 수행한다.union(1, 4)일때는 작은 값을 대표로 생각하고 4의 대표노드자리에 1을 넣는다.find(4)연산은 4번노드의 대표노드와 4를 비교해서 같지 않으면 대표노드에 해당하는 번호를 찾는다.find연산은 대표 노드 값도 찾지만, 그래프를 정돈하고..

그래프그래프는 노드와 에지로 구성된 집합이다.노드는 데이터를 표현하는 단위, 에지는 노드를 연결하는 선유니온 파인드 : 그래프의 사이클이 생성되는지 판별하는 알고리즘위상정렬 : 싸이클이 없고 방향이 있는 그래프. 노드를 정렬해주는 알고리즘(정렬결과가 꼭 1개 X,) -> 수강신청문제다익스트라 : 시작점(S)이 있고 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘(단, 음수간선은 안된다)벨만-포드 : 다익스트라와 같지만 음수간선도 가능하다는 차이점이 있다. 음수사이클이 있는지 판별하는 문제로 많이 나옴.플로이드-워셜 : 시작점이 없고 모든 노드에 대해 최단거리를 구한다. 하지만 시간 복잡도가 좋지않다.최소 신장 트리 : 모든 노드를 최소의 비용으로 연결하는 알고리즘. 사이클이 나올 수 없게끔 유니온 파..

소수 구하기소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수.1과 자기 자신 외에 약수가 존재하지 않는 수! 💡  소수 구하기의 핵심 이론 - 에라토스테네스의 체 원리구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.2부터 시작하고 현재 숫자가 지원지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.배열의 끝까지 2를 반복한 후 배열에서 남아있는 모든 수를 출력한다.☝🏻 에라토스테네스의 체 원리의 시간복잡도는 최적화의 정도에 따라 다르지만 일반적으로 O(Nlog(logN))이다! 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다!!  192..

그리디 알고리즘그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.* 항상 최적의 해를 보장하는 것은 아니기에 그리디 알고리즘이 문제에 적합한지 판단해야한다. 💡  그리디 알고리즘의 핵심 이론1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.  11047 : 동전 0문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의..

이진탐색(Binary Search)데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.시간복잡도  O(logN)💡  이진 탐색의 핵심 이론 1. 현재 데이터셋의 중앙값을 선택한다. 2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다. 3. 중앙값  4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.☝🏻 이진 탐색을 사용하면 N개의 데이터에서 데이터를 반씩 줄여가며 탐색하기 때문에 총 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.  1920 : 수 찾기문제N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라..

BFS 너비 우선 탐색너비 우선 탐색은 그래프 완전 탐색 기법 중 하나이다. -> DFS와 공통점시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘FIFO 탐색큐 자료구조 이용한다.목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.시간 복잡도 : O(V+E) V: 노드 수, E: 에지 수💡  BFS의 핵심 이론1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화한다.visit배열을 사용하고 인접리스트를 사용하는 것은 DFS와 같다. 하지만 BFS는 스택이 아닌 큐를 사용한다.  2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기큐에서 노드를 꺼내면서 해당 노드와 인접 노드를 큐에 삽입한다.   3. 큐 자료구조에 값이..

DFS 깊이 우선 탐색깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다.시작 노드에서 출발하여 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동해서 탐색을 수행한다.재귀 함수로 구현 -> 스택 오버플로를 유의해야한다.스택 자료구조 이용한다.(FILO)단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬 등의 문제를 풀 때 사용한다.DFS는 한 번 방문한 노드를 다시 방문하면 안된다. 그렇기 때문에 노드 방문을 체크할 배열이 필요하다.시간 복잡도 : O(V+E) V: 노드 수, E: 에지 수💡  DFS의 핵심 이론1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화한다.(여기서는 인접리스트) 2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기 3. 스택 ..