[Softeer] 지도 자동 구축(Lv.2) - Day4

📋 개요

2024.01.29 - [Algorithm/Problem] - [Softeer] 비밀메뉴2(Lv.3) - Day4

[Softeer] 비밀메뉴2(Lv.3) - Day4

 

4일차에는 DP문제로 구성해놓은거 같은 느낌이다. 4일차의 마지막 문제는 지도 자동 구축이다. 다이아몬드 스퀘어 알고리즘에 관련해서 나온거 같은데 추가적으로 궁금해서 찾아봤는데 문제에 포함되어있지 않는 더 딥한 내용이 있어서 흥미롭게 읽어보았다.

https://softeer.ai/practice/6280

Softeer - 현대자동차그룹 SW인재확보플랫폼

---

🧩 문제

현대자동차그룹이 레벨3 자율주행차 상용화 목표에 발맞춰 총력을 다하고 있는 가운데, 국내 최고 수준의 지도 구축 기술력을 보유한 현대엠엔소프트는 자율주행에 필요한 정밀지도를 제작해 배포하고, 기술 고도화를 위한 연구에 매진하고 있다.

최근에는 도로 데이터를 기반으로 자동으로 정밀지도를 구축하는 ‘지도 자동 구축(Map Auto Creation, 이하 MAC)’ 기술을 개발해 지도 제작 시간을 단축하고 정밀도를 향상시키는 데 성공했다.

 

자율주행차용 정밀 지도에 관한 궁금증으로 인터넷 검색을 해보니, Diamond-Square-Algorithm이라는 것을 찾게 되었다. 이 알고리즘은 정사각형을 이루는 점 4개를 고르고 그 후에는 다음과 같은 과정을 거쳐 모양이 만들어진다.

 

정사각형의 각 변의 중앙에 점을 하나 추가한다.

 

정사각형의 중심에 점을 하나 추가한다.

 

 

[그림]은 0단계(start)에서 2단계(2 iterations)까지 수행한 결과이다. 각 단계(N)가 계속해서 커져갈수록 점의 수가 커져간다.

⛔ 제약조건

1 ≤ N ≤ 15

📝  형식 

📥 입력	📤 출력
첫째 줄에 N이 주어진다.	첫째 줄에 N단계를 거친 점의 개수를 출력한다.

💡  예제

🔢 번호	📥 입력	📤 출력
1	1	9

🖥️ 내 코드

---

📖  해설 및 느낀점

점화식을 세워서 풀어야하는 dp유형중 하나이다. 아래의 그림과 표를 보면 점화식이 세워진다.

 

dp[i] = dp[i-1] + 2^i-1

 

위와 같은 수식이 나온다, 앞에꺼에서 단계 -1의 2제곱

 

사실상 귀찮은 문제지 문제를 풀고나면 규칙 찾기랑 다 찾고나면 쉬운문제이다.

dp는 사실상 점화식이 복잡하면 풀기 힘들수도 있는데 이번에 푼거는 점화식이 막 어렵지는 않았다. 

 

그리고 유의해야할점중 하나가 숫자가 매우 커진다는 점이다. 그래서 int형으로 선언하면 overflow가 발생한다. 그렇기 때문에 long long으로 선언하여 overflow를 방지해줘야한다.

 

4일차 문제도 잘 마쳤고 포스팅을 하면서 다시 복기도 진행했다...후!!

하루하루 공부할 시간이 있는것에 대해서 매우 감사하다!

 

https://en.wikipedia.org/wiki/Diamond-square_algorithm

Diamond-square algorithm - Wikipedia