오늘도 맑음

목차1. 문제 풀이2. 정답 코드3. 시간 복잡도1. 문제 풀이외판원이 모든 도시를 한번씩 거쳐 마지막에 다시 출발 도시로 돌아오는 데 걸리는 최소 비용을 구하는 문제이다. 4개의 도시에 대하여, i -> j 로 이동할 때 걸리는 비용이 2차원 배열로 주어진다.이 때, 기본적인 dfs 코드와는 다르게 '비용'이 있으므로, 방문할 때마다 비용을 더해줘야 한다.또한 여러 케이스의 경로에 대하여 '총 비용'을 비교하여 최소 비용을 출력해야하므로, 모든 경로를 탐색하기 위해 백트래킹 개념을 사용하였다. 백트래킹은 쉽게 말하자면, 순열과 같다.'A' , 'B', 'C', 'D' 가 있을 때, ABCD, ABDC, ACBD, ACDB, .... 순으로 진행되는데, 이를 구현하기 위해 1. 한 가지 선택지를 택함2...

목차1. 문제 풀이2. 내가 푼 정답 (shift 연산 사용)3. 개선한 풀이 (큐 직접 구현)1. 문제 풀이2차원 평면에서 출발지점과 목적지점이 주어질 때, 장애물(0)을 이동하는 데 걸리는 최단 거리를 구하는 문제이므로, bfs로 해결할 수 있었다.다만, 시간 복잡도를 줄이는 데에서 애를 먹었다. 시간 복잡도제한 조건에서 알다시피 maps의 row, col은 최대 100이다. 따라서 row, col을 둘 다 N 이라고 하겠다.이 때, 시간 복잡도는 다음과 같다.시간 복잡도- 모든 칸을 순회 : O(N^2)- shift 연산 : O(N^2)👉 O(N^4) 최악의 경우 N 👉 O(10^8) 여기서 문제였던 부분이 1초당 10^8 연산을 할 수 있는데, 그럼 간당간당하게 되거나 안되거나 하겠다. 라는 ..

목차1. 문제 풀이  1) 테두리 구하기  2) 테두리 이동할 때, 풀이법 (❌ 주의: 칸 이동과 다름)2. 전체 코드3. 느낀 점1. 문제 풀이그림과 같이 여러 다각형이 배열 형태로 주어질 때, 테두리 정보를 배열에 저장해두어야 한다.출발지 (x, y) 에서 목적지 (x, y) 에 도달할 때까지 걸리는 가장 짧은 거리를 계산하기 위해서는 bfs 코드를 수행한다. 직사각형 입력 형식직사각형 배열은 [fromX, fromY, toX, toY] 로 주어지며, 각각 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점 정보이다.예를 들어, 가장 아래의 직사각형은 [1,1,7,4] 로 주어진다. 처음 생각한 방식처음에 생각한 방식은 직사각형이 주어질 때, 모든 선분을 1로 만드는 것이였다.그리고 1과 0(초기화) 경계에 있는 ..