[2020 KAKAO BLIND RECRUITMENT] 블록 이동하기(Java, 간단한 코드, DFS? or BFS?)
## 접근 1. DFS와 BFS 중 선택, DFS는 구현이 간단하지만 최소 시간을 구할 때는 적합하지 않다. 따라서, Depth(Time)을 확인할 수 있는 BFS를 선택. 2. 방문 표시를 통해서, 재탐색이 이루어지지 않도록 한다.(시간초과방지), 로봇 상태를 구분해서 방문 표시를 해야 하므로 3차원 배열을 사용해야 한다. 2차원 배열 시에, 수직과 수평의 구분이 없어지므로 주의한다. 3. 회전을 한다는 것을, 로봇의 아래, 위, 오른쪽, 왼쪽의 2칸이 모두 비어있어야 함을 의미한다. 코드에서 구현을 확인하도록 한다. ## 유의사항 1. 변수를 사용할 때, x1, y1, x2, y2는 지양한다. 문자에 숫자를 덧붙여 쓰다보니, 실수를 할 수 있다. ## 해설코드 1 2 3 4 5 6 7 8 9 10 1..
Trie(트라이) 자료구조 정의, 예제 코드
2020 신입 개발자 카카오 블라인드 시험을 치다가, 문자열 처리에 대한 자료구조를 알게 되었다. Trie 자료구조에 대한 다음과 같은 모습으로 생겼다. 위에 보면, APPLE, LABLE, CABLE이라는 단어를 넣은 것이다. 왜 굳이, Trie 자료구조를 사용해야 하는지를 생각해보자. 특정 문자열을 벡터에서 순차적으로 탐색하면, 최대 문자열의 갯수만큼 걸리게 된다. 하지만 Trie 자료구조를 사용하면, 문자열의 길이만큼의 탐색 시간이 걸린다. 즉, 많은 문자열속에서 특정한 문자열을 찾기 위해서는 Trie만한 자료구조가 없다. Trie 자료 구조를 사용하지 않으면, 카카오 블라인드 2020 기출문제 효율성을 통과할 수 없게끔 설계되어 있다. Trie 자료 구조를 몰랐을 때 사용했던 방법은, 문자열을 일..
