프론트엔드 개발자의 기록 공간

백준 DFS 알고리즘 4963번_섬의 개수 난이도 : 실버II 문제 설명 입출력 문제 풀이 : 1012_유기농 배추부분이랑 로직은 일치한다. 관련된 로직은 (ghost4551.tistory.com/27) 여기에 상세하게 설명해뒀으니 참고하면 좋을것같다. 한번더 설명하자면 DFS를 활용하여 연결된 요소를 방문처리하고 연결된 집합의 개수를 출력해주면 된다. 여기서 고려해야될게 방문처리는 그래프의 값을 0으로 초기화 시켜 해결할 수 있다. 또한 대각선 이동도 유의해야한다. //실버2 섬의 개수 const solution = () => { //별 섬의 개수 let cnt = 0; //가로 세로 배열 높이 구하기 [w, h] = input .shift() .split(" ") .map((el) => Number(..

백준 DFS 알고리즘 1012번_유기농 배추 난이도 : 실버II 문제 설명 입출력 문제 풀이 : 이 문제는 백준 11724번 연결 요소의 개수 문제와 유사하다. 참고할것(ghost4551.tistory.com/26) 연결 요소 찾기와 유사하게 로직을 작성하되 몇가지만 고려해주면된다. 1. 배추가 위치한 곳은 1이된다. 한번 방문했다면 해당노드를 0의 값으로 만들어준다. (방문처리) 2. 상하좌우 옮겨갈수 있으므로 옮겨주되 그래프의 범위인지 검사 크게 이렇게 두가지만 고려해주면 된다. function solution() { let cnt = 0; //그래프 전체 탐색 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { //그래프의 값을 돌면서 1이 존..

백준 DFS 알고리즘 11724번_연결 요소의 개수 난이도 : 실버II 문제 설명 입출력 문제 풀이 : 이 문제 또한 전형적인 DFS 문제이다. 또한 문제 제목처럼 연결된 정점들의 묶음의 수를 출력하면된다. 기존에는 한번만 DFS함수를 호출하면 재귀적으로 돌면서 인접 노드들을 알아낼 수 있다. 그렇게 되면 한번의 호출만으로 i(시작노드)와 인접한 모든 노드들은 방문 처리가 된다. 이를 이용하여 반복문을 통해서 graph의 길이만큼 DFS함수를 호출한다. 하지만 처리된 노드들은 방문처리가 되었기 때문에 방문되지않은 노드가 있을때만 DFS함수를 호출하고 연결요소를 카운트 해주면된다. //실버2 연결 요소의 개수 //DFS 기본 로직과 동일 function DFS(v) { visited[v] = true; f..

백준 DFS 알고리즘 1260번_DFS와 BFS 난이도 : 실버II * DFS와 BFS 두개 다 요구하는 문제입니다. 문제 설명 입출력 문제 풀이 : 문제 제목부터 DFS와 BFS를 요구하는 문제이다. 기본 DFS와 BFS 구현 알고리즘을 이용해서 해결하면된다. 인접행렬 방식으로 풀어줘야한다는 것만 알고 풀면된다! //실버2 DFS와 BFS //DFS함수 function DFS(v) { //노드 방문처리 visited[v] = true; //출력을 위해 리스트에 노드 삽입 DFS_graph.push(v); for (let i = 1; i < graph.length; i++) { //graph에 1이 있고 방문하지 않았다면 재귀 호출 if (graph[v][i] === 1 && visited[i] === ..

백준 DFS 알고리즘 2599번_짝 정하기 난이도 : 실버IV 해결하지 못한 문제입니다. 문제 설명 입출력 문제 풀이 : 초등학교 출신을 순서대로 배열의 index값으로 생각하고 이차원 배열에 각각 학교별로 남자, 여자의 수를 입력 받는다. 그후 list(초등학교)를 순서대로 돌면서 자기학교를 제외한 여학생들의 수와 비교해서 쌍을 맺을수 있는대로 맺어준다. 맺은 쌍 만큼 남학생, 여학생 수를 빼주고 맺은 쌍의 수를 배열에 넣어준다. 이 과정을 마치고나면 list(초등학교)에는 맺을 수 있는 쌍을 제외한 값이 존재한다(모두 쌍을 맺었다면 모든 배열에 0 그렇지 않다면 0을 제외한 수가 남게 된다.) 그후 모든 list(초등학교)에 0만 존재한다면 모든 쌍이 맺어진것이므로 학교의 수만큼 짤라서 맺어진 쌍을 ..

백준 DFS알고리즘 2606번_바이러스 난이도 : 실버 III 문제 설명 입출력 문제 풀이 : 이 문제는 DFS 알고리즘의 대표적인 문제이다. 인접행렬을 통해 연결된 노드의 개수를 구하는 문제이다. 입력으로 주어지는 쌍을 해당 값에 맞는 인덱스에 1을 대입하여 연결된 노드가 있음을 알려준다. 그 후, 방문처리를 위해 배열을 초기화 해주고 인덱스 1부터 dfs함수를 실행시켜 dfs기능을 실행해주면된다. 자세한 설명은 코드에 주석으로 달아놨습니다. 재귀풀이 //실버3 바이러스 function solution(n, graph) { //방문노드 초기화 visited = new Array(n + 1).fill(false); //노드 1로 dfs시작 dfs(n, 1); //dfs의 재귀가 끝난후 로직 let cnt..

백준 그리디 알고리즘 1339번_단어 수학 난이도 : 골드IV 문제 설명 입출력 문제 풀이 : 단어가 주어졌을때 해당 단어에 9부터 차례로 대입해서 최대값을 출력하면된다. ex )'GCFG' G:9, C:8 F:7(중복이면 큰값으로 설정) 개발로직 1. 단어의 길이에 따라 10의 거듭제곱으로 나타내준다. 'GCFG' G:1000, C:100, F:10 G:1 G는 중복되니깐 G: 1001, 나머지 그대로가 된다. 2. 이후 큰 값부터 정렬을한 뒤 9부터 대입해주면된다. 'GCFG' G(1001 * 9) + C(100 * 8) + F(10 * 7) = 9879 function solution(n, list) { let tmp = 0; //객체에서 value 의미 //여기서 각각의 단어는 key가되고 해당자..