설모의 기록

이 문제는 주어진 NxM 배열에서 (0, 0) 에서 (N - 1, M - 1) 칸까지 가는 최소한의 칸의 수를 구하는 문제입니다. 문제에서는 (1, 1) 에서 (N, M) 으로 가는 최소한의 칸의 수를 구하라고 했지만, 인덱스의 개념상 (0, 0) 에서 (N - 1, M - 1) 로 가는 것이 이해하기 편해서 아래의 문제는 이것을 바탕으로 풀이한 알고리즘입니다. 이 문제는 BFS 문제입니다. 처음 (0, 0) 을 큐에 넣고 while 문 안에서 큐에 있는 노드들의 다음 목적지를 다시 큐에 넣고 반복하면 됩니다. 코드는 아래와 같습니다.

바둑과 체스같은 게임에서는 상대방이 다음에 어떤 자리에 수를 놓을것인가 까지 생각을 하며 게임을 진행해야 합니다. 이런 게임에 인공지능을 투입한다면, 이 인공지능도 사람이 어디에 놓게 될것인가를 생각하도록 코드를 구현해야 합니다. 이 때 사용하는 알고리즘이 바로 최소최대 알고리즘입니다. 최소최대 알고리즘 (Minmax Algorithm)바둑과 체스같은 게임에서는 상대방은 내가 제일 불리한 곳에 수를 두게 될 것입니다. 그래서 내 차례에는 내게 제일 유리한 수, 상대방 차례에는 내게 제일 불리한 수가 선택될 것이며, 단지 다음 턴만이 아니라 그 이후의 수까지도 바라보며 탐색을 해가는 과정입니다. 정리하자면, 최대와 최소를 번갈아가며 선택해 가장 좋은 경우를 선택하는 것이 최소최대 알고리즘의 답이 됩니다. ..

탐색 알고리즘에는 여러가지가 있습니다. 가장 기본적인 알고리즘이 BFS 와 DFS 인데요. 각각 아래에서 살펴보겠습니다. BFS(Breath First Search) BFS 는 너비우선탐색 알고리즘입니다. 위의 트리는 깊이(depth)가 2인 이진트리입니다. BFS는 루트부터 시작해서 깊이별로 가로방향을 먼저 탐색해나가는 방식입니다. 따라서 1단계에 있는 a를 먼저 탐색하고, 2단계에 있는 b,c 를 탐색하고, 마지막으로 3단계에 있는 d,e,f,g 를 탐색하는 방식입니다. 장점너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장합니다.최단경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단경로를 반드시 찾을 수 있습니다.노드의 수가 적고 깊이가 얕은 해가 존재..

최단 경로 탐색 알고리즘 최단 경로를 탐색하는 알고리즘의 종류는 여러가지가 존재합니다. 그 종류 중 하나인 a* 알고리즘에 대해 알아보겠습니다. a* 알고리즘은 bfs 알고리즘의 한 예로, 휴리스틱(h) 값을 이용해 최단 경로를 추정해나가는 방식입니다. 아래의 설명을 보시면 아시겠지만 휴리스틱 값이 0이라고 생각하면 결국 최단 경로가 되는데요. 휴리스틱 값이 0 이라면 bfs 와 똑같은 알고리즘이 됩니다. 따라서, 이 알고리즘은 결국 bfs 알고리즘이 최단 경로를 발견한다는 것을 다시 입증해주는 예시입니다. 개념과 예시는 아래에서 설명하도록 하겠습니다. A* 알고리즘? 한 지점에서 목표 지점으로 가는 방법 중 가장 짧은 길을 찾는 것을 최단 경로 탐색이라 하며, 지점을 노드라고 표현합니다. a* 알고리즘..

vue router 는 url 경로마다 띄워줄 component 들을 설정하는 것입니다. vue-router 를 이용하면 SPA(Single Page Application) 을 구현할 때 마치 여러 페이지를 구현한 것 같은 효과를 낼 수 있습니다. 참고로 vue router 의 기본 경로는 '기본_도메인/#/' 입니다. 기본 경로에 #을 없애고 싶으시다면 router 의 mode 를 history 로 설정하시면 됩니다. 이제 기본적인 사용법에 대해 알아볼까요? Vue router 사용법1. 모듈설치우선 모듈부터 설치해야겠죠? 아래의 명령어를 이용해 vue-router 모듈을 설치해주세요.$npm i vue-router --save // --save 는 package.json 에 자동으로 추가되도록 하기 ..