운영체제는 프로그램들 간의 올바른 실행을 돕고, 다양한 하드웨어 자원을 프로그램에 배분하는 프로그램이다.OS 종류에 관계 없이 운영체제가 제공하는 핵심적인 기능은 비슷하다.i) 프로세스 및 스레드 관리(동기화와 교착 상태)ii) 자원 할당 및 관리(CPU 스케줄링, 가상 메모리, 파일 시스템) 시스템 콜과 이중 모드운영체제도 일종의 프로그램이기 때문에 반드시 메모리에 적재되어야 한다.이 때 메모리 내의 커널 영역이라는 공간에 따로 적재되어 실행된다.운영체제가 적재되는 커널 영역 외에 응용 프로그램이 적재되는 공간은 사용자 영역이다.운영체제의 기능을 제공받기 위해 커널 영역에 적재된 운영체제 코드를 실행해야 한다.일반적으로 웹브라우저나 게임 같은 응용 프로그램은 CPU, 메모리와 같은 자원에 직접 접근하거..

최대 힙을 구현해보자힙은 이진트리로 구현하는 우선순위 큐 이다. (이진트리는 배열로)삽입 O(lgN), 삭제 O(lgN) 힙의 삽입힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입한다.새로운 노드를 부모 노드들과 교환한다.static void add(int x){ tree[++size] = x; int idx=size; while(idx >1){ if(tree[idx] 힙의 삭제최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다. (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것)삭제된 루트 노드에는 힙의 마지막 노드를 가져옴힙을 재구성static int remove(){ if(size == 0) return 0; int top = tree[1]..

이분 탐색에서 언제나 헷갈리는 경계값 lower_bound / upper_boundlower_bound(k): k 이상의 수가 처음 등장하는 위치upper_bound(k) : k 초과의 수가 처음 등장하는 위치 lower bound를 구하는 함수를 만들어보자 mid 위치의 값이 K와 같더라도, 왼쪽으로 범위를 줄인다.더 앞쪽에 K 이상인 값이 존재할 수 있으므로K 이상(≥ K)이 처음 등장하는 위치를 찾는 것이 목적def lower_bound(N, arr, K): answer = N # 못 찾으면 N (arr 끝 다음 위치) l = 0 r = N - 1 while l https://school.programmers.co.kr/learn/courses/30/lessons/..

작업들 사이에 선후관계가 존재할 때,그 선후관계를 유지하면서 전체 작업의 수행 순서를 그래프를 이용해 정렬하는 알고리즘이다.입력값 1 4는 1번 작업을 먼저 수행한 뒤 4번 작업을 수행해야 한다는 의미방향 그래프로 1→4가 된다5→4도 마찬가지 방향 그래프로 표현 가능즉, 입력으로 주어진 작업 순서 정보들을 이용해 방향 그래프를 구성한다.예를 들어 4번 작업은 여러 작업으로부터 영향을 받는 노드이며, 연결된 간선이 총 3개이다. (차수는 3) 노드로 들어오는 간선의 개수를 진입 차수라고 하며,토폴로지 정렬에서는 진입 차수가 중요하고, 나가는 간선은 상대적으로 중요하지 않다.4번 노드의 진입 차수는 2이다. 4번 작업으로 들어오는 간선을 가진 작업들이 모두 먼저 끝나야만 4번 작업을 수행할 수 있다.따라서..

그래프에서 모든 정점에서 모든 정점 쌍 사이의 최단 거리(최소 비용)를 구하는 알고리즘다익스트라 알고리즘과 벨만-포드 알고리즘은 특정 한 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 거였다. 출발 정점, 도착 정점을 모두 고려해야 하므로 DP 테이블은 2차원으로 구성되어야 한다. 그리고 최단 거리 갱신을 위한 점화식이 필요하다.2차원 형태의 dis 배열 준비 dis[i][j]는 i번 노드에서 j번 노드로 이동하는 데 드는 최소 비용초기에는 dis 테이블을 인접 행렬 기준으로 초기화한다. 이는 중간에 어떤 노드도 거치지 않고 i에서 j로 바로 가는 경우의 비용을 의미한다. 예를 들어, dis[1][2]에는 1번 노드에서 2번 노드로 직접 이동할 때 드는 비용을 기록한다.마찬가지로 2- >4 는 1..

최소 비용으로 출발 정점에서 도착 정점으로 가는 방법을 찾는 것, 근데 간선에 음수가 존재한다.여기서는 출발 정점 1, 도착 정점 5먼저 간선을 1번만 사용해서 갈 수 있는 경로가 있다고 가정하고 계산해 보고,그다음엔 간선을 2번 사용해서 갈 수 있다고 가정하고 또 계산해 본다.만약 간선을 2번 사용해서 가는 경로가 더 좋다면(dist가 더 작다면) 그 값으로 갱신한다.이런 식으로 반복.그럼 이 과정을 몇 번까지 반복하느냐?정점이 5개라면, 최단 경로에서 사용할 수 있는 간선의 최대 개수는 4개(V-1)이다.예를 들면 1→2→3→4→5처럼 모든 정점을 한 번씩 거쳐 가는 경우가 간선을 가장 많이 사용하는 경우다. 음의 사이클이 존재면 안된다는 전제 조건이 있다.만약 음의 사이클이 없는한, 노드가 5개일..

가중치가 있는 방향 그래프에서, 한 정점으로부터 다른 정점까지의 최단 거리를 구하는 알고리즘먼저 dist를 무한대로 초기화dist[i]는 1번 정점에서 i번 정점까지의 최소 비용을 저장한다.1번 정점에서 출발하므로 dist[1]은 0으로 초기화한다. 1번 정점에서 2번 또는 3번으로 갈 수 있다.1에서 2로 가는 간선의 가중치가 12이므로, 0에 12를 더한다.기존 값보다 작으면 갱신해준다. 처음에는 무한대니까 갱신된다.1에서 3으로 갈때는 간선이 4니까 0에 4를 더해 dist[3]을 4로 갱신한다. 그렇게 해서 다 바꿨다 하면 다시 최소값을 찾는다. (이때 체크한 것은 제외)이번에는 3이 체크되면서 최소값이 된다.1번에서 3번으로 가는 비용은 4라는 것이다. ★ 이 최소값 4는 앞으로 다른 경로에 의..

지원 계기본 프로그램은 6개월 동안 해외 인턴십을 하면서 학점을 얻을 수 있는 프로그램이다. 이전부터 해외 취업이라는 꿈을 가지고 있었다. 많은 선진 기술들이 해외에서 시작되고 우리나라로 들어온다고 생각했기 때문이다. 그 최전선에서 몇년 경험하면 많이 배울 수 있을 거라고 생각한다. (기존에 최종 합격했던 분들을 보니, 6개월 이후에도 연장이 가능한 것 같다.) 결론적으로 탈락했지만, 열심히 준비했었기에 기록으로 남기고자 한다.회사 선정, 서류 준비기수마다 차이는 있는 것 같지만, 이번 기수에서는 총 5곳의 회사에 지원할 수 있었다.지원 가능한 회사들은 다양하다. Upstage하고 프로그래머스(grepp)같은 회사도 있었다. 주로 웹 기술과 AI 기술등을 요구하는 거 같다. 나는 웹 백엔드와 데이터..

대표 예제풀이 방법이 2가지 있다. 9개의 도시가 모두 연결되어야하는데 최소 비용으로 연결해야 한다. 그래프 → 최소비용의 트리로 만들어야한다.트리는 n개의 정점이 있으면 간선은 n-1개만 있으면 된다. Kruskal MST1. 우선 들어오는 간선들의 가중치를 기준으로 오름차순으로 나열한다. 2. 밑에서부터 선택한다. 이 때 무조건 밑에서부터 선택하는 것은 아니고만약에 간선을 선택했는데 회로가 되면 간선을 선택하면 안된다.ex) 2 3 10이 들어 왔을 때 2번과 3번이 이미 연결되어 있는지 find함수로 확인한다.이 때 2번과 3번의 집합이 서로 다른 집합이면 연결한다.8 9 15 까지 했을 때의 모습 3. 만약 같은 집합이 나오면2 8 17이 왔을 때find(2)하고 find(8)하면 같은 집합으로 ..

기본 예제서로 친구이면 하나의 집합으로 묶을 수 있다.만약 1번과 2번이 친구라면 A = {1, 2}만약 2번과 3번이 친구라면 B = {2, 3}이 때 집합 A 와 집합 B에 공통된 원소가 있으면 두 집합을 한 집합으로 본다.즉 공통원소가 있으면 묶어버린다. Disjoint Set은 공통원소가 없는 서로소 집합을 뜻한다.Disjoint Set은 내부적으로 트리 구조로 표현한다.각 집합은 하나의 트리트리의 루트가 집합의 대표같은 루트를 가지면 같은 집합친구일 때마다 트리에 연결하고 그렇게 연결된 노드들은 한 집합이다위 입력 예제에서는 다음과 같이 트리가 2개 생성 코드로 구현1. 먼저 초기화를 해준다.for(int i=1; iunf은 1차원 배열로 트리를 표현한 것이다. 각 idx은 학생을 뜻하고 unf..