혼종 꼬지마루
삼성전자 수시 역량테스트 B형을 준비하기 위해서 필요한 reference code를 직접 구현하면서 정리를 해보는 중 어짜피 queue나 stack은 딱히 구현할 연습은 없어보임....원래 stl을 안썻으니.... 하지만 map이나 sort는 해본적이 없고, 우선순위 queue같은 것도 미리 구현을 해보면 좋을 것 같다는 생각이 들었다. 그 중에 이 글은 map을 대체로 사용할 수 있는 hash를 구현해 보았다. 여기서 가장 중요하게 기억해야 할 것은 5381이라는 골든 넘버! hash를 구현하다 보면 다른 key값이지만, 이미 할당된 index를 참조하는 경우가 있다. 이런 index 충돌이 일어나게 되는 것이 최소화시키는 것이 5381이라고 한다. 자세한 것은 아래의 코드를 보면서 참조하면 될 것 같..
삼성전자 상시테스트 문제와 상당히 유사하다고 해서 풀어보았는데..... 돌리는게 귀찮은 문제라고 결론을 내려본다 단순히 dfs로 돌리는 순서를 정해주면서, 최소값을 찾는 배열을 만들어 주느냐가 관건이다 항상 말하지만 나는 stl을 안쓰고 짜는 것을 선호하지만, 이 문제는 색종이 붙이기와 같이 dfs함수가 return되었을 때 map이 그 depth에서 만든 map으로 원복되는 것을 원하기 때문에 vector를 선언해서 사용했다 1. map을 선언하고, map을 rotation시키는 좌표를 입력받는다 2. dfs로 전체 탐색 하면서, 순서를 저장하는 것이 아닌, 그때마다 돌려준다.- 저장했다 한번에 돌려줘도 되지만, 비효율적이라고 생각이 들었기 때문 3. depth가 K에 이르면, 문제의 조건에 따른 각 ..
이것 또한 삼성전자 기출이라고 한다 그냥 BFS라고 생각해서 풀었다가 예외처리를 겁나 해준..... dfs와 함께 섞어서 사용하지만, 메인은 bfs라서 bfs에 올림 최적화나 코드 정리따위는 하고 싶지않아서 그냥 간단하게 코드정리만 하고 포스팅 1. 언제나 그렇든 map을 입력을 받는다- 입력을 받으며 바이러스는 따로 구조체배열에 저장하고, 벽과 바이러스가 없는 구간의 공간을 count해준다 2. dfs를 돌면서 virus를 M개만큼 선택하며 큐에 담아준다 3. bfs에 들어가면, 큐에 담긴 K개의 좌표를 visit배열에 표기하고, st값을 올려주면서 virus(순회한 virus로 정의했음)의 갯수를 올림 4. bfs를 돌면서 조건에 맞게 단순 bfs를 돌지만, virus가 있는 공간을 지날때, map[..