3번째 강의는 그리디, 완전 탐색, DP에 관한 내용이었다. 대부분은 친숙한 내용이었지만 visited를 비트 마스킹으로 배열이 아닌 int로 사용한다는 것이 신기했다. 이러한 비트 연산을 통해 재귀와 DP를 같이 사용할 때에도 [N][1<<N]과 같은 방식으로 DP 배열을 선언한다면 쉽게 정보를 저장할 수 있다는 것을 알게 되었다.
이것에 영감을 얻어 문제에서 bool 배열 대신 int visited를 사용하려 했으나 int가 32비트라는 것을 간과했다. 비트 연산을 1<<200을 하는 것도 시간이 꽤 걸리는지 똑같은 코드에 bool vis[]를 사용할 때에는 6ms가 걸리지만 int 를 사용하여 비트 연산을 할 때에는 1초가 넘어가 시간초과가 떴다. 하지만 그래도 int 를 사용하는 비트마스킹에 조금 더 익숙해졌다는것으로 만족해야겠다.
이외에도 P NP NP-Hard NP-Complete에 관한 내용도 배웠다. 학기 중 알고리즘 시간도 배웠는데 내용을 어렴풋하게 알 것 같은데 이것이 무슨 의미를 갖는지는 아직 잘 모르겠다. 아마 이해를 잘하지 못하였기 때문이지 않을까 싶다. 다음에 블로그에 NP에 관해 공부한 것을 정리해서 올려야 되겠다!
'코딩 > 삼성 알고리즘 특강' 카테고리의 다른 글
| [SWEA] 5. 그래프 탐색 (0) | 2022.01.25 |
|---|---|
| [SWEA] 4. 분할정복 (3) | 2022.01.21 |
| [SWEA] 2. 링크드 리스트 (0) | 2022.01.18 |
| [SWEA] 오리엔테이션 후기 + 1. 비트 연산 (0) | 2022.01.18 |
| [삼성전자 DX 부문 동계 대학생 S/W 알고리즘 역량 강화 특강] (0) | 2022.01.17 |