본문 바로가기
728x90
반응형

전체 글77

[algorithm] 백준 - 경사로 삼성 SW 기출문제이다. 구현문제인데, 문제를 이해하고 나면 쉽게 풀 수 있는 문제이다. 문제를 분석해보면, 탐색할 때 총 세가지의 경우로 나눌 수 있다. 이 외의 경우는 탐색에서 나가도록 break 처리 해준다. 1. 현재 칸과 같은 높이의 칸일 때 길이가 L인 경사로를 놓기 위해서는 동일한 칸의 개수를 세야한다. 그러므로 현재 칸과 같은 높이의 칸일 때 칸의 개수를 증가해준다. 2. 현재 칸보다 한칸 높은 층일 때 칸의 개수가 L보다 작을 때 경사로를 놓을 수 없으니까 탐색에서 나가도록 break 처리한다. 그렇지 않으면 칸의 개수를 1로 갱신한다. 현재 칸을 고려하여 0이 아닌 1로 갱신해야한다. 3. 현재 칸보다 한칸 낮은 층일 때 칸의 개수가 이미 음수일 경우엔 탐색에서 나가도록 break처리한.. 2020. 12. 23.
[algorithm] 백준 - 연산자 끼워넣기 이 문제는 dfs이다. 덧셈 뺄셈 곱셈 나눗셈 총 4가지의 연산자로 모든 경우의 수를 따졌을 때 최댓값, 최솟값을 구하는 문제이다. 처음에 순열로 구현했었는데, 같은 경우의 수가 여러개 나올 수 있었다. 덧셈 뺄셈 곱셈 나눗셈 각 1개씩으로 이루어진 것이 아닌 여러개로 이루어져 있기 때문이다. 그렇기 때문에 분기를 4가지로 나누어야 한다는 특징이 있었다. 코드는 이렇다. //연산자 끼워넣기 #include #include using namespace std; int num[12]; int maxNum = -9876543210; int minNum = 9876543210; void permutation(int index, int size, int plusCount, int minusCount, int mu.. 2020. 12. 22.
[algorithm] 백준 - 로봇 청소기 이 문제는 시뮬레이션, bfs문제이다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다. 로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다. 우선 왼쪽 방향으로 전진하는 함수, 후진하는 함수를 따로 작성해뒀다.. 2020. 12. 22.
[algorithm] 백준 - 구슬탈출(2) 이 문제는 삼성 SW 기출 문제이다. 빨간 구슬을 구멍을 통해 빼내기 위해 기울이는 최소 횟수를 구해야 하므로 BFS로 풀었다. 문제에서 지켜야하는 조건이 있다. 1. 빨간 구슬과 파란 구슬이 같이 들어가면 실패 2. 빨간 구슬이 파란 구슬보다 먼저 들어가야 함 빨간 구슬과 파란 구슬을 이동하는 방향을 동일하게 설정해야하므로 방문 여부를 판단하는 배열의 인덱스도 빨간 구슬과 파란 구슬 모두의 방문유무를 설정해야한다. 이 방문 배열을 만드는 것을 생각하는 것이 가장 핵심이다. 그리고 큐에 넣을 때도 빨간 구슬과 파란 구슬의 위치, depth를 push해야한다. 따로따로 탐색하는 것이 아니라 같이 탐색해야한다! 참고로 중력에 의해 구슬의 위치가 정해지는데, ##### #..R# #...# #O.B# ####.. 2020. 12. 18.
728x90
반응형

티스토리툴바