본문 바로가기

전체 글140

user thread, kernel thread mapping 우리가 일반적인 프로그래밍 언어로 여러 스레드를 생성하여 멀티 스레드 프로그래밍을 구현하려고 할 때, 언어 자체의 스레드 관련 라이브러리를 사용하여 스레드를 생성하곤 한다.이렇게 우리가 언어로 생성한 스레드를 user level thread(user thread)라 하는데, 이 스레드는 운영체제가 직접 관리하지 않고, 언어 라이브러리에 의해서 관리된다.그런데 이 라이브러리는 해당 프로세스 내부에서의 스레드만 관리하기 때문에, 하나의 운영체제 내에서 돌아가는 전체 프로세스(스레드)에 대한 정보를 알 수 없다.결국 라이브러리 내부에서는 내부 스레드들 간의 스케줄링을 통해 최대한 자원을 효율적으로 사용하려 하지만, 결국 각 유저 스레드는 언어 라이브러리에 의존하게 되는 것이고 모든 프로세스의 정보를 전부 가지.. 2024. 7. 7.
[백준] 19644 - 좀비 떼가 기관총 진지에도 오다니 https://www.acmicpc.net/problem/19644 19644번: 좀비 떼가 기관총 진지에도 오다니 킬로와 헥토는 좀비 떼로부터 탄약고를 사수하는 데에 성공했다. 포상 휴가나 조기 전역을 기대했으나 좀비 사태로 인해 계엄령이 선포되면서 오히려 전역이 연기되고 기관총 진지에 배치되었 www.acmicpc.net 진지 앞 쪽의 길이가 최대 300만이기 때문에 좀비를 한 칸씩 당겨가며 최적의 수를 고르는 것은 불가능하다(O(N^2)). 따라서 현재 좀비의 상태를 보고 기관총을 쓸 것인지, 지뢰를 쓸 것인지를 판단해야 한다. 만약 i 지점의 좀비를 사살할 때 이전의 어느 지점에서 지뢰를 쓰고, 어느 지점에서 기관총을 썼는지 알아야 한다. 그래서 다음과 같은 누적합 배열을 사용하였다. s[i] =.. 2023. 8. 16.
[백준] 15559 - 내 선물을 받아줘 https://www.acmicpc.net/problem/15559 15559번: 내 선물을 받아줘 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000) 둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다. 지도에 쓰여 있는대로 이동했을 www.acmicpc.net 우선 모든 경우의 수를 전부 탐색하는 경우를 생각해 보자. 예제 1번에서, (1, 1)에서 시작하면 가장자리의 모든 수를 방문하게 된다. (1, 2)에서 시작해도 가장자리의 모든 수를 방문하게 된다. (1, 3)에서 시작해도 가장자리의 모든 수를 방문하게 된다. .. 따라서, 어떤 점에서 시작해서 방문한 이력이 있는 곳을 방문했을 때 그 이후에는 방문하지.. 2023. 8. 15.
[백준] 2325 - 개코전쟁 https://www.acmicpc.net/problem/2325 2325번: 개코전쟁 “앙두레 강”이 개미와 코끼리 결혼식에서 기차를 아름답게 만드는 것을 실패했기 때문에 식장이 아수라장이 되고 결혼이 물거품이 되어버렸다. 급기야는 왕국 간에 분쟁으로 이어져 개미왕 www.acmicpc.net 이전에 비슷한 문제를 풀어봐서 쉽게 풀 수 있었던 문제이다. 간선의 개수가 최대 약 50만 개가 주어지므로, 모든 간선을 없애면서 다익스트라를 수행하는 것은 불가능하다. 하지만 모든 간선을 다 체크해 볼 필요가 있을까? 예제 1번에서 최단 거리는 1 -> 2 -> 4 -> 5이다. 여기서 1-3 또는 2-3 또는 2-5 간선을 없앴다고 해서 최단 거리가 변경이 될까? 그렇지 않을 것이다. 따라서 핵심은 최단 거리.. 2023. 8. 14.
[백준] 14864 - 줄서기 https://www.acmicpc.net/problem/14864 14864번: 줄서기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 학생 수 N (1 ≤ N ≤ 100,000)과 순서쌍의 수 M (0 ≤ M ≤ 1,000,000)이 공백으로 분리되어 주어진다. 일렬로 서 있는 학생들을 순서대로 학생1, 학 www.acmicpc.net 입력으로 주어지는 쌍들을 이용해서 하나의 그래프를 생성할 수 있다. 그래프가 생성되면 각 정점에 입력 간선, 출력 간선이 생기고 그에 따라 각 학생이 가져야 하는 번호를 유추할 수 있다. 각 학생이 가져야 하는 번호를 유추하는 방법은, 해당 학생보다 작은 번호를 가진 학생 수와 큰 번호를 가진 학생 수를 통해서 알 수 있다. 예제 1번의 4번 정점으로 예시를 들면.. 2023. 8. 14.
[백준] 2917 - 늑대 사냥꾼 https://www.acmicpc.net/problem/2917 N, M제한이 500이기 때문에, 지도의 모든 곳을 탐색하면서 동시에 가장 가까운 나무와의 거리를 구하는 것은 최대 500 ^ 4의 시간이 걸릴 것이다. 따라서 지도의 각 부분에서 어떻게 하면 가장 가까운 나무와의 거리를 빠르게 구할 수 있는지 생각해야 한다. 그렇다면 각 나무에서 빈 목초지까지 거리를 구하면 어떨까? 그런데 이 방법은 더 가까운 나무가 생길수록 빈 목초지의 내용이 계속 갱신될 것이다. 이 부분은 BFS를 통해서 해결해 보자. ..... .+..+ +.... ...+. 이런 입력이 있다. BFS를 이용하면 t = 1 일때 다음과 같다. .1..1 1+11+ +1.11 1.1+1 t = 2 일때 다음과 같다. 21221 1+.. 2023. 8. 8.
[백준] 3114 - 사과와 바나나 https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net 문제를 보고 prefix sum + dp이라는 것을 알아차리고 간단하게 해결하려 했지만 WA를 받았다. 먼저 처음 시도한 방법부터 알아보자. map[i][j] = 입력 asum[i][j] = j열의 i행 까지의 사과나무의 누적합(map[1][j] + map[2][j] + ... map[i][j]) bsum[i][j] = j열의 i행 까지의 바나나나무의 누적합(map[1][j] + map[2][j.. 2023. 8. 7.
[백준] 3117 - YouTube https://www.acmicpc.net/problem/3117 3117번: YouTube 첫째 줄에 N, K, M이 주어진다. (1 ≤ N,K ≤ 100,000) (1 ≤ M ≤ 1,000,000,000) N은 학생의 수, K는 동영상의 개수, M은 남은 수업 시간이다. 둘째 줄에는 1보다 크거나 같고, K보다 작거나 같은 수가 N개 www.acmicpc.net 많이 봐왔던 sparse matrix 문제이다. 희소 배열에 대한 개념이 없다면 여기를 참고해도 좋다. 이 문제의 입력으로 사이클이 생기는 그래프가 주어질 수 있다. 그래서 M의 범위가 10억이어도 상관이 없는 것이고, M의 범위가 10억 인 만큼 sparse matrix를 다음과 같이 정의할 것이다. p[i][j] = 정점 i의 2^j 번째.. 2023. 8. 2.
[백준] 21922 - 학부 연구생 민상 https://www.acmicpc.net/problem/21922 21922번: 학부 연구생 민상 첫 번째 줄에는 연구실의 크기가 세로 $N(1 \le N \le 2,000)$, 가로 $M(1 \le M \le 2,000)$ 순으로 주어진다. 두 번째 줄부터 $N + 1$ 줄까지 연구실 내부 구조 정보를 알려주는 값 $M$개가 주어진다. $1,2,3,4$ www.acmicpc.net 간단한 문제였지만, 생길 수 있는 반례를 좀 오래 생각한 문제였다. 처음에 ans[n][m]이라는 배열을 생성해 에어컨 바람이 오는 자리를 체크해 답을 내려했지만, ans[n][m]을 채우는 과정에서 만약 이미 채워진 공간에 진입했을 때, 어차피 왔던 공간이므로 탐색을 끝낸다. 다른 경우의 수가 있을 수 있으므로 계속 채워.. 2023. 8. 2.

티스토리툴바