35일차 TIL 210421

1. TOY문제 인트로

  • 알고리즘 문제를 꾸준히 시도한다는 것에 의의를 둔다…라…
  • 9시보다는 좀더 빨리 시작해서 문제 분석하고 블로깅도 해야겠다.

2. 위클리 리플렉션

  • 우리 조는 상당히 재밌고 다양한 경험을 가지고 계신 분들이 많다. 다들 실제로 만나게 될 날이 기대가 된다. ( 내가 그전에 녹아버리지 않는다면 )
  • 다음주부터는 서버에 대해 배우게 된다고 한다. 스프린트 이름만 들어도 벌써 머리가 아프다.
  • 리액트 예습을 해놓고 싶었는데 유어클래스 서버 부분 내용을 먼저 봐야 할 것 같다.
  • 코스 진행에 대하여 약간의 힌트를 얻었다. 여태 진행 했던 스프린트들( 그리고 앞으로 진행할 스프린트 들도 ) 약간 기본적인 틀은 잡힌채로 처음 시작하는 경우가 많다.
  • 아예 전체를 다 지우고 처음부터 구축을 해보라는 팁을 받았다. 주말에 혼자서 해봐야지!
  • 그리고 toy 문제의 레퍼런스는 따로 간직해 두는 것이 좋다고 한다. one Note에 따로 저장해 두어야겠다.

3. 멘탈 나가서 하지 못했던 코플릿 문제 분석

<문제 : 방향이 있는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.
입력 : 인자 edges :2차원 배열, 시작과 도착 정점이 담겨있는 배열들을 담고 있는 목록
출력 : 숫자 타입을 리턴해야 한다. 연결된 정점의 컴포넌트 수를 숫자로 반환한다.
주의사항 : 주어진 간선은 무향이다.
입출력 예시 :
const result = connectedVertices([
	[0, 1],
	[2, 3],
	[4, 5],
]);
console.log(result); // 3

내가 생각한 문제 해결 방식:

  1. 가장 큰 수를 구해서 그 크기만큼 인접리스트를 만든다.
  2. 입력받은 edges 에 방향이 없으니 양방향 모두 1로 바꾼다.
  3. 리스트 를 순회하면서, 연결되어있는것을 찾아나선다. 근데 그룹을 찾아서 count++ 를 하는데, 그룹에 연결된 다른 요소를 방문해서 또 count++ 이 되면 안되니까, isVisited 를 써서 연결되어있는걸 찾아서 visited = true 로 바꿔준다.
  4. isVisited 는 max - min 의 길이를 가진 배열이다.


function connectedVertices(edges) {
	// 최대 버텍스를 찾습니다.
	const maxVertex = edges.reduce((a, c) => {
		const bigger = Math.max(...c);
		if (bigger > a) return bigger;
		return a;
	}, 0);

	//  비어있는 인접 리스트 생성
	const adjList = {};

//최대 버텍스 만큼 adjList안에 버텍스 추가하기
	for (let i = 0; i <= maxVertex; i++) {
		adjList[i] = [];
	}
//주어진 edges 길이만큼 순회하면서 adjList 의 요소인 버텍스에 인접 리스트 추가하기.
//무향이기 때문에 양방향 다 만들어 준다.

	for (let i = 0; i < edges.length; i++) {
		adjList[edges[i][0]].push(edges[i][1]);
		adjList[edges[i][1]].push(edges[i][0]);
	}

// 컴포넌트 갯수를 세어야 하는데 중복되어서 세면 안되겠다.
// 때문에 해당 컴포넌트를 세었는지 확인하기 위한 visited 객체 선언
// 컴포넌트 갯수를 세기위한 count변수 선언.
	const visited = {};
	let count = 0;

 // 0부터  maxVertex까지 순회한다.
	for (let vertex = 0; vertex <= maxVertex; vertex++) {
  // 해당 버텍스에 방문하지 않았다면,
		if (!visited[vertex]) {
    //bfs함수를 실행한다. 인자는 adjList, vertex,visited를 넘긴다.
    //bfs로 갈 수 있는 모든 정점을 방문하여 visitied를 담는다. 방문한 버텍스는 visitied에 들어있어서 bfs를 돌지 않는다.
			bfs(adjList, vertex, visited);
      //count를 1 올려준다.
			count++;
		}
	}
  //최종 할고싶은 컴포넌트 갯수를 출력한다.
	return count;
}


function bfs(adjList, vertex, visited) {

	//queue라는 변수에 [vertex]할당
	const queue = [vertex];
  // 방문해서 count올려줬으므로 visited 에 발도장 찍는다.
	visited[vertex] = true;

 //queue의 길이가 0보다 클경우 while문은 실행된다.
	while (queue.length > 0) {
  //cur 라는 변수에 queue의 맨앞 값일 뺀 것을 할당한다.
		const cur = queue.shift();
  		// 만약, 해당 버텍스를 방문하지 않았다면 queue에 삽입합니다.
			// 방문했다는 표시로 visited에 해당 버텍스를 삽입하고 true를 할당합니다.
		for (let i = 0; i < adjList[cur].length; i++) {
			if (!visited[adjList[cur][i]]) {
				queue.push(adjList[cur][i]);
				visited[adjList[cur][i]] = true;
			}
		}
	}
}

4. BFS란, breathed first search의 약자이다.

  • 가까운 정점부터 탐색한다. 그리고 더는 탐색할 정점이 없을떄, 그다음 떨어져있는 정점을 순회한다.
  • 너비를 우선적으로 탐색하는 방법, 너비 우선 탐색. 주로 두 정점 사이의 최단 경로를 찾고 싶을 떄 사용한다.

Updated: