분류 전체보기

[백준 2213] 트리의 독립집합 C++

2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 트리 DP 1. 문제 해결 아이디어 [백준 1949] 우수 마을 C++ 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, hyeo-noo.tistory.com 위 문제와 표현하는 말만 다르지 결국 똑같이 서로 인접하지 않는 정점들의 가중치의 최댓값을 찾는 문제이다. 하지만..

[백준 2458] 키 순서 C++

2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 플로이드-와샬 1. 문제 해결 아이디어 자신보다 키가 큰 게 확실한 사람, 키가 작은 게 확실한 사람들의 수를 구하면 된다. 주어진 방향그래프에서 자신이 도달할 수 있는 정점들이 모두 자신보다 키가 큰 학생임을 알 수 있다. 자신보다 키가 작은 학생들도 알아야 하므로 입력이 주어질 때 역방향 그래프도 같이 저장한다. 역방향 그래프에서 자신이 도달할 수 있는 정점들이 모두 자신보다 키가 작은 학생임을 알 수 있다. 따라서 임의의 정점에서 다른 모든 정점으로 갈 수 ..

음주 운전 단속 (DRUNKEN)

algospot.com :: DRUNKEN Drunken Driving 문제 정보 문제 As the holiday season approaches, the number of incidents caused by Driving While Intoxicated (known as DWI) increases rapidly. To prevent this, the city of Seoul has proclaimed a war against drunken driving. Every day, www.algospot.com 플로이드-와샬 문제 설명 더보기 플로이드 알고리즘은 아무 정점도 경우하지 않는 최단 거리에서 시작해 경유할 수 있는 정점을 하나씩 추가해 가며 최단 거리를 갱신한다. 이 과정에서 경유하는 정점을 1번부..

[백준 15684] 사다리 조작 C++

15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 완전 탐색, 백트래킹 삼성 SW 기출 1. 문제 해결 아이디어 처음에 문제에 대한 감이 안 왔다. 백트래킹이라기엔 H가 너무 커 보였고 그래프라 하기엔 간선 정보를 어떻게 담아야 할지 생각이 안 났다. 그러다 완전 탐색 문제라는 말을 듣고 힘들게 접근을 시도할 수 있었다. 지금까지 만든 사다리에서 사다리 타기를 했을 때 각 line의 도착점이 시작 line의 번호와 같아야 true를 return 하는 함수를 만들었다. 그리고 사다리를 놓지 못하는 조건을 걸어주고..

[백준 17144] 미세먼지 안녕! C++

17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 [백준 17143] 낚시왕 C++ 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래 hyeo-noo.tistory.com 낚시왕 문제와 느낌이 비슷했다. 시뮬레이션 문제는 문제에 어떻게 구현해야 하는지 자세히 나와있어서 풀이라고 할 게 없다. ..

[백준 1613] 역사 C++

1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 플로이드-와샬 1. 문제 해결 아이디어 사건들의 전후 관계를 파악하는 문제라서 처음에 바로 위상 정렬로 풀기 시작했었다. 근데 위상 정렬을 해놓으니 관계도는 명확히 그려지지만 임의의 정점 2개를 선택했을 때 해당 정점들이 서로 어떤 관계에 있는지 알아보려면 매번 BFS가 필요해 보였다. 효율이 안 좋게 느껴졌고 위상 정렬은 아닌 것 같아 알고리즘 분류를 켜서 어떤 알고리즘을 써야 하는지 힌트를 받았다. 플로이드-와샬 알고리즘을 쓰는 문제였다. N이 400..

[OS] Scheduling #3

Scheduling [하루OS] Day-6 Scheduling 어제에 이어서 Scheduling을 좀 더 알아보자 지난번 정리 SJF는 turnaround time을 최적화하는데 유용한 방법이다. RR은 빈번한 context switching을 통해서 response time을 줄이는데 최적화된 방법이.. hyeo-noo.tistory.com Starvation 짧은 수행 시간을 가진 interactive job이 너무 많아진다면 우선순위가 낮은 queue에 배치된 작업은 작업(오래 걸리는 작업)은 수행할 수 없게 된다. Game the scheduler 만약 time slice의 99%를 I/O 작업이 가져가 버린다면 오래걸리는 job들은 오히려 CPU를 거의 사용하지 못하게 될 수도 있다. 프로그램의..

소방차 (FIRETRUCKS)

algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 www.algospot.com 다익스트라 문제 설명 더보기 각 소방서마다 불이나는 집까지의 최단거리를 구하고, 그 중에서 가장 가까운 소방서만 선택해서 전체 시간을 구한다면 시간초과가 날 것이다. Key point는 소방서가 시작점이기 때문에 가상의 정점(0번 정점)을 만들고, 0번 정점에서 소방서까지 가는 비용을 0으로 잡고 queue에 넣어주면 된다! -> 0번 정점에서 모든 소방서로 가중치가 0인 간선을 연결한다고 생각하자 우선순위 큐에서 항상 가장 적은 시간이 소요되..

[백준 17143] 낚시왕 C++

17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 1. 낚시왕은 0번 col에서 오른쪽으로 한 칸 이동 2. 낚시왕이 있는 열에서 땅과 제일 가까운(row값이 가장 작은 상어)를 잡는다 3. 상어이동 상어 - 방향, 크기, 속도 특정방향으로 이동하다가 벽을 만나면 방향을 바꿔서 뒤로 감 상어 객체 생성 모든 상어가 일단 이동하고 겹치게 된 상어가 있으면 크기가 가장 큰 애들만 살아남음 맵에는 상어가 2마리 이상 있다는걸 알 수 있는 장치가 필..

[OS] Scheduling #2

Scheduling 이어서 Scheduling을 좀 더 알아보자 지난번 정리 SJF는 turnaround time을 최적화하는데 유용한 방법이다. RR은 빈번한 context switching을 통해서 response time을 줄이는데 최적화된 방법이다. 사용하는 프로그램마다 제각기 다른 특성을 가지고 있다. 한 번에 끝내는게 효율이 좋거나, 여러 번 나눠서 끝내는 게 좋거나 등등 스케줄러가 프로그램의 특성을 파악하고 그에 따라 더 나은 결정을 할 수 있다면 얼마나 좋을까 MLFQ (Multi-Level Feedback Queue) MLFQ는 여러개의 구별된 queue로 구성되고 각각 다른 우선순위를 가진다. 규칙 1 : A의 우선순위 > B의 우선순위 , A를 실행한다. 규칙 2 : A의 우선순위 =..