문제 링크 https://www.acmicpc.net/problem/1987 오늘의 생각 : 시간 초과가 날때, 백트래킹 기준이 안보이면 방식을 바꿔보자. ◆문제 해결 및 설명◆ 문제 해설 : 알파벳이 써있는 맵위 (0,0) 위치에서 출발하여 상하좌우로 움직일때, 새로 이동한 칸은 지금까지 지나온 모든 칸에 적혀있는 알파벳과 달라야 할때 최장거리를 구하여라 처음에는 맵을 나타내는 이차원 배열 map의 크기와 같게 visited 배열을 선언하고 못 가는 곳을 1로 설정해 dfs로 구현하였으나, 시간 초과로 인하여 visited를 일차원 배열로 설정 하였다. ◆코드 전문◆ #include #include #include using namespace std; int R, C, answer = 0; vector..
2022년 2학기에 학부 캡스톤 디자인 프로젝트를 회고하는 글이다. 프로젝트 개요 내가 이번 프로젝트에서 팀장으로 선정되어, 3명의 팀원과 함께 안드로이드 애플리케이션을 개발하게 되었다. 우리 팀은 프로젝트의 주제를 결정하기 위해 회의를 진행하였는데, 주제를 정할 때 애로사항이 많았는데, 의견이 없거나, 의견은 있는데 개발 난이도가 높은 의견이 나왔다. 개발 난이도가 높은 의견 중에 대표적으로 중고거래 앱이였는데, 팀원 중 서버 경험자, 안드로이드 경험자가 둘 다 없었기 때문에 팀에 부담이 크다고 생각해서 기각하였다. 다른 주제를 고민하던 중, 전에 아플 때 어떻게 대처해야 할지, 어느 병원을 가야 할지 몰라 고생했던 기억이 났고, 이를 제안하여 응급상황시 도움을 줄 수 있는 앱을 만들기로 결정하였다. ..
서론 오늘도 문제 풀다 번아웃이 왔다. 4시간 동안 풀었다... 4일 차 대체 경로 문제 : 요약이 힘들어 사진으로 대체 가장 짧은 거리를 찾는것임으로 BFS를 이용하여서, 하나의 길이 만들어진다면 종료되도록 구성하였다. 단순한 BFS를 구현하면 Timeout이 발생함으로 distace 배열을 통하여 거리를 저장하여 계산을 구현하였다. ◆코드 전문◆ #include #include #include using namespace std; int node, edge, start, endNode; int bfs(int day,vector &edgeList) { if (day == start || day == endNode) { return -1; } vector distance(node + 1, -1); vec..
서론 진짜 순수 문제 풀이 시간만 5시간은 걸렸다. 이렇게 어렵게 풀 문제였나 생각이 들어서 마음이 심란했던 하루다. 2일 차 통신망 분석 문제 : 그래프에서 연결된 것들의 집합 중 가장 밀도가 높은 컴포넌트의 정보를 구하자. 간선을 2차원 배열 edge에 받아 저장해 주었다. 빠른 시간 복잡도를 위해서 각 노드(i)에서 갈수 있는 노드(j)를 저장해 주었다. 연결된 것들의 집합을 DFS를 통하여 구하고(밀도를 구하기 위해 간선의 갯수도 구하고), realComponent에 저장해주었다. 출력 조건을 맞추기 위해서 realComponent배열 앞에 밀도와 (컴퓨터의 수 * -1) 마지막으로 (컴포넌트에서 가장 작은 수* -1) 를 넣어주고 내림차순으로 정렬하여 realComponent[0]에 있는 값을 ..
