본문 바로가기

전체 글

 (159)
[백준 1507] 궁금한 민호 그래프 이론 문제다. 처음 문제를 가볍게 읽었을 때는 최소 스패닝 트리 문제인 줄 알았다. 하지만 문제를 꼼꼼하게 읽다 보니 개성 있는 문제라고 느꼈는데, 각 노드에서 목적 노드 별 최단 거리가 주어지고 최소 간선으로 그 그래프를 만들었을 때 간선의 비용 총합을 추측하는 문제였다.  먼저 시도했던 방법은, 최소 스패닝 트리를 만들듯이 간선들을 우선순위 큐에 넣고 비용이 작은 간선을 우선해서 그래프를 만들어 나가는 방법이었다. 이 방법으로 구현하다가 결국에는 다른 노드를 경유해서 만들어질 수 있는 최단 거리 문제 때문에 중간에 지워버렸다. 매 간선을 추가하려고 할 때마다 DFS가 필요할 테니까.  그다음으로 이용한 방법은, 플로이드-워셜 알고리즘을 이용한 방법이었다. 문제에서 주어지는 입력값은 결국 어떤 ..
[백준 1365] 꼬인 전깃줄 LIS 문제다. 문제를 잘 해석해 보면, 꼬임이 발생하지 않는 경우는 왼쪽 전봇대와 연결된 오른쪽 전봇대의 번호가 계속해서 증가하는 형태로 나타날 때임을 알 수 있다. 따라서 LIS의 길이를 구하고, 전봇대의 개수에서 그만큼을 빼준다면 잘라내야 하는 전선의 수가 될 것이다. LIS 자체를 출력할 필요도 없기 때문에, 역추적을 위한 추가 처리 등이 전혀 필요하지 않다. 이런 간단한 형태의 LIS 문제에 대한 설명은 이전에 풀었던 아래 문제를 참조하면 좋을 것 같다. 거의 같은 유형.https://winterry.tistory.com/102 [백준 12015] 가장 긴 증가하는 부분 수열 2아마 알고리즘을 따로 공부했거나, 학부 과정에서 컴퓨터 알고리즘 과목을 수강했다면 익숙할 LIS 문제이다. 대표적인 D..
[운영체제] 5. CPU 스케줄링 본 내용들은 전공수업으로 배운 내용들을 스스로 리마인드하기 위한 목적으로 작성되었으며, 누군가에게 지식을 전달하기 위한 목적으로 작성한 것이 아닙니다. 대부분의 내용은 제가 수강했던 전공수업 및 Operating System Concepts, 10th Edition에 근거하고 있습니다.   1. 개념- CPU 스케줄링은 멀티 프로그래밍과 함께 CPU 이용률을 극대화하기 위해 등장했다. 기본적으로 프로세스는 CPU burst와 I/O burst의 사이클로 동작하게 되며, CPU burst를 어떻게 배분하느냐가 주요한 고민거리이다.- 이런 CPU burst의 경우 short burst가 많은 부분을 차지 하고 있으며, longer burst는 그 비율이 훨씬 낮다. - 프로세스 상태를 running, rea..
[백준 1922] 네트워크 연결 최소 스패닝 트리 문제. 가장 심플한 형태의 MST 문제라서 포스팅을 작성하지 않으려다가, 그래도 MST를 처음 접하는 사람들에겐 연습하기 좋은 문제인 것 같아서 들고 왔다.  각각의 컴퓨터를 노드로 생각하고, 무방향 가중치 그래프의 부분 그래프로 모든 노드가 연결되도록 했을 때 그 간선 비용의 총합이 최소가 되어야 한다. 이런 유형의 문제는 대부분 MST 문제인 경우가 많다. MST는 Kruskal 알고리즘이나 Prim 알고리즘으로 해결하게 되는데 간단하게 차이를 정리하면 아래와 같다.  Kruskal 알고리즘- 모든 간선을 비용 기준으로 정렬하여, 사이클이 되지 않도록 간선을 하나씩 스패닝 트리에 추가하는 방법.- 사이클에 대한 판정은, 새로 추가하려는 간선의 두 노드가 스패닝 트리 내에서 이미 하나..
[백준 14428] 수열과 쿼리 16 최근에 프로그래머스 문제들을 몰아서 푸느라 백준에서는 매일 간단한 문제만 하나씩 풀었는데, 오랜만에 좋은 문제를 만났다. 문제를 읽으면 바로 느껴지겠지만 세그먼트 트리 문제다. 다른 부분은 일반적인 세그먼트 트리를 이용한 문제와 다를 바가 없지만, 주의해야 하는 부분은 쿼리의 결과로 최솟값이 위치한 인덱스를 출력해야 한다는 것이다. 따라서 세그먼트 트리에 값으로 최솟값만 저장할 게 아니라 최솟값이 위치한 인덱스를 함께 저장하는 방법으로 접근했다. 그리고 문제 조건에서 최솟값이 구간 내에 여러 개 있을 경우 가장 작은 인덱스를 출력하도록 되어있으므로, C++ 기준 pair를 이용하되 {최솟값, 인덱스} 순서로 배치해서 비교 연산을 수월하게 했다.  위 내용을 토대로 세그먼트 트리를 초기화, 업데이트, 쿼리..
[운영체제] 4. 스레드 본 내용들은 전공수업으로 배운 내용들을 스스로 리마인드하기 위한 목적으로 작성되었으며, 누군가에게 지식을 전달하기 위한 목적으로 작성한 것이 아닙니다. 대부분의 내용은 제가 수강했던 전공수업 및 Operating System Concepts, 10th Edition에 근거하고 있습니다. 1. 개요 현대의 대부분의 응용 프로그램들은 멀티 스레드 기반으로 동작한다. 응용 프로그램들이 보통 다수의 태스크를 동시에 처리해야 하기 때문인데, 당장 워드만 사용해도 UI를 표시하면서 지속적으로 맞춤법을 검사하며, 동시에 저장소의 데이터를 읽거나 쓰는 것도 가능하다.  프로세스는 저번 챕터에서 본 것처럼 생산 및 관리의 오버헤드가 크기 때문에, 오버헤드를 줄이고 보다 효율적으로 다수의 태스크를 처리하기 위해 등장한 개..
[운영체제] 3. 프로세스 본 내용들은 전공수업으로 배운 내용들을 스스로 리마인드하기 위한 목적으로 작성되었으며, 누군가에게 지식을 전달하기 위한 목적으로 작성한 것이 아닙니다. 대부분의 내용은 제가 수강했던 전공수업 및 Operating System Concepts, 10th Edition에 근거하고 있습니다.  1. 개념- 프로세스는 실행 중인 프로그램을 의미한다. 즉 온 메모리 상태인 것. 프로그램은 secondary storage 내에 있는 실행가능한 코드를 의미한다.- 물론 하나의 프로그램이 여러 개의 프로세스를 가질 수도 있다. 한 프로그램이 여러 번 실행되는 상황이라든지.- 이런 프로세스는 다음과 같은 구성요소로 이뤄진다.Text Section: 실제 프로그램의 코드가 저장된 부분, instruction set.Dat..
[백준 2243] 사탕상자 세그먼트 트리 문제다. 수정이 빈번하게 일어나는 구간 쿼리 문제는 대부분 세그먼트 트리로 해결할 수 있는 것 같다. 구간 값 update 함수는 일반적인 세그먼트 트리와 같고 query 함수를 조금 신경 쓸 필요가 있다. 문제에서 요구하는 것은 특정 구간 합 그 자체가 아니라, 꺼내야 하는 사탕의 맛 값이다. 따라서 왼쪽 자식 노드 값, 그러니까 현재 구간 중에서 앞쪽 절반 구간에 존재하는 사탕 수 합이 쿼리하는 값 이상이라면, 해당 구간에 대해 쿼리를 이어나가면 된다. 반대로 앞쪽 절반 구간에 존재하는 사탕 수가 불충분하다면, 당연히 오른쪽 자식을 이용해야 한다. 이때, 주의해야 할 것은 쿼리하는 값을 그대로 사용하면 안 된다는 것이다.  전체에서 b번째 맛을 꺼내야 하므로, 앞쪽 구간의 사탕 수만큼을..

티스토리툴바