코딩 테스트 준비! (백준)/DFS 17

[DFS] 백준 16964 DFS 스폐셜 저지(C++)

https://www.acmicpc.net/problem/16964 [BFS] 백준 16940 BFS 스폐셜 저지(C++) [BFS] 백준 16940 BFS 스폐셜 저지(C++)https://www.acmicpc.net/problem/16940 와우~ BFS 스폐셜 저지? [DFS,BFS] 백준 1260번 BFS와 DFS(C++) [DFS,BFS] 백준 1260번 BFS와 DFS(C++)https://www.acmicpc.net/problem/1260BFS와 DFS라는 개념에 대해서 아는가? 예제를 통한 예시lee-soo.tistory.com 사실 BFS 풀고 다음날에 푼 문제인데, 막혀가지고 이제서야 올린다 문제 자체는 BFS와 동일하게 접근하면 될 것 같다. BFS에서 문제를 풀 때 어떻게 풀었냐면..

[DFS] 백준 16947번 서울 지하철 2호선(C++)

https://www.acmicpc.net/problem/16947 내가 문해력이 떨어지는건지.. 너무 문제부터 이해하기 어려웠다이게뭐야 이런ㅡㅡ;; 잘 찾아보니까 앞선 graph처럼 노드들이 연결되어 있을때순환하는 친구하고 순환하지 않은 친구 구별하는 것 +순환하지 않는 친구의 순환하는 곳 까지의 거리 를 구하면 되는 것! 즉 예시 입력과 출력에 나온 건데 1,2,3의경우 "순환"하고 있고 5 4 6은 순환하지 않고 있다 이때 여기서 1 2 3 은 순환하는 역 까지의 거리가 0(자기자신)이니까 0이 출력되고 5 ,4 6 의 경우는 1 1 2 가 출력되는 것이다(제일 가까운 3까지의 거리가) [DFS,BFS] 백준 16929번 Two Dots(C++) [DFS,BFS] 백준 16929번 Two Dot..

[DFS,BFS] 백준 1260번 BFS와 DFS(C++)

https://www.acmicpc.net/problem/1260BFS와 DFS라는 개념에 대해서 아는가? 예제를 통한 예시를 보여주겠다 먼저 1,2 1,3 1,4 2,4 3,4라는 edge가 있는 경우를 그래프로 나타내보겠다 대략 이렇게 그려져 있다 그리고 문제내부에 보면 정점 번호가 작은것을 먼저 방문한다고 했다 그리고 bfs와 dfs에 대한 간략한 설명을 하자면 bfs : 현재 노드에서 방문할 수 있는 점을 먼저 모두 방문, 그 이후 연결된 점을 또 시작으로 방문가능한 모든 점을 방문(작은순서로) dfS:현재 노드에서 가장 깊에 들어갈 수 있는 점을 방문, (한 방향으로 끝까지) 막히면 되돌아와서 다른길을 탐색 그림으로 bfs를 먼저 설명해 주겠다입력상 1을 먼저 탐색하게 되니당연히 1이 먼저 들어..

[DFS] 백준 13023번 ABCDE(C++)

https://www.acmicpc.net/problem/13023 코테 준비를 할때마다 느끼는 건데, 진짜 30분안에 안풀리면 무조건 답지를 보자.오히려 내 방식대로 풀려다가 1시간 2시간 지나고 못풀면 그 자괴감이 더 크다. 심지어 푸는 방식도 달라서 내 접근법이 아예 틀렸을땐 정신적인 타격또한 후... 그나마 오늘푼건 1시간정도 끙끙대쓴데, 접근법은 맞아서 50%정도만 아팠다 내용은 간단하다 각 친구관계 사이가 주어졌을때 5명이 이어져서 친구인 관계가 존재하는가? 나는 여기서 어라, 이거 dfs로 depth 가 4일때 끊으면 되는거 아닌가? 생각하고그 각 값을 저장해줄 struct를 따로 만들어 보자고 생각했다 예를들어 struct s{bool arr[2000]} 을 하고, s를 배열로 정하는 거..

[DFS] 백준 1182번 부분 수열의 합(C++)

https://www.acmicpc.net/problem/1182 정말 많이 풀어본 유형 및 예제군...수열문제라... [DFS] 백준 15649번 N과 M (1,2,3) (C++) [DFS] 백준 15649번 N과 M (1,2,3) (C++)https://www.acmicpc.net/problem/15649 이 문제를 풀면서 나에게도 큰 시련이 찾아왔다. 도저히 못풀겠다 사실 글쓴이는 아직 코테 초보수준이라 해본게 브루트 포스랑, dp 랑.. 자료구조 뭐 이런것들인lee-soo.tistory.comn과 m 시리즈를 한번보고 와야겠군?정말 단순히 그냥! 들어오는 대로 더해주고 0인지 확인하고반복하면된다 단 주의해야 할 점은모든 수열이 아닌, 한가지 경우 만이므로(예를들어 1 3 5 의 경우 수열이 1..

[DFS] 백준 2529번 부등호(C++)

https://www.acmicpc.net/problem/2529 이 문제!!백트래킹! 모든 경우의수 찾아보자고 대충 문제는 이해가 갈 것이다 1.각 부등호 사이사이에 들어갈 수 있는 적절한 수열을 찾아 넣으시오2.단 중복되면 안됨 어떻게?? 나의 생각은 1.각 부등호 사이에 들어갈 수 있는 후보군 수열을 찾아놓는다2.그 후 실제로 부합한지 부등호에 맞게 검사(조건문) 아니면 return 우선 이렇게만 해도 대충 수열은 나올 것이고 이후, 나온 값들에 대한 최대 최소를 구해야되는데무작정 숫자로 바꿧다간, 012 의 경우 12로 출력되는 불상사가 발생할 수 있기에 출력또한 string 이나 char을 사용해야 한다. #include #include #include #include using namespac..

[DFS] 백준 1248번 Guess(C++)

https://www.acmicpc.net/problem/1248 영어를 보니 현기증이 난다.내용 자체는 생각보다 간단하다 해당 조건을 만족하는 수열을 찾아라! 1.n입력2.부호입력3.해당 부호에 맞는 수열 입력 해당 부호는 예를들어 수열이 3 -6 2 7일 경우 앞에서부터 하나씩 더한 값의 부호를 정하는 것이다. ex) 3 = 3 +3 - 6 = -3 -3-6+2 = -1 -3-6+2+7 = 6 +즉 +--+ 이렇게나오고그 다음은맨 앞 수를 제외한 나머지도 똑같이 진행 -6 =-6 --6 +2 = -4 --6+2+7 = 3 +- - +... 이렇게 진행해 나가는 것인데 이것을 처음 입력단에 쓴 후 적절한 수열 아무거나 출력하라는 뜻이다. 예를들어 4 +--+--++++ 이렇게 되어있다면 앞서 말한 수열..

[DFS] 백준 15661번 링크와 스타트(C++)

https://www.acmicpc.net/problem/15661  앞선 문제https://lee-soo.tistory.com/27 [DFS] 백준 14889번 스타트와 링크(C++)https://www.acmicpc.net/problem/14889 풀다 현타옴어려워서 아 핵심 더블 중복문 안에서, 한번 정해지면 다른팀은 자동으로 정해짐을 알고 있어야함  사실 이제, 비스무리하게 모든 경우의수를 처리lee-soo.tistory.com를 꼭 풀고 와주세요 여기선 단순히 팀의 인원수가 상관 없다고 되어있네요그럼 모든 경우의 수를 보면 됩니다앞서 스타트와 링크문제에서 풀때는 depth==n/2일때밖에 없었죠? 하지만 지금은 인원수 상관없이 depth>0 으로 하면 됩니다왜냐면 1명이상이 되면 상관이 없으니까..

[DFS] 백준 14889번 스타트와 링크(C++)

https://www.acmicpc.net/problem/14889 풀다 현타옴어려워서 아 핵심 더블 중복문 안에서, 한번 정해지면 다른팀은 자동으로 정해짐을 알고 있어야함  사실 이제, 비스무리하게 모든 경우의수를 처리해야 한다는것은 깨닫고 있었고 visited를 1차원 배열로 사용해야 함을 깨닫고 있었음왜? visited[][]을 2차원 배열로 하게되면1,3의 이 true가 되면 1 4는 false까 1이 또 선택될 수 있는 느낌 그래서 단순한 1차원 배열로 사용해야 했어   코드로보여줌#include #include #include using namespace std;bool visited[20];int arr[20][20];int sum = 0;int temp_min = 1000000;void t..

[DFS] 백준 14501번 퇴사(C++)

https://www.acmicpc.net/problem/14501 모든 직장인들의 가슴속에 담긴 단어"퇴사"짜자자잔 흠 쉽다쉬워 문제는 대충 이해가 갈 것이다 1일차에 3일되는 상담을 받으면비용 10 받고3일동안 못하니까 4일부터 시작하고... 이걸 n일까지 할 수 있는거잖아 n은 최대 15에다가, 시간은 2초나 주네?>>모든 경우의수 ㄱㄱ >>백트래킹 ㄱㄱ대충 위에 그려진 표를 보고 흐름을 적으면 이렇게 되겠지? 그리고 만약 6일차로 갔을 땐 t=2이고, 이 경우는 안되겠군.. 다시 뒤로 돌아가! backtracking 코드로 ㄱㄱ #include #include #include using namespace std;int arr[15][2];int sum = 0;int temp_max = 0;void..