Leo.K | To become a cooler Developer

최근에 네이버 공채를 지원해보고, 코딩테스트를 보았다. 나름 준수하게 푼 것 같긴 한데, 생각보다 애먹었던 내용과 비슷했던 문제를 다시 풀어보고자 한다. 너비우선탐색을 진행하는데, 실제탐색은 2차원 배열로 진행하지만, 각 요소가 익숙했던 정사각형이 아닌 정육각형으로 이질감이 있게 생겼다. 물론 이에 따라서 이동가능한 경우의 수도 (상, 하, 좌, 우) 4가지에서 (좌, 좌상, 좌하, 우, 우상, 우하)6가지로 바뀌었다는 점, 더불어 현재 행이 짝수인지, 홀수인지에 따라서 이동하는 위치가 다르다는 것이다. 말로만 설명하면 어려우니 간단한 예시를 보자. 문제에서 예시로 주어진 그림을 보면 척 봐도 모든게 복잡하다. 일단 그림부터도 불편하긴 한데, 행과 열이 거꾸로 되어 있기까지 하다니,,, 하지만 이는 모양..

용어 설명 그래프(Graph) 노드와 간선을 하나로 모아 놓은 자료 구조 정점(Vertex) 노드라고도 하며, 정점에는 데이터가 저장된다. 간선(Edge) 링크라고도 하며, 노드간의 관계를 나타낸다. 인접 정점 (adjacent vertex) 간선에 의해 직접 연결된 정점 차수(degree) 무방향 그래프에서 하나의 정점에 인접한 정점의 수. 무방향 그래프에 존재하는 존재하는 정점의 모든 차수의 합 == 그래프의 간선의 수 * 2 진출 차수 (out-degree) 방향 그래프에서 사용되는 용어로, 현재 노드에서 외부로 향하는 간선의 수 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 == 방향 그래프의 간선의 수 진입 차수 (in-degree) 방향 그래프에서 사용되는 용어로, 외부 노드에서 ..

오늘은 알고리즘 스터디원들과 문제풀이를 하는 도중 다들 이 문제를 어려워 하길래 정리할 겸 풀어보았다. 필자는 별 다른 문제를 못느끼고 문제를 풀었는데, 아무리 해도 안된다는 스터디원들의 말을 듣고, 다른 풀이를 인터넷에 검색해보았다. 한 가지 다른 점이 있다면 인터넷과 팀원들의 풀이는 입력값에 반대 방향으로 그래프를 그렸고, 필자는 입력값 방향 그대로 그래프를 구성했다. 문제를 보면 그래프가 방향성이 없는 무방향 그래프가 아니라 방향성이 있는 단방향 그래프라는 것은 눈치챘을 것이다. 사실 필자도 구글링을 해보면서 찾아보았지만 시간 초과가 나는 정확한 이유를 모르겠다... 예상가는 바라고 한다면, 1만개의 정점이 10만개의 간선으로 모두 연결이 되어 있는 상태라면, 모든 노드를 탐색해야 하는 이번 문제에..