Stack알고리즘 문제 및 DFS 복습 및 react 컴포넌트 작성[TIL 2021.08.11]

7416 단어 알고리즘TILTIL

😊Today Learn

  • Stack관련 알고리즘 문제를 풀어봄
  • 깊이 우선탐색(DFS)에 대한 개념이 미흡하여 DFS문제를 풀어봄.
  • Tap컴포넌트를 react, Styled componnents를 이용하여 만들어봄.

미흡한 부분이나 배운점

- Stack관련 알고리즘 문제를 풀어봄

스택관련해서는 다 이해하고 있는 줄 알았지만, 막생 기초를 넘어선 문제를 풀어보니 처음엔 왜 스택을 이용해서 풀어야 하는지 이해하지 못하였음.. 여러 알고리즘 문제를 접하며 이부분은 익숙해져야 된다고 생각.

-깊이 우선탐색(DFS)에 대한 개념이 미흡하여 DFS문제를 풀어봄.

현재의 나는 재귀가 굉장히 약한데.. DFS가 재귀를 이용하여 탐색을 하는것이기 때문에
앞으로 있을 HA테스트를 대비하여 DFS와 재귀를 이해하고자 완전 기초문제부터 다시 풀어보고 있다.
짜여진 코드를 보면서 하나씩 이해하는것은 어느정도 가능하게 되었지만.. 아직 내가 해당 코드를 직접 짜는것은.. 조금 어려울것 같다.

DFS를 풀어보며 든 느낌은
옆은 신경안쓰고 앞만보고 달리다가 막다른 골목에 도착하면, 그제서야 자기가 길을 잘못 들어선 것을 인식하고 그제서야 옆을 보는 탐색 방법이구나 라는 생각이 들었다.(물론 앞만보고 달리다가 목적지를 찾으면 정말 좋지만 못찾으면 고생길이 훤하다)

DFS는 이동한 경로를 알수 있음. 왜냐면 앞만보고 가니까..
그대로 뒤돌아서 왓던길 가보면 되니까..

DFS를 풀게되면 기억해둘점

반드시 내가 한번 방문한 버텍스는 표시를 해두어서 중복되게 방문하지않는것과 스택이 터지지 않도록 하기.

DFS기초 예시

아래 함수 실행시 console.log에 찍히는 순서
1->2 ->7 -> 6 ->8 ->3 -> 4 ->5

function dfs(graph, v, visited) {
  // 현재 노드 방문
  visited[v] = true;
  // 방문 노드 출력
  console.log(v);

  // 인접 노드 탐색
  graph[v].forEach(i => {
    // 방문하지 않았다면
    if (!visited[i]) {
      // 재귀 호출
      dfs(graph, i, visited);
    }
  })
}

// 노드 연결 정보
const graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
];

// 방문 정보
const visited = new Array(graph.length).fill(false);

// 호출
dfs(graph, 1, visited);

좋은 웹페이지 즐겨찾기