본문 바로가기

분류 전체보기

 (161)
[백준 4195] 친구 네트워크 분리 집합과 해시를 이용하는 자료구조 활용 문제다. 문제를 유심히 읽어보면 알 수 있듯이, 친구 집합이 계속해서 합쳐져야 하고 특정 아이디의 유저가 속한 친구 집합을 빠르게 조회할 수 있어야 한다. 따라서 분리 집합을 활용해 이를 효율적으로 처리할 수 있다. 다만 유저에 대한 정보를 문자열 형태의 아이디로 제공하고 있으므로, 이를 Union-Find 연산 내에서 매번 문자열 형태로 비교하면 효율성이 떨어진다. 나는 그래서 해시 맵을(C++ 내의 unordered_map을 사용했다) 활용해, 각 유저의 아이디에 대한 고유 정수 id값을 부여했다. 이렇게 하면 처음 유저 아이디를 입력받았을 때만, 한 번 id 값을 조회하고 그 이후부터는 정수 id로 빠르게 Union-Find 연산을 처리할 수 있다.  나머..
[백준 1949] 우수 마을 트리 DP 문제다. 처음 본다면 로직을 떠올리기 조금 힘들 수도 있다. 트리 DP 문제를 풀어본 경험이 있다면 쉽게 접근할 수 있는 문제.  각각의 마을이 일반 마을일 수도 있고, 우수 마을일 수도 있는데 문제에서는 조건을 통해 이를 제약하고 있다. 1. 우수 마을로 선정된 마을 주민 수의 총합을 최대로 해야 한다.2. 우수 마을끼리는 인접할 수 없다.3. 일반 마을은 최소한 하나의 우수 마을과 인접해야 한다.  따라서 dp 값을 계산할 때 어떤 마을이 일반 마을인 경우와 우수 마을인 경우로 나눈 다음에 트리 탐색 과정에서 이를 조건에 맞게 처리해 주어야 한다. 나처럼 dp[마을 번호][우수 마을 선정 여부(0: 선정x, 1: 선정)] = 해당 마을 번호를 루트로 하는 서브 트리의 최대 우수 마을 주민 ..
[백준 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를 표시하면서 지속적으로 맞춤법을 검사하며, 동시에 저장소의 데이터를 읽거나 쓰는 것도 가능하다.  프로세스는 저번 챕터에서 본 것처럼 생산 및 관리의 오버헤드가 크기 때문에, 오버헤드를 줄이고 보다 효율적으로 다수의 태스크를 처리하기 위해 등장한 개..

티스토리툴바