개발기록 개발기록

https://algospot.com/judge/problem/read/TSP1 algospot.com :: TSP1 Traveling Salesman Problem 1 문제 정보 문제 NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 정확히 한 번씩 방문하는 가장 짧은 경로를 찾는 문제이다. 이 문제를 다항 시간에 해결할 수 있는 방법은 현재까지는 존재하지 않지만, 도시의 숫자가 작은 경우에는 비교적 사용 가능한 시간 안에 algospot.com n의 크기에 따라 풀이법을 달리해야 하는 유명한 문제라고 한다. 이 문제는 n이 8로 매우 작으므로 완전탐색으로..

https://algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다. 게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요. 입력 력의 첫 algospot.com 전형적인 완전탐색 문제였다. 접근방법 1. 2차원 배열에서 한 칸씩 이동한다. 2. 이때 ..

1. 문제를 읽고 이해하기 2. 재정의와 추상화 3. 계획 세우기 4. 계획 검증하기 5. 계획 수행하기 6. 회고하기 1.문제를 읽고 이해하기 문제를 실수없이 이해하기 2.재정의와 추상화 자신이 다루기 쉬운 개념을 이용하여 문제를 자신의 언어로 풀어 쓰는 것 + 추상화 3. 계획 세우기 문제를 어떤 방식으로 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택 4. 계획 검증하기 설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지를 증명하고, 시간과 메모리가 제한 내에 들어가는지 확인 5. 계획 수행하기 코드의 중복없이 코딩 알고리즘이라는 도구를 사용할 때는 일관된 방법으로 사용 6. 회고하기 문제 해결 기술은 추상적인 기술이다. 따라서 끊임없이 자신이 이 기술들을 어떻게 사용하고 있는지 돌아..

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 ..