본문 바로가기
반응형

전체 글

 (168)
[프로그래머스] 디스크 컨트롤러 디스크 컨트롤러 1. 이해하기 하드디스크는 한 번에 하나의 작업만 수행할 수 있다. 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리할때 평균을 구하는 문제. 2. 구현하기 우선순위 큐를 이용하여 처리 시간이 가장 짧은 것부터 처리하게 한다. 이때 큐를 이용하면 원하는 위치의 삭제가 힘드니 우선순위 큐의 결과를 벡터에 담는다. priority_queue pq; for(int i = 0; i < jobs.size(); i++) pq.push({-jobs[i][1],jobs[i][0]}); vector job; for(int i = 0; i < jobs.size(); i++) { job.push_back(pq.top()); pq.pop(); } 시간과 일의 시작시간을 비교하여 시작시간이..
[프로그래머스] 가장 먼 노드 가장 먼 노드 1. 이해하기 1번 노드에서 가장 먼 노드의 갯수를 구한다. 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미한다. bfs를 이용해서 구할 수 있다. 2. 구현하기 bfs를 이용하여 1번에서 각 노드까지의 거리를 구한다. 그 이전에 edge로 주어진 각 노드들의 연결관계를 인접리스트로 바꾼다. void bfs() { queue q; q.push(1); visited[1] = true; dist[1] = 0; while(!q.empty()) { int here = q.front(); q.pop(); for(int i = 0; i < adj[here].size(); i++) { int there = adj[here][i]; if(visited[there]..
[프로그래머스] 단어 변환 단어 변환 1. 이해하기 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾는 것이다. 한 번에 한 개의 알파벳만 바꿀 수 있다. words에 있는 단어로만 변환할 수 있다. dfs를 이용하여 찾을 수 있다. 2. 구현하기 dfs함수를 만든다. dfs(now,target,depth,visited,words): 현재와 target을 비교해서 같으면 최소 과정을 반환해준다. 현재까지 찾은 과정보다 더 많은 과정을 찾으려고 하는 경우에는 바로 끝나도록 해준다. 있는 단어들을 모두 살펴보면서 이미 지나온 경우는 패스할 수 있도록 visited를 이용한다. 또한 고른 단어와 현재 단어가 한글자만 다른지 확인하고 맞다면 dfs를 반복한다. void dfs(string now, string target..
[백준] 2098번 외판원 순회 2098번 외판원 순회 1. 이해하기 비트마스크와 DP를 이용하는 문제이다. 비트마스크를 이용하여 방문한 지점을 체크하고 DP를 이용하여 특정 지점까지의 최소거리를 갱신한다. 2. 구현하기 TSP(current,visited)일때 방문한 지점은 visited & (1
[백준] 1967번 트리의 지름 1967번 트리의 지름 1. 이해하기 트리의 지름은 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다. 가중치가 있는 간선들로 주어진다. 2. 구현하기 dfs를 이용해 루트로부터 제일 멀리 떨어진 노드 하나를 먼저 찾는다. 그 이후 이 노드로부터 가장 멀리 떨어진 노드를 찾고 그 때의 길이를 구한다. void dfs(int here, int cost) { visited[here] = true; if(ans < cost) { ans = cost; endPoint = here; } for(int i = 0; i < adj[here].size(); i++) { INF there = adj[here][i]; if(visited[there.next]) continue; dfs(there.next,c..
[백준] 17822번 원판 돌리기 17822번 원판 돌리기 1. 이해하기 원판의 회전은 독립적으로 이루어진다. 원판을 회전시킬 때는 수의 위치를 기준으로 한다. 원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi,di,ki이다. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다. 인접하면서 수가 같은 것을 모두 찾는다. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다. 원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구하는 문제. 시뮬레이션 문제. 2. 구현하..
[모의 SW 역량테스트] 5650. 핀볼 게임 [모의 SW 역량테스트] 핀볼 게임 1. 이해하기 게임판 위에서는 작은 핀볼 하나가 상, 하, 좌, 우 중 한 방향으로 움직인다. 핀볼은 블록이나 웜홀 또는 블랙홀을 만나지 않는 한 현재 방향을 유지하며 움직인다. 핀볼이 블록의 수평면이나 수직면을 만날 경우 방향을 바꿔 반대 방향으로 돌아오고, 경사면을 만날 경우에는 직각으로 진행 방향이 꺾이게 된다. 핀볼은 벽을 만날 경우에도 반대 방향으로 돌아온다. 웜홀에 빠지면 동일한 숫자를 가진 다른 반대편 웜홀로 빠져 나오게 되며 진행방향은 그대로 유지된다. 핀볼이 블랙홀을 만나면, 핀볼이 사라지게 되어 게임은 끝난다. 게임은 핀볼이 출발 위치로 돌아오거나, 블랙홀에 빠질 때 끝나게 된다. 점수는 벽이나 블록에 부딪힌 횟수가 된다. 게임에서 얻을 수 있는 점수..
[모의 SW 역량테스트] 5648. 원자 소멸 시뮬레이션 [모의 SW 역량테스트] 원자 소멸 시뮬레이션 1. 이해하기 원자들은 2차원 평면에서 이동하며 두 개 이상의 원자가 충돌할 경우 충돌한 원자들은 각자 보유한 에너지를 모두 방출하고 소멸된다. 원자는 각자 고유의 움직이는 방향을 가지고 있다. 모든 원자들의 이동속도는 동일하다. 즉, 1초에 1만큼의 거리를 이동한다. 원자들이 소멸되면서 방출하는 에너지의 총합을 구하는 문제. 시뮬레이션 문제. 2. 구현하기 원자들은 0.5초 후에도 만나면 충돌하여 에너지를 방출한다. 따라서 이동 구간을 2배로 늘려주면 된다. 원자들의 이동을 구현한다. 이때, 입력이 y,x로 주어지기 때문에 이동방향을 맞춰서 잘 구현해주어야 한다. bool out_of_bound(int x, int y) { return x < 0 or x ..

티스토리툴바