✔ 최소 스패닝 트리 [백준 1197] 문제 분석하기 최소 신장 트리를 구하는 가장 기본적인 문제 손으로 풀어보기 엣지 리스트에 엣지 정보를 저장한 후 부모 노드 데이터를 초기화하고, 사이클 생성 유무를 판단하기 위한 유니온 파인드용 부모 노드도 초기화 최소 신장 트리는 엣지 중심의 알고리즘이므로 데이터를 엣지 리스트를 활용해 저장해야 함 크루스칼 알고리즘을 수행 현재 미사용 엣지 중 가중치가 가장 작은 엣지를 선택하고, 이 엣지를 연결했을 때 사이클의 발생 유무를 판단 엣지를 더한 횟수가 노드 개수 - 1이 될 때까지 반복하고, 반복이 끝나면 엣지의 가중치를 모두 더한 값을 출력 슈도코드 작성하기 N(노드 수) M(엣지 수) parent(대표 노드 저장 배열) queue(엣지 정보를 저장할 우선순위 큐..
✔ 케빈 베이컨의 6단계 법칙 [백준 1389] 문제 분석하기 BFS 탐색 알고리즘을 이용해도 해결할 수 있는 문제이지만, 유저의 최대 수가 100 정도로 작기 때문에 플로이드-워셜 알고리즘 이용 1번째로 사람들이 직접적인 친구 관계를 맺은 상태를 비용 1로 계산하여 인접 행렬에 저장하는 방법으로 접근 손으로 풀어보기 친구 관계 정보를 인접 행렬에 저장 자기 자신이면 0, 아니면 충분히 큰 수로 인접 행렬의 값을 초기화 그리고 주어진 친구 관계 정보를 인접 행렬에 저장 플로이드-워셜 알고리즘을 수행 케빈 베이컨의 수를 비교해 가장 작은 수가 나온 행 번호를 정답으로 출력 슈도코드 작성하기 N(유저 수) M(친구 관계 수) distance(친구 관계 데이터를 저장하는 인접 행렬) for(i -> N만큼 반..
✔ 경로 찾기 [백준 11403] 문제 분석하기 모든 노드 쌍에 관해 경로가 있는지 여부를 확인해야 하므로 플로이드-워셜 알고리즘을 사용하여 문제에 접근 단, 최단 거리를 구하는 문제가 아니기 때문에 최단 거리를 업데이트하는 부분만 조금 수정 필요 손으로 풀어보기 인접 데이터를 인접 행렬에 저장 변경된 플로이드-워셜 알고리즘을 수행 S와 E가 모든 중간 경로 중 1개라도 연결돼 있다면 S와 E는 연결 노드로 저장 알고리즘으로 변경된 인접 행렬을 출력 슈도코드 작성하기 N(인접 행렬의 크기) distance(노선 데이터를 저장하는 인접 행렬) for(i -> N만큼 반복하기) { for(j -> N만큼 반복하기) { 인접 행렬 데이터를 distance 행렬에 그대로 저장하기 } } for(k -> N만큼 ..
✔ 플로이드 [백준 11404] 문제 분석하기 모든 도시 쌍과 관련된 최솟값을 찾아야 하므로 플로이드-워셜 알고리즘을 사용 손으로 풀어보기 버스 비용 정보를 인접 행렬에 저장 연결 도시가 같으면 0, 아니면 충분히 초기화 그리고 주어진 버스 비용 데이터값을 인접 행렬에 저장 플로이드-워셜 알고리즘을 수행 3중 for문으로 모든 중간 경로를 탐색 알고리즘으로 변경된 인접 행렬을 출력 슈도코드 작성하기 N(도시 개수) M(노선 개수) distance(노선 데이터를 저장하는 인접 행렬) for(i -> N만큼 반복하기) { for(j -> N만큼 반복하기) { 시작 도시와 종료 도시가 같으면 0, 아니면 충분히 큰 수로 저장하기 } } for(M만큼 반복하기) { 노선 데이터를 distance 행렬에 저장하기..
✔ 오민식의 고민 [백준 1219] 문제 분석하기 벨만-포드 알고리즘의 원리를 바탕으로 요구사항에 따라 내부 로직을 바꿔야 함 기존 벨만-포드 알고리즘은 최단 거리를 구하는 알고리즘이지만, 이 문제는 도착 도시에 도착할 때 돈의 액수를 최대로 하고 싶기 때문에 업데이트 방식을 반대로 변경해야 함 또한 돈을 무한히 많이 버는 케이스가 있을 수 있으므로 음수 사이클이 아닌 양수 사이클을 찾도록 변경해야 하며 마지막 예외 처리 1개를 사용하여 도착 도시에 가도록 해야 함 이를 위해 기존 엣지의 업데이트처럼 N - 1번이 아닌 충분히 큰 수만큼 추가로 돌리면서 업데이트를 수행하도록 로직을 변경 손으로 풀어보기 엣지 리스트에 엣지 데이터를 저장하고, 거리 배열값을 초기화 변형된 벨만-포드 알고리즘을 수행 시작 도..
✔ 타임머신 [백준 11657] 문제 분석하기 시작점 및 다른 노드와 관련된 최단 거리를 구하는 문제이며, 엣지에 해당하는 이동하는 시간이 양수가 아닌 0 또는 음수가 가능하므로 발만-포드 알고리즘을 사용 손으로 풀어보기 엣지 리스트에 엣지 데이터를 저장한 후 거리 배열을 초기화 벨만-포드 알고리즘을 수행 음수 사이클이 존재하면 -1, 존재하지 않으면 거리 배열의 값을 출력 단, 거리 배열의 값이 INF일 경우에는 -1을 출력 슈도코드 작성하기 자료 구조 선언하기(그래프 정보 저장, 최단 거리 저장) N(노드 개수) M(엣지 개수) Edges(엣지 리스트 배열) 거리 배열을 충분히 큰 수로 초기화하기 for(엣지 개수) { 엣지 리스트 배열에 이 엣지 정보를 저장하기 } 거리 배열에 출발 노드 0으로 초..
✔ K번째 최단경로 찾기 [백준 1854] 문제 분석하기 시작점과 도착점이 주어지고 목적지까지 가는 K번째 최단 경로를 구하는 문제이므로 다익스트라 알고리즘으로 접근 최단 경로가 아니라 K번째 최단 경로이므로 최단 경로를 표현하는 배열을 우선순위 큐 배열로 변경하도록 함 손으로 풀어보기 도시는 노드로, 도로는 엣지로 나타내어 그래프를 그림 도시 개수의 크기만큼 인접 리스트 배열의 크기를 설정하고 도로 개수의 크기만큼 반복문을 돌면서 그래프를 리스트 배열에 저장 최단 거리 배열을 우선순위 큐 배열로 선언하고, 규칙에 따라 최단 거리 배열을 채움 현재 노드에 저장된 경로가 K개 미만일 때 신규 경로를 추가함 경로가 K개일 때 현재 경로 중 최대 경로와 신규 경로를 비교해 더 작을 때 업데이트 K번째 경로를 ..
✔ 최소비용 구하기 [백준 1916] 문제 분석하기 시작점과 도착점이 주어지고, 이 목적지까지 가는 최소 비용(최단 거리)을 구하는 문제이므로 다익스크라 알고리즘을 이용 손으로 풀어보기 도시는 노드로, 도시 간 버스 이용은 엣지로 나타냄 도시 개수의 크기만큼 인접 리스트 배열의 크기를 설정하고 버스 개수의 크기만큼 반복문을 돌면서 그래프를 리스트 배열에 저장 이때 버스의 비용이 존재하므로 인접 리스트 배열의 자료형이 될 클래스를 선언 다익스트라 알고리즘을 수행 최단 거리 배열이 완성되면 정답을 출력 슈도코드 작성하기 자료구조 선언하기(그래프 정보 저장, 최단 거리 저장, 노드 사용 여부 저장) N(노드 수) M(엣지 수) 선언한 변수들을 초기화하기 거리 배열은 충분히 큰 수로 초기화하기 for(노드 개수..
