본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

Algorithm/DFS15

[DFS] 양과 늑대 - 2022 KAKAO BLIND RECRUITMENT 해결 방법 사실상 모든 경로를 다 따져봐야 하는 문제다. 물론, 양과 늑대의 수가 같아지는 시점부터는 해당 경로에 대한 dfs는 중단해야 한다. 필자는 현재까지의 방문 노드들을 하나의 통합 노드로 두고, 통합 노드의 인접 노드들을 하나씩 방문해나가는 방법으로 해결했다. 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장한다는 접근법만 놓고 보면 프림 알고리즘과 비슷한 느낌이 들지 않는가? 물론 간선의 비용도 없고 dfs이기 때문에 방문을 취소해야 할 때가 있다는 차이점이 있기는 하다. 인접노드를 방문했을 때 양과 늑대의 수가 같아지거나 더 이상 방문할 노드가 없다면 해당 경로에 대한 dfs를 중단하면서 방문도 취소해주면 된다. 소스 코드 #include using namespace std; vecto.. 2022. 10. 14.
[DFS] 경주로 건설 - 2020 카카오 인턴십 해결 방법 DP와 DFS를 병행하여 해결하였으며, DP없이 DFS로만 해결하면 시간초과가 나온다. 이 문제의 경우에는 나아가는 방향이 직진인지 코너인지를 판별하여 100 또는 600(코너 비용 500추가)을 더해야 한다. 이를 위해서는 다음 DFS 재귀함수를 반복할 때 현재의 진행 방향이 전달되어야 한다. 이 때, 동서남북을 일일이 가려낼 필요는 없으며 가로(동서) 방향과 세로(남북) 방향만 알면 된다. 연산시간 절약을 위해 현재 dfs 재귀에서 cost가 answer값을 넘는다면 더 이상 dfs 재귀를 수행하지 않도록 했다. 그리고 진행 칸에 대한 최소 비용이 갱신되지 않았다면 이 역시 더 이상 dfs 재귀를 수행하지 않도록 하되, 직선 도로와 코너 건설 비용의 차이인 500이 있을 수 있다는 사실을 .. 2022. 5. 11.
[DFS] 불량 사용자 - 2019 카카오 개발자 겨울 인턴십 경우의 수를 구하는 유형의 문제는 DFS 또는 DP 문제일 확률이 높다. 경우의 수를 조합이나 순열같은 수식으로 해결해보려고 시도해보았지만 꽤 복잡해서 DFS로 풀기로 결정했다. 해결 방법 먼저, banned_id의 1번째 id와 매칭 가능한 user_id가 있는지 확인해서 매칭 가능한 user_id를 발견했다면 save 벡터에 해당 user_id를 저장해둔다. 그리고 이후의 banned_id들에 대해서도 동일한 과정을 반복하여 모든 banned_id가 매칭되었다면 하나의 경우가 완성된 것이다. 이 때의 save 정보를 다른 벡터에 저장해놓고 DFS를 이어서 수행해주면 된다. 조건에 맞는 모든 경우들을 모두 저장했다면 중복되는 아이디 목록을 최종적으로 제거해주고 남은 경우의 수를 구하면 문제가 해결된다... 2022. 4. 5.
[DFS] 다단계 칫솔 판매 - 2021 Dev-Matching 난이도가 Level3인 것 치고는 쉽게 해결한 것 같다. 이 문제는 DFS로 해결할 수 있으며, 분배금을 10% 떼어내고 남은 몫은 자신이 가지고 다음 노드(인원)에게 10%의 분배금을 전달하는 과정을 반복하면 된다. 그리고 일일이 간선을 연결하는 과정 없이 map을 활용하여 간단히 DFS를 수행할 수 있다. 주의할 점이 있다면, 분배금이 1원 미만일 때에도 DFS를 진행하면 시간초과가 난다. 그래서 반드시 분배금이 있을 때만 DFS 함수를 호출해야 한다. 소스 코드 #include #include using namespace std; map mres; map mref; vector answer; void distribute(string seller, int money) { if(seller=="-") .. 2022. 4. 3.
[DFS] 괄호 변환 - 2020 카카오 블라인드 채용 단순히 주어진 조건대로 코딩하면 되는 문제이기 때문에 소스 코드에 사용된 함수만 설명하였다. bcheck 함수 괄호 문자열에는 균형잡히지 않은 괄호 문자열, 균형잡힌 괄호 문자열, 올바른 괄호 문자열 3가지 경우가 있는데, 어느 경우인지를 판단하여 반환하는 함수다. 괄호 문자열을 첫 문자부터 검사하면서 누적 '('과 ')'의 수를 카운트 하여 어느 케이스의 문자열인지 판단할 수 있다. - 균형잡히지 않은 괄호 문자열 : 누적 ')'의 개수가 누적 '(' 개수보다 큰 순간이 있는 경우 - 균형잡힌 괄호 문자열 : 총 ')'의 개수와 총 '(' 개수가 같은 경우 - 올바른 괄호 문자열 : 총 ')'의 개수와 총 '(' 개수가 같고, 누적 ')'의 개수가 누적 '(' 개수보다 큰 순간이 없었을 경우 dfs 함.. 2022. 3. 13.
[DFS, 난이도 중] 프로그래머즈, 쿼드압축 후 개수 세기 전체 영역을 4분할 한뒤 분할 영역 안의 요소가 모두 같을 경우에는 압축하고, 그렇지 않을 경우에는 분할 영역을 다시 4분할해가는 식으로 진행한다. 이 방식으로 모두 압축했을 때 남아있는 0,1의 개수를 계산하면 되는 문제이다. 자세한 설명은 맨 아래 첨부한 코드의 주석에 달아놓았다. dfs함수를 수행하기 전에 전체 영역에 대해 요소가 모두 같은지 여부를 알아내야 한다. 그 이유는 dfs함수에서는 영역을 4분할 하고 계산하기 때문에, 전체 영역을 바로 넣어버리면 전체 영역에 대해 요소가 모두 같더라도 강제로 4분할이 되어 버린다. 이러한 과정이 없다면, [[1,1],[1,1]] 이 입력으로 주어지더라도 출력값은 [0,1]이 아닌 [0,4]가 되어버릴 것이다. 테스트 케이스 16개 모두 통과 #includ.. 2020. 10. 19.
DFS/BFS 고득점 kit 풀이 완료, 후기 본인이 이전에 DFS/BFS에 대해 설명한 포스팅이 있다. 저 때는 설명에 필요한 그림을 손으로 직접 그렸는데... 얼마 안돼서 한계를 깨닫고 파포로 갈아탔다. kimcoder.tistory.com/15?category=879722 [BFS, 난이도 하] 백준 1260번 DFS와 BFS BFS, DFS 알고리즘의 기본 원리를 공부한 사람이라면 쉽게 풀 수 있을 만한 문제이다. BFS(너비우선탐색)는 자신의 노드 주변에 자신이 갈 수 있는 경로들부터 탐색하는 알고리즘으로, 방문하지 않� kimcoder.tistory.com 프로그래머즈에 와서 문자열 DFS/BFS 문제를 처음 접해보았는데 이런 문제들은 고민을 좀 하고 풀었다. 지금까지 노드에 번호가 매겨져 있는 문제만 풀었는데 특히 '여행 경로' 문제는 .. 2020. 9. 30.
[DFS, 난이도 중하] 프로그래머즈, 타겟 넘버 문제 설명에 쓰인 예제를 예로 들어 풀이 하겠다. □1□1□1□1□1 = 3에서 □에 +/- 를 넣어 3을 만들 수 있는 경우의 수를 계산하면 되는 문제이다. 이를 해결하기 위해서, 뒤에 있는 □일 수록 깊이가 커지는 DFS를 수행하면 된다. 예를 들면 탐색 순서는 +++++ ++++- +++-+ +++-- ++-++ ...... 이런 식인 것이다. DFS의 깊이가 numbers의 크기와 같아지면 리턴을 하되, 누적 값이 target과 같다면 리턴하기 전에 answer에 1을 더하고 target과 같지 않다면 그냥 리턴만 해버리면 된다. 테스트 케이스 8개 모두 통과 #include using namespace std; int answer; void dfs(int sum, int depth, vector.. 2020. 9. 29.
[DFS, 난이도 중] 프로그래머즈, 단어 변환 begin을 시작점으로 두고 words중에서 현재 단어와 알파벳 하나만 차이나는 단어로 변환해 나가며, 최소 몇 번째 변환만에 target이 되는가 계산하는 문제이다. target이 될 때 까지 연속으로 변환한다는 점에서 DFS문제라는 것을 알았다. 문자열 a,b가 알파벳 하나만 차이나는가 여부를 판단하기 위해 connect 함수를 만들었다. 먼저 connect 함수를 이용하여 begin과 words를 비교해나가며 참일 경우 간선을 설정한다. 다음에는 words단어끼리 간선을 설정한다. 그리고 편리를 위해 정점마다 번호를 매겨주었다. target은 정점 번호를 0으로 정했고, words의 i번째 단어의 정점 번호를 i+1로 매겼다. words에서 target이 있는 위치를 알기 위해 target_inde.. 2020. 9. 29.

티스토리툴바