['22 삼성전자 동계 대학생 S/W 알고리즘 특강] 사전 문제 풀이

 

원래는 '22. 1.10 13시 - '22. 1.12 13시 까지였는데 '22. 1.13 9시까지 연장되었다.

 

연장된 이유에 대한 세 가지 추측이 있다.

 

1. 푼 인원이 너무 적어서

 

2. 문제에 오류가 있어서

 

3. 13시에 서버가 안 닫혀서 형평성을 위해

 

아마 1번이 가장 유력하지 않을까 싶다.

 

 

문제를 처음 봤을 때 이제까지 풀던 문제들과 너무 달라 쉽게 적응하지 못했다.

 

분명 초급 S/W 알고리즘 역량을 보유하고 있는 사람들을 대상으로 진행하는 프로그램이라 했었는데 왜 이리 어렵지.

 

 

많은 시행착오와 여러 번의 삽질을 통해 세 문제를 다 풀 수 있었다.

 

다 풀고 나서 느낀 점은 일단 자료구조와 STL (C++를 사용했다면), 코드 설계에 대한 이해가 있어야 문제를 풀 수 있다는 점이었다.

 

일반적인 알고리즘 문제보다는 스케일이 크기 때문에 네이밍에도 신경을 써주는 것이 코드를 짜고 디버깅하는데 도움이 됐다.

 

 

 

1번. 시간여행자의 주식

 

map과 set, struct와 max, min을 어떻게 관리할 것인지에 대한 로직을 이용해 문제를 해결하였다.

 

 

 

2번. 가족 구성원 찾기

 

처음에는 map과 struct, pointer, reference, BFS를 이용하여 문제를 이용하려 했었다.

 

근데 시간 초과가 나서 BFS부분이 문제인가 하고 로직을 바꿨는데 또 시간 초과가 났다.

 

map을 unordered_map으로 바꾸고 이리저리 해봤었는데 계속해서 시간 초과가 나서,

 

결국엔 pointer와 reference의 사용을 줄이고 string을 int로 mapping해서 사용했더니 통과가 되었다.

 

 

 

3. Battle Ship

 

가장 작은 배가 1x2 크기니깐 격판을 격칸으로 검사해서 있으면 주위를 다 살피면 되겠다고 생각해 코드를 짰다.

 

근데 너무 많이 찾아서 통과하지 못했다.

 

그래서 생각해낸 아이디어가 조금 heuristic한 방법이었는데 배를 찾은 칸 주위에서 배가 있는 칸을 하나만 찾고 끝내는 것이었다.

 

그다음 찾아낸 배가 있는 칸을 세어 개수가 valid 한 지를 체크하고 그렇지 않다면 하나씩 더 찾아보는 방법을 사용했다.

 

로직이 너무 rough하여 이게 되겠나 싶었는데 다행히도 통과할 수 있었다.

 

 

 

확실히 이때까지 짜던 코드들과 달라서 많이 헤매었는데 그래도 덕분에 pointer와 reference의 올바른 사용이나 set sorting method, naming 등 많은 부분들에 대한 깨달음이 있었다.

 

한편으론 이게 초보자들을 대상으로 진행하는 알고리즘 특강의 사전 문제가 맞나 싶어 의구심이 들었다.

 

나만 어려웠나.

 

 

+ '22. 1.14.

0.5문제 정도 풀면 합격했다고 한다.