본문 바로가기

반응형

dfs

(6)
[삼성 기출 문제] 백준 14888 연산자 끼워넣기 문제 링크 클릭시 문제로 이동합니다. 어떻게 풀까? 다행히도 연산자의 우선 순위가 모두 같기 때문에, 앞에서부터 차례차례로 처리하면 됩니다! 그리고, 더하기, 빼기, 곱하기, 나누기 연산의 개수가 나옵니다.그렇다는 것은, 현재 계산된 수에서 다음 수를 더하기, 빼기, 곱하기, 나누기 중 하나를 선택하고, 다음 수와 계산한 뒤에, 이렇게 계산된 수와 최댓값, 최솟값을 비교해서 계속 갱신해줍시다. 이렇게 모든 경우의 수를 다 구해서 저장된 최댓값과 최솟값을 출력하면 문제의 답을 출력할 수 있습니다! 3 3 4 5 1 0 1 0 위 예제를 통해서 한번 살펴봅시다. 처음에 더하기의 개수가 존재하기 때문에, 더하기의 개수를 하나 깎은 후에 3과 4를 더합니다. 다음에 더하기와 빼기의 개수가 0개이므로, 이 부분들..
[삼성 기출 문제] 백준 14502 연구소 문제 링크 클릭시 이동합니다. 어떻게 풀까? 문제를 크게 2 부분으로 나눠야 합니다. 1. 벽을 3개 세우는 부분2. 바이러스를 퍼뜨리는 부분 1번은 dfs를 이용해서 조합을 이용해서 해당 좌표에 벽을 세운다 or 안세운다 의 동작을 통해서 모든 구역에 벽을 3개씩 세워보는 방법을 이용합니다. 그리고 벽을 3개 세웠을 때, bfs를 이용해서 2번을 동작해서, 바이러스의 개수를 세서 이 최댓값을 출력하면 풀이는 완료됩니다! 2차원에서 조합을 이용하는 방법을 알아봅시다! n = 3이라고 하겠습니다. 시작은 (0,0) 입니다.우선, (0,0)에 벽을 세울지 안 세울지 정합니다. 우선 세운다고 가정하겠습니다. 그럼, 열의 크기를 1 늘려준 뒤에 해당 위치에서 다시 위의 과정을 반복합니다.이번에는 안세운다고 하겠..
[BOJ] 1405. 미친로봇 미친 로봇 성공스페셜 저지클릭시 이동합니다.어떻게 풀까? 중요한 것은 이전에 왔던 경로에 도착하지 않는 경우의 확률만 구해야 한다는 것입니다.즉, DFS를 통해서, N번을 이동하면서, 자신의 위치를 visit처리 해준 다음에, visit처리 되지 않은 방향으로만 이동합니다!그리고, 각 방향으로의 확률이 있기 때문에, 자신이 현재 도착한 위치의 확률 * 다음으로 이동할 확률을 계속 곱해가면서, 자신의 현재 위치에 대한 확률을 계속 가지고 있습니다! 그리고, N번의 이동을 완료했으면, 결과 확률에 그 확률을 더해주고, 이전 상황으로 돌아가서, 다른 방향을 탐색합니다! 그림으로 예를 들어 드리겠습니다! 처음엔 이 장소에서 시작합니다! 오른쪽으로 이동할 수 있습니다!예제에서는 오른쪽 확률이 0.25이기 때문에,..
[BOJ] 6603. 로또 로또클릭시 이동합니다. 어떻게 풀까? 조합 문제입니다! 심지어 숫자들도 오름차순으로 들어오기 때문에, 조합 짜는 코드만 잘 짜주시면 됩니다! 참고로, 최대 길이가 13밖에 되지 않으니, 선택했다는 것을 비트로 이용하여 나타낼 수 있습니다! 재귀 함수로 순열을 짜는 방법은 다음과 같습니다. 1. 해당 배열을 선택한다! - 이 경우에는 해당 배열을 선택했다는 select check를 해주고 다음 인덱스를 확인합니다.2. 해당 배열을 선택하지 않는다! - 이 경우에는 아무런 처리를 하지 않고 다음 인덱스를 확인합니다! 이렇게 하면, 마지막에 r이 0이 되거나, n이 r과 같아지는 경우에는 visit을 적절하게 1로 만들면서 visit을 이용하여 선택된 숫자들을 출력하면 됩니다. 코드 12345678910111..
[BOJ] 1219. 오민식의 고민 (18.8.22 그림 추가) 오민식의 고민클릭시 이동합니다. 어떻게 풀까? 으악... 저는 dfs와 bfs를 이용해서 풀었는데... 알고보니 벨만-포드 알고리즘이었어요.. 이따가 벨만-포드로 풀어서 해당 방법도 업데이트 하겠습니다. 버전 1과 2로 나누죠! Version.1 DFS and BFS 노드가 100개밖에 없으니 DFS를 이용해서 최댓값을 구해봅시다.잘 생각해보면, 해당 문제에서 양수 사이클이 생겨서 무한이 생기는 경우는, 방문했던 점을 또 방문할 경우에만 생깁니다.더 정확하게 말하면, 양수 사이클이 생겼을 경우이죠. 반대로, 음수 사이클이 생기는 경우에는 싸이클의 반복 경로를 탄다면, 가격이 계속 줄어든다는 것을 알 수 있죠!결국, 음수 사이클이 생기는 경우에는 반복 경로를 타지 않고 가는 것이 최대 수익을 얻는 경우입니..
[SW Expert Academy] 길찾기 길찾기 SW Expert Academy는 문제 복제가 금지되어 있기 때문에 링크로 대체하겠습니다. 어떻게 풀까? 대표적인 DFS / BFS 문제입니다.저 같은 경우는 그냥 시작점에서 큐를 돌려서 BFS를 이용해서 풀었습니다! 0번 노드에서 시작해서 0번 노드에서 이어지는 노드들을 모두 큐에 넣은 후에 방문 했다는 것을 체크해 둡니다.만약, 99번 노드가 나온다면 바로 연결되어있다는 것으로 끝내주면 됩니다.하지만 큐가 빌 때까지 99번 노드를 찾을 수 없다면, 시작 노드에서 끝 노드로 갈 수 없다는 것이 될 것입니다! 문제를 하나 풀어보겠습니다. 큐에 시작점인 0을 넣고, 0번을 방문 했다고 체크 합니다. 큐의 가장 위에 있는 0번 노드가 시작 노드가 됩니다.0번 노드가 가리키는 1번과 2번 노드를 큐에 ..

반응형