분류 전체보기 (386) 썸네일형 리스트형 [boj] 백준 13904 과제 (c++) - 그리디 [문제] https://www.acmicpc.net/problem/13904 [풀이] 1. 점수의 최댓값을 얻기위해서는 점수가 높은 과제 순으로 처리해야 한다. 2. 하지만 점수가 높은 과제에 대해서도 바로 수행하는 것이 아니라, 최대한 마감일까지 미뤄서 수행해야 한다. 4 60 2 50 4 40 3 30 1 20 4 10 6 5 예제로 주어진 입력을 점수가 높은 순으로 정렬하면 위와 같다. 과제는 최대한 마감일까지 미뤄서 수행해야 하기 때문에 마감일부터 일수를 감소시켜가며 과제를 수행할 수 있는지 확인한다. 예를 들어, 60인 과제는 4일에 수행가능하므로 score[4] = 60, 50인 과제는 2일에 수행가능하므로 socre[2]= 50이다. 그런데 40인 과제를 보면, 이미 4일에 60인 과제를 수.. [boj] 백준 1774 우주신과의 교감 (c++) - MST(크루스칼) [문제] https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net [풀이] 별자리 만들기 문제와 같은 최소 신장 트리 유형이다. 마찬가지로 크루스칼 알고리즘을 이용해서 풀이하였고, 이미 연결된 통로들에 대해 미리 입력받아 처리한다. [코드] #include #include #include #include #include #include #include #define INF 987654321 using namespace std;.. [boj] 백준 2234 성곽 (c++) - BFS, 비트마스킹, 브루트포스 [문제] https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net [풀이] 먼저 벽의 위치를 1, 2, 4, 8 로 나타내기 때문에 비트마스킹을 이용할 수 있다. 성에 있는 방의 개수는 BFS의 호출 횟수로, 가장 넓은 방의 넓이 역시 BFS에서 면적을 증가시켜서 각 방의 넓이를 구한 후 비교하여 구할 수있다. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 넓이는 브루트포스 완전 탐색을 통해 얻을 수 있다. 이때 벽이 있는지 판단하기 위해 비.. [boj] 백준 17825 주사위 윷놀이 (c++) - DFS, 시뮬레이션 [문제] https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net [풀이] 1. 윷놀이 판을 위와 같이 새롭게 세팅해준다. 윷놀이 판에서 이동 가능한 다음 4가지 경로에 대해서 말이 이동할 수 있도록 map[] 배열에 이동 칸의 인덱스를 저장해준다. turn[] 배열에는 5, 10, 15의 파란색 칸에 대해서 방향 전환이 이뤄질 수 있도록 전환 후 이동 칸 인덱스를 저장한다. score[] 배열에는 각 칸의 점수를 저장한다. 2. dfs를 통해 10번의 주사위를 다 던졌을 경우의 최종합 크기를 비교한다. 이 때, 도착 위치가 아닌데 이동한 위치에 다른 말이 있을 경우 그 말을 고.. [운영체제] 5. CPU Scheduling (2) 더보기 kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다. 1. Multilevel Queue Ready queue를 여러 개로 분할 foreground(interactive) background(batch - no human interaction) 각 큐는 독립적인 스케줄링 알고리즘을 가짐 foreground - RR background - FCFS 큐에 대한 스케줄링이 필요 Fixed priority scheduling serve all from foreground then from background possibility of starvation Time slice 각 큐에 CPU time을 적절한 비율로 할당 eg) 80% to foreground in RR, 20% to back.. [운영체제] 5. CPU Scheduling (1) 더보기 kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다. 1. 프로세스 특성 분류 I/O-bound process cpu를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job Interactive job -> 적절한 response 제공이 필요 many short CPU bursts CPU-bound process 계산 위주의 job - 중간에 I/O가 거의 끼어들지 않음 few very long CPU bursts 2. CPU Scheduler & Dispatcher CPU Scheduler : Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다. (하드웨어가 아닌 운영체제 안 특정 코드를 의미함) Dispatcher : CPU의 제어권을 CPU Schedu.. [boj] 백준 14442 벽 부수고 이동하기 2 (c++) - BFS [문제] https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net [풀이] 벽 부수고 이동하기 1 문제와 다른 점은 벽을 k번 부수고 올 수 있다는 것 하나이다. 따라서 기존 벽을 부수고 왔는지, 아닌지 여부만 체크했던 visited[] 배열을 벽을 몇 번 부수고 왔는지를 체크하도록 바꿔준다. 역시 구분해줘야 하는 경우는 다음 2가지이다. 1) 벽이 있고, 아직 벽을 k번 부수지 않았다면 벽을 부수고 이동할 수 있다... [boj] 백준 20057 마법사 상어와 토네이도 (c++) - 시뮬레이션 [문제] https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net [풀이] 토네이도의 이동 방향성을 파악하는 것이 중요하다. 1. 좌표 중간 지점부터 시작하여 서->남->동->북 으로 방향을 계속 바꾼다. 2. 이동 칸 수가 1->1->2->2->3->3->4->4-> ... 으로 같은 카운트만큼 2번 이동 후 한 칸 씩 증가한다. 이때 이동 방향은 이동 칸 수 만큼 이동하면 바뀐다. /2번씩 이동한 후 move_cnt .. 이전 1 ··· 19 20 21 22 23 24 25 ··· 49 다음 목록 더보기
