본문 바로가기

알고리즘 문제풀이 입문: 코딩테스트 대비51

바둑이 승차(DFS) 설명철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요. 입력첫 번째 줄에 자연수 C(1둘째 줄부터 N마리 바둑이의 무게가 주어진다. 출력첫 번째 줄에 가장 무거운 무게를 출력한다. 예시 입력 1 259 58158423361 예시 출력 1242 문제 해결 철수가 가지고 있는 바둑이들 중에서 무게 C 를 초과하지 않으면서 가장 무거운 무게로 바둑이들을 트럭에 실을 수 있는 무게를 구하는 문제이다. 이는 DFS를 이용해 해결할 수 있다.  public class P.. 2024. 5. 10.
합이 같은 부분집합(DFS : 아마존 인터뷰) 설명N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. 입력첫 번째 줄에 자연수 N(1두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다. 출력첫 번째 줄에 “YES" 또는 ”NO"를 출력한다. 예시 입력 1 61 3 5 6 7 10  예.. 2024. 5. 10.
송아지 찾기1 (BFS) 설명현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.송아지는 움직이지 않고 제자리에 있다.현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 입력첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다. 출력점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다. 예시 입력 1 5 14 예시 출력 13 문제 해결 최단 거리 문제이므로 BFS를 사용하는 게 적합.. 2024. 5. 9.
그래프 최단거리(BFS) 설명다음 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선 수를 출력하세요. 입력첫 번째 줄에 정점의 수 N(1 출력1번 정점에서 각 정점으로 가는 최소 간선 수를 2번 정점부터 차례대로 출력하세요. 예시 입력 1 6 91 31 42 12 53 44 54 66 26 5 예시 출력 12 : 33 : 14 : 15 : 26 : 2 문제 해결 최단 거리이므로 BFS로 해결해보자.1에서 시작하기때문에 1은 03과 4 => 1 (한 번만에 갈 수 있으므로). 그리고 1,3,4는 큐에 들어간 상태이며 방문했다고 체크3이 큐에서 나오고 연결된 4. 4는 이미 체크됐으므로 4에서 연결된 5,6을 체크.5는 4의 값에 +1 (dis[nv] = dis[v] +1) 즉 2 그리고 큐에 들어가고 체크6도 2, 큐에 .. 2024. 5. 9.
경로탐색 (인접 행렬 / 인접 리스트) 설명방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 1 2 3 4 51 2 51 3 4 2 51 3 4 51 4 2 51 4 5총 6가지입니다.  입력첫 번째 줄에 정점의 수 N(1 출력총 가지수를 출력한다. 예시 입력 1 5 91 21 31 42 12 32 53 44 24 5 예시 출력 16  문제 해결 1번 정점에서 시작하여 N번 정점으로 가는 모든 경로의 수를 찾는 문제이므로 DFS를 이용해 모든 경로를 탐색할 수 있다.각 정점을 방문할 때마다 방문했다는 표시를 해두고, 탐색을 마친 후에는 그 표시를 지워 다른 경로에서 해당 정점을 다시 방문할 수 있게 해야 하는 것이 포인트이.. 2024. 5. 9.
Tree 말단 노드까지 가장 짧은 경로 (DFS, BFS) 설명아래 그림과 같은 이진 트리에서 루트 노드 1에서 말단 노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하시오. 각 경로의 길이는 루트 노드에서 말단 노드까지 가는데 이동하는 횟수를, 즉 간선의 개수를 길이로 한다.  가장 짧은 길이는 3번 노드까지의 길이인 1이다  문제 해결 사실 이 문제는 최단 거리를 구하는 문제이므로 DFS 보다는 BFS 가 더 적합하다. 연습을 위해 둘 다 풀어보라는 취지같다.   DFS를 이용하려면 루트 노드부터 시작해 말단 노드에 도달하면 현재 깊이를 반환하고, 부모 노드로 돌아가서 다시 다른 경로를 탐색하고 깊이를 반환하고....의 과정이다. 이를 통해 가장 짧은 길이를 찾으면 된다.public static int DFS(int L, Node root) { .. 2024. 5. 8.
반응형

티스토리툴바