'study/coding test' 카테고리의 글 목록 (4 Page)

study/coding test

37건

백준 14395 : 4연산

1. 문제 정리 - 입력받은 s값을 제시 받은 4개의 연산을 이용해 t값으로 변환한다. - 4개의 연산 중 나누기가 포함된 연산은 s가 0일 때는 사용할 수 없다. - s와 t는 1과 10^9 사이의 값이다.(주의하자.) 2. 접근 - 일반적인 bfs 방식으로 풀 수 있다고 생각하였다. - 4가지 연산자를 이동 가능한 범위, 그리고 정답 범위에 포함된 정수값을 이동할 수 있는 node라고 판단한다. - 중복 체크는 bool check 배열로 구현하기에는 검사 범위가 너무 넓기 때문에, set 을 사용하여 해결 - 검사 범위가 크기 때문에(10^9) int 형이 아닌 long 형으로 설정한다. 3. 풀이 #include #include #include using namespace std; struct nu..

10026 적록색약

1. 문제 정리 - 영역 정의 문제이다. 상하좌우로 인접한 값 중 같은 값을 가질 경우 하나의 영역으로 인식한다. - 적록색약의 경우 R 값과 G 값의 경우 같은 취급을 한다. 2. 접근 - 영역 정의 문제인 만큼 bfs로 풀기로 하였다. - 영역을 정의하는 기준이 두개인 만큼 bfs를 두가지로 나누어 하나는 비적록색약, 하나는 적록색약을 기준으로 하는 bfs를 구현하기로 했다. - 적록색약 기준 bfs의 경우 'R'과 'G'의 값을 동일시 하도록 하였다. 3. 풀이 //2021.12.06 #include #include using namespace std; int n; char a[100][100]; bool check[100][100][2]; int ans = 0; int wAns = 0; int d..

백준 1963 소수 경로

1. 문제 정리 - 비밀번호는 4자리이며, 소수이다. - 비밀번호는 한번에 한자리만 바꿀 수 있다. - 비밀번호는 4자리 수로, 1000 이상 9999이하이다. - 비밀번호 A에서 새로운 비밀번호 B로 바꾸기 위한 최소 변경 횟수를 구하라. - 변경할 수 없다면 Impossible을 출력하라. 2. 접근 - 비밀번호는 소수이므로 소수 판정을 필요로 한다. 에라토스테네스의 체를 이용하자. - 네자리 값을 모두 판별하기 위해 탐색을 해야한다. Brute Force를 BFS를 이용해 풀어나가자. - 시간 복잡도는 모든 가능한 경우의 수를 탐색하는 것으로 O(n) = O(10000)으로 제한시간인 2초 안에 문제를 풀 수 있다. 3. 풀이 #include #include using namespace std; b..

처음에 쉽게 풀거라 생각하고 덤볐다가 또 고전했다... 이 문제 또한 bfs를 이용해서 풀었다. 문제를 간단히 하자면, 간단하게도 방향 전환이 될 때, 방향 전환된 수의 최솟값을 통해 목적지까지 도달하는 문제이다. 코드를 먼저 보자. #include #include #include using namespace std; struct pos{ int x, y, dir, val; }typedef pos; int w, h; char a[101][101]; int change[101][101]; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, -1, 0, 1}; vector v; bool isPossible(pos p){ if(p.x = h ||..

이 문제는 꽤나 고전을 했던 것 같다. 이번에도 bfs 문제인데 문제도 꽤나 길고 조건도 많아서 차근히 정리하고 푸는 것을 추천한다. 먼저 조건부터 정리하자면 - 상어는 상하좌우 4방향으로 움직인다. - 상어는 자기보다 크기가 작은 물고기만 먹을 수 있으며, 같다면 지나갈 수 있고, 물고기가 더 크다면 지나갈 수 없다. - 상어가 더 이상 먹을 수 있는 물고기가 없다면 엄마 상어에게 도움을 요청한다 = 알고리즘이 종료한다. - 먹을 수 있는 물고기가 다수라면 가장 가까운 물고기를 향해 가며, 거리가 가깝다면 가장 위쪽, 그마저 윗방향으로 같은 값이라면 가장 왼쪽에 있는 물고기를 먹으러 간다. 그럼 이쯤에서 코드를 봐보자. #include #include using namespace std; struct ..

이번 문제도 bfs를 이용해서 풀었다. 먼저 짚고 넘어가야 할 점은 bfs가 시작될 지점이 하나가 아닌 다수라는 것. 즉, 물의 좌표와 고슴도치의 좌표 각각이 bfs를 시작해야한다는 것이다. 그럼 코드를 보겠다. #include #include #include using namespace std; class pos{ public: int x, y, min; pos(int a, int b, int c){ x = a; y = b; min = c; } pos(){x = 0; y = 0; min = 0;} }; char a[50][50]; bool check[50][50]; int dx[4] = {-1, 1, 0 ,0}; int dy[4] = {0, 0, -1, 1}; int r, c; vector water;..

8*8로 고정된 체스판에서 1초에 한번 위에서 아래로 한칸씩 움직이는 벽을 피해 가장 왼쪽 아래에서 가장 오른쪽 위로 캐릭터가 이동할 수 있는지 판별하는 문제이다. bfs로 풀거나, dfs로 풀거나 큰 차이는 없겠지만 나의 경우에는 bfs로 풀었다. 문제를 풀 때 인지해야할 부분은 1. 캐릭터는 대각을 포함한 총 8방향으로 움직일 수 있으며, 가만히 있는 것까지 총 9개의 움직임 경우를 갖는다. 2. 벽은 캐릭터가 움직인 이후에 아래 방향으로 한칸씩 움직인다. 3. 움직인 벽이 캐릭터와 겹칠 경우 해당 캐릭터는 움직일 수 없다. 위 세가지로 보인다. 그럼 코드를 보자 #include #include using namespace std; class point{ public: int x, y, sec; po..

이 문제를 처음 보았을 때는, 그저 단순하게 벽의 좌표들을 vector에 저장해놓고 각각을 기준으로 bfs를 이용하여 갈 수 있는 칸의 수를 체크하면 되겠구나! 하고 생각했다. 그 결과는 시간초과... 아마 나와 비슷한 경우의 사람들이 꽤 있을 거라 생각하고 정리해볼까 한다. 먼저, 위 아이디어 자체는 틀리지 않다. 맞다고 해도 좋을 것이다. 그런데 위에서 처럼 모든 벽에 대해 bfs를 순회한다? 그렇게 되면 중복 검사를 하는 배열의 수가 아주 많아져 결국 시간초과로 결론이 날 수 밖에 없는 것이다. 그럼 어떻게 해야할까? 간단히, 중복 검사를 최소화하면 된다. 아래는 내가 문제를 풀었던 코드이다. //2021.10.08 #include #include #include using namespace std..

이 문제를 처음 봤을 때는 다른 그래프 순회처럼 check 변수를 별 생각 없이 사용하여 문제를 풀고자 하였다. 그런데 check 배열을 선언하고자 하니 [1501][1501][1501]로 1501*1501*1501*1byte = 3234MB정도 나오는게 아닌가.. 택도 없다. 그럼 어떻게 배열을 줄일까? 우리는 세가지 변수 A, B, C를 받고 이는 임의의 수이므로 크기순으로 정렬을 하여도 문제의 답에는 영향을 전혀 주지 않는다. 그럼 이를 정렬한 세가지 값으로 max, mid, min이라 가정하였을 때, 그리고 A, B, C의 값의 합을 sum이라 하였을 때, sum = max + mid + min 으로 항상 같고 이는 곧 sum - max - min = mid라는 식 또한 만들 수 있다. 여기서 우..

1 2 3 4 5

티스토리툴바