1090 문제 관련하여 맨해튼 거리 최솟값에 대해 질문 있습니다.
Q1) 2, 3, ..., N차원 맨해튼 거리에서 각 차원은 서로 독립적인게 맞나요?
ex) 2차원인 x, y에서 x의 맨해튼 거리의 최소값과 y축 거리의 최소값은 서로 독립적이라 전체 최소값은 결국 x 맨해튼 거리 최솟값인 x좌표, y 맨해튼 거리가 최솟값인 y 좌표
Q2) N+1개 이상의 N차원 맨해튼 거리의 최솟값은 항상 주어진 점 위에 존재하게 되는건가요?
ex) 점이 3개 혹은 4개가 주어진 2차원 맨해튼 거리 최소값은 무조건 주어진 점 위에 있는것인지?
Câu trả lời 2
0
안녕하세요, 인프런 AI 인턴입니다.
sjhh4님께서 질문하신 “1090 문제 관련하여 맨해튼 거리 최솟값”에 대해 기존 답변들과 관련된 내용을 찾아보았습니다. 아래의 설명은 맨해튼 거리의 특성과 관련된 내용입니다.
Q1) 차원 독립성에 관한 설명:
맨해튼 거리는 각 차원이 독립적으로 작용하는 특성을 가지고 있습니다. 주어진 좌표들이 N차원에 있을 때, 각 차원의 거리는 독립적으로 계산됩니다. 예를 들어, 2차원인 경우 x와 y에서 각각의 맨해튼 거리의 최소값을 구하고, 이를 더하여 전체 최소거리를 구할 수 있습니다. 이 접근 방식은 각 차원의 좌표가 독립적이라는 의미에서 맞습니다.
Q2) N차원 위에서 최솟값 존재 여부:
N차원 맨해튼 거리에서 각 차원 별로 독립적으로 최솟값을 계산하므로, 그 결과로 나온 최솟값의 좌표는 반드시 주어진 점들 중 하나와 동일할 필요는 없습니다. 하지만, 주어진 점에서 결정되는 좌표의 경우가 많은 상황에서 최적의 결과를 도출할 수 있기 때문에 다차원에서의 경우는 일반화된 경우로 보시면 좋습니다.
아래 링크는 강의 내 관련 부분을 참조하여 설명한 것입니다:
- 1090 완전탐색 - 각 차원에서의 독립적인 최솟값을 계산하는 방법과 관련된 이해를 도울 수 있는 예시를 설명합니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
dp[x]가 최대값이라고 확신할수 있는 이유
0
41
1
1090번 문제 질문
0
147
1
유니온파인드
0
111
1
투포인터 25:15 질문
1
126
1
#1090번 문제 반례가 궁금합니다.
0
145
1
예제코드 자바입니다
1
184
1
정수론 파트 #2247 문제에 대한 질문입니다!
0
99
0
코드 오류
0
184
1
2강 정수론 문제3 #1407 질문
0
123
0
이차원 배열 (int형)dp로 0 혹은 -1로 체크하는 방법 말고 boolean형 배열로 체크해서 바로 리턴해줄 수 없나요?
0
153
0
1717번 최적화
0
111
0
백준 22988 문제 질문
1
191
2
[Python] 백준 1090번 문제
1
223
3
강의자료에서
1
160
2
2503 문제 제한 조건 질문!
1
247
2
백준 22988 번 문제
1
190
1
추가 강의 순서
1
178
2
(*문제 풀이)1090 테스트케이스 1번 C++
1
219
2
7강 RGB 색칠하기 질문 있습니다.
1
159
2
정수론 약수 빠르게 구하기 질문
1
254
1
1090 문제의 2, 3번째 아이디어는 결국 같은거 아닌가요?
1
370
2
누적합 문제 3번 질문
1
213
2
기억 ( 누적합 ) 강의 11660 문제
1
160
2
14719
1
202
2