전체 글
-
종만북 문제 해결 알고리즘? 2019. 12. 21. 02:11
1. 문제를 읽고 이해하기 2. 재정의와 추상화 3. 계획 세우기 4. 계획 검증하기 5. 계획 수행하기 6. 회고하기 1.문제를 읽고 이해하기 문제를 실수없이 이해하기 2.재정의와 추상화 자신이 다루기 쉬운 개념을 이용하여 문제를 자신의 언어로 풀어 쓰는 것 + 추상화 3. 계획 세우기 문제를 어떤 방식으로 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택 4. 계획 검증하기 설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지를 증명하고, 시간과 메모리가 제한 내에 들어가는지 확인 5. 계획 수행하기 코드의 중복없이 코딩 알고리즘이라는 도구를 사용할 때는 일관된 방법으로 사용 6. 회고하기 문제 해결 기술은 추상적인 기술이다. 따라서 끊임없이 자신이 이 기술들을 어떻게 사용하고 있는지 돌아..
-
백준 1922번 네트워크 연결PS 2019. 12. 20. 21:25
https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소신장트리 기본 문제입니다. 본인은 크루스칼 알고리즘과 프림 알고리즘으로 풀어보았습니다. 1. 그래프의 상태는 따로 저장해놓고(v에 저장하였습니다) 아무것도 연결되어있지 않은 상태에서 시작합니다. 2. 그래프의 간선을 가중치를 기준으로 오름차순 정렬합니다. 3. 가중치가 가장 작은 간선부터 연결합니다. 이때, 사이클이 생기지 않아야 합니다. 이를 위해서 유니온-파인드 기법을 이용합니다. #include #include #include using namespace std; struct ..