본문 바로가기
반응형

알고리즘

 (136)
[모의 SW 역량테스트] 2105. 디저트 카페 [모의 SW 역량테스트] 디저트 카페 1. 이해하기 디저트 카페 투어는 어느 한 카페에서 출발하여 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다. 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다. 하나의 카페에서 디저트를 먹는 것도 안 된다. 왔던 길을 다시 돌아가는 것도 안 된다. 디저트를 가장 많이 먹을 수 있는 경로를 찾고, 그 때의 디저트 수를 구하는 문제. 완전 탐색 문제이다. 2. 구현하기 디저트 카페 투어는 대각선 방향으로 움직여야 한다. 사각형 모양을 그려야 하고, 출발한 카페로 돌아와야 하는 조건이 있다. 또한, 하나의 카페에서 디저트를 먹는 것이 안된다는 조건이 있으므로 디저트 카페 투어 수는 4 이상이 되어야 한다. 카페 투어를 하는..
[모의 SW 역량테스트] 2477. 차량 정비소 [모의 SW 역량테스트] 차량 정비소 1. 이해하기 N개의 접수 창구와 M개의 정비 창구가 있다. 고객은 접수 창구에서 고장을 접수하고 끝나면 정비 창구로 간다. 접수 창구 및 정비 창구의 담당자 업무 능력이 달라서 담당자 별 처리 시간이 다르다. 고객은 도착하는 대로 1번부터 고객번호를 부여 받는다. 접수 창구의 우선 순위 여러 고객이 기다리고 있는 경우 고객번호가 낮은 순서대로 우선 접수한다. 빈 창구가 여러 곳인 경우 접수 창구번호가 작은 곳으로 간다. 정비 창구의 우선 순위 먼저 기다리는 고객이 우선한다. 두 명 이상의 고객들이 접수 창구에서 동시에 접수를 완료하고 정비 창구로 이동한 경우, 이용했던 접수 창구번호가 작은 고객이 우선한다. 빈 창구가 여러 곳인 경우 정비 창구번호가 작은 곳으로 간..
[모의 SW 역량테스트] 2383. 점심 식사시간 [모의 SW 역량테스트] 점심 식사시간 1. 이해하기 이동 완료 시간은 모든 사람들이 계단을 내려가 아래 층으로 이동을 완료한 시간이다. 사람들이 아래층으로 이동하는 시간은 계단 입구까지 이동 시간과 계단을 내려가는 시간이 포함된다. 계단 입구까지 이동 시간: |PR-SR|+|PC-SC| (PR,PC: 사람 P의 세로,가로위치, SR,SC: 계단 입구 S의 세로,가로위치) 계단을 내려가는 시간 계단 입구에 도착하면, 1분 후 아래칸으로 내려 갈 수 있다. 계단 위에는 동시에 최대 3명까지만 올라가 있을 수 있다. 이미 계단을 3명이 내려가고 있는 경우, 그 중 한명이 계단을 완전히 내려갈 때까지 계단 입구에서 대기한다. 계단마다 길이 K가 주어지며, 계단을 완전히 내려가는데 K분이 걸린다. 모든 사람들이..
[모의 SW 역량테스트] 2382. 미생물 격리 [모의 SW 역량테스트] 미생물 격리 1. 이해하기 미생물들이 구역을 벗어나는걸 방지하기 위해, 가장 바깥쪽 가장자리 부분에는 특수한 약품이 칠해져 있다. 미생물의 움직임은 상, 하, 좌, 우 중 하나이다. 처음에 미생물은 약품이 칠해진 부분에 위치하지 않는다. 미생물 군집은 1시간마다 이동방향에 있는 다음 셀로 이동한다. 미생물 군집이 이동 후 약품이 칠해진 곳에 도착하면 군집 내 미생물의 절반이 죽고, 이동방향이 반대로 바뀐다. 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다. 합쳐 진 미생물의 이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다. M시간 후 남아 있는 미생물 수의 총합을 구하는 문제. 시뮬레이션 문제. 2. 구현하기 미생물의 움직임을 구현..
[모의 SW 역량테스트] 1953. 탈주범 검거 [모의 SW 역량테스트] 탈주범 검거 1. 이해하기 지하 터널은 총 7 종류의 터널 구조물로 구성되어 있다. 탈주범은 1시간에 인접한 네 방향으로 1 이동이 가능하다. 경과된 시간이 주어질 때 탈주범이 위치할 수 있는 장소의 개수를 구해야 한다. 2. 구현하기 현재 위치한 지하 터널과 다음에 이동할 지하 터널을 비교해서 이동할 수 있는 곳인지 판별해야 한다. 또한 지하 터널이 없는 곳은 탈주범이 이동할 수 없다. bool can_not_move(int x, int y, int nx, int ny, int d) { if(nx = N or ny = M or dist[nx][ny] != -1 or map[nx][ny] == 0) return true; if(map[x][..
[모의 SW 역량테스트] 1952. 수영장 [모의 SW 역량테스트] 수영장 1. 이해하기 수영장에서 판매하고 있는 이용권은 4 종류이다. 1일 이용권, 1달 이용권, 3달 이용권, 1년 이용권 이용권의 요금과 각 달의 이용 계획이 주어질 때, 이용 가능한 가장 적은 비용을 찾는 문제. 완전탐색 문제. 2. 구현하기 해당 달이 되었을 때, 각 이용권을 이용할 때의 비용을 각각 구해본다. 그리고 이 때의 최소값을 구한다. int solve(int index, int sum) { if(index >= 12) return sum; int ret = MAX; ret = min(ret,solve(index+1,sum+fee[0]*plan[index])); ret = min(ret,solve(index+1,sum+fee[1])); ret = min(ret,s..
[모의 SW 역량테스트] 1949. 등산로 조성 [모의 SW 역량테스트] 등산로 조성 1. 이해하기 등산로를 만드는 규칙은 다음과 같다. 등산로는 가장 높은 봉우리에서 시작해야 한다. 등산로는 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다. 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K깊이만큼 지형을 깎는 공사를 할 수 있다. 가장 긴 등산로를 찾아 그 길이를 출력. 시뮬레이션 문제. 2. 구현하기 등산로의 가장 높은 봉우리를 구한다. 여러개가 있을 수 있기 때문에 배열로 구한다. 이때, K만큼 깎는 공사를 한다고 하더라도 시작하는 위치는 바뀌지 않는다. vector get_max_hill() { vector ret; int max_value = 0; for(int i = 0; i < N; i++) { for(int ..
[백준] 17142번 연구소 3 17142번 연구소 3 1. 이해하기 현재 비활성인 바이러스 중 M개를 선택해서 활성 상태로 바꾼다. 바이러스는 상하좌우로 인접한 빈 칸으로 동시에 복제가 된다. 연구소는 빈 칸, 벽, 바이러스로 이뤄져있다. 바이러스는 벽을 통과하지 못한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다. 연구소의 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제. 모든 바이러스에 대해 구해보는 완전탐색 문제. 2. 구현하기 활성화 시킨 M개의 바이러스에 대해 퍼지는 시간을 구한다. void bfs(vector live_virus) { memset(virus_time,-1,sizeof(virus_time)); queue q; int size = live_virus.size..

티스토리툴바