본문 바로가기
반응형

알고리즘

 (136)
[백준] 15685번 드래곤 커브 15685번 드래곤 커브 1. 이해하기 드래곤 커브의 다음 세대가 변하는 규칙을 찾아야 한다. 규칙을 보면 가장 최근에 추가된 방향부터 차례대로 90도 반시계 방향 회전해서 다음 세대에 추가하는 것을 볼 수 있다. 규칙대로 드래곤 커브를 표시해주고 표시된 것 중 사각형의 갯수를 찾아서 출력해 주면 된다. 시뮬레이션 문제. 2. 구현하기 드래곤 커브의 다음 세대를 구해 반환해준다. vector get_next_cur(vector cur) { vector ret = cur; int size = cur.size(); for(int i = 0; i < size; i++) { int dir = cur.back(); cur.pop_back(); dir = (dir+1)%4; ret.push_back(dir); } ..
[백준] 15684번 사다리 조작 15684번 사다리 조작 1. 이해하기 사다리에 가로선을 놓아 길을 만들어 자신이 출발한 세로선과 끝난 세로선이 같도록 해야 한다. 사다리의 가로선을 모두 놓아보는 완전 탐색 문제. 2. 구현하기 사다리를 타고 내려가보면서 자신이 출발한 세로선에서 끝나는 경우인지 판단. bool is_all_match() { for(int i = 0; i = 0 and map[x][y-1] == num) { y--; } else if(y+1 < N and map[x][y+1] == num) { y++; } } x++; } if(y != i) return false..
[백준] 15683번 감시 15683번 감시 1. 이해하기 CCTV는 5가지 종류가 있다. 종류마다 감시할 수 있는 방법이 다르다. CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있지만 벽은 통과해서 감시하지 못한다. 이를 사각지대라 부른다. CCTV는 90도 방향으로 회전할 수 있다. CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구해야 한다. 각 CCTV마다 방향을 달리해 사각지대를 구하는 완전탐색 문제. 2. 구현하기 카메라의 종류, 현재 위치와 가리키고 있는 방향을 받아와 그 방향으로 감시할 수 있는 영역을 표시한다. bool out_of_bound(int x, int y) { return x = N or y = M; } void mark_view_area(in..
[백준] 14891번 톱니바퀴 14891번 톱니바퀴 1. 이해하기 톱니바퀴가 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수 있다. 옆에 있는 톱니바퀴를 회전시키는 경우는 맞닿은 극이 서로 다를 경우에 반대 방향으로 회전하게 된다. 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 문제. 시뮬레이션 문제. 2. 구현하기 톱니바퀴를 시계방향 혹은 반시계방향으로 회전시킨다. void rotate(int n, int dir) { if(dir == 1) { char temp = gear[n][7]; for(int i = 7; i > 0; i--) { gear[n][i] = gear[n][i-1]; } gear[n][0] = temp; } else if(dir == -1) { char temp = gear[n]..
[백준] 14890번 경사로 14890번 경사로 1. 이해하기 지도에서 지나갈 수 있는 길이 몇개인지 세는 문제이다. 지나갈 수 있는 길은 평평한 길이거나 경사로를 설치할 수 있는 길을 의미한다. 경사로는 높이 차이가 1인 곳, 경사로의 길이 만큼의 평평한 길이 있을 때만 설치할 수 있다. 경사로를 이미 설치한 곳에 또 설치를 할 수 없다. 시뮬레이션 문제. 2. 구현하기 행과 열의 특정 길이에 대해 경사로를 설치할 수 있는지 판단한다. 설치할 수 있으면 설치한다. bool can_install_row(int i, int st, int en) { int temp = map[i][st]; for(int j = st; j = N) { flag = false; break; } if(!can_install_col(i,st,en)) { fl..
[백준] 14889번 스타트와 링크 14889번 스타트와 링크 1. 이해하기 전체 N명에서 N/2명으로 두 팀을 나눠서 각 팀의 선택된 사람들의 능력치 차이의 최소를 구하는 문제이다. 모든 경우를 다 해보는 완전탐색 문제. 2. 구현하기 N명에서 N/2을 고르는 방법을 만든다. 그 후 각 팀에서 고른 사람들의 능력치 차이의 최솟값을 반환한다. int solve(int index, int cnt) { if(index > N) return MAX; if(index == N and cnt == N/2) { int sum1 = 0, sum2 = 0; for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { if(i == j) continue; if(selected[i] and selected[j]) ..
[백준] 14888번 연산자 끼워넣기 14888번 연산자 끼워넣기 1. 이해하기 수와 수 사이에 연산자를 하나씩 넣는데 주어진 수의 순서를 바꾸면 안 된다. 연산자는 수의 개수-1 개가 주어지기 때문에 모두 사용해야 한다. 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구해야 한다. 만들 수 있는 결과를 모두 만들어 보는 완전탐색 문제. 2. 구현하기 최대인 것과 최소인 것을 반환하기 위하여 구조체를 만든다. struct RET { int min_val,max_val; }; 연산자를 모두 쓰는데 오버해서 쓰면 최댓값과 최솟값을 반환해준다. RET solve(int index, int plus, int minus, int mul, int div, int val) { if(plus < 0 or minus < 0 or mul < 0 or d..
[백준] 14503번 로봇 청소기 14503번 로봇 청소기 1. 이해하기 맵의 끝부분은 모두 벽으로 되어 있다. 청소기는 바라보는 방향이 동, 서, 남, 북중 하나이다. 청소기는 다음과 같이 작동한다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 있다면, 그 방향으로 회전, 한칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 네 방향 모두 청소가 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진하고 2번으로 돌아간다. 네 방향 모두 청소가 되어있거나 벽이면서, 뒤쪽 방향이 벽이면 작동을 멈춘다. 로봇 청소기는 벽을 통과할 수 없다. 로봇 청소기가 청소한 영역의 크기를..

티스토리툴바