본문 바로가기

알고리즘119

MST 최소비용신장트리, Union find 개념과 JS코드 신장트리란 모든 노드가 연결되있고 사이클이 없는 그래프이다. n개의 노드를 n-1개의 선으로 연결한다. 그래프의 최소연결 그래프이다 보통 네트워크 구축에 많이 사용된다 최소비용신장트리란 MST (Minimum Spanning Tree) 간 선에 비용을 붙여 최소의 비용이 드는 신장트리다 조건은 비용 최소 반드시 n-1개의 선만 사용 사이클이 없다 MST를 구하는데 주로 크루스칼, 프림알고리즘이 사용된다 먼저 크루스칼 알고리즘의 베이스인 union find를 알아보자. Union-Find란 여러개의 노드가 존재할 때 선택한 두 개의 노드가 같은 그래프에 있는지를 판별하는 알고리즘이다. 먼저 기본적으로 자기자신을 부모로 가지는 배열을 만들고 서로 다른 부모를 합칠 때 더 작은 쪽으로 합친다. 3과 1이 연결.. 2023. 9. 25.
[dfs, union find] 네트워크 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 첫 풀이 처음에 단순히 섬의 개수를 구하는 문제와 비슷하다고 생각해서 땅을 찾으면 땅을 파고들어갔는데 문제를 잘 못 이해한거 였다 function solution(n, computers) { var answer = 0; const direction = [ [-1, 0], [0, 1], [1, 0], [0, -1], ]; function dfs(r, c) { for (const [dx, dy] of.. 2023. 9. 25.
색종이 만들기 (dfs) https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 여러줄 입력 split('\n') map(e => Number(e)) === map(Number) 0항 0열부터 돌면서 isUnion을 검사한다 isUnion이거나 더이상 자를 수 없는 조각이면 왼쪽상단모서리가 1일떈 blue++, 0일땐 white++ !isUnion이면 한 변이 n/2크기로 잘라서 다시 isUnion검사를 한다 const input = require(.. 2023. 9. 23.
[그리디] 체육복 https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=javascript# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 function solution(n, lost, reserve) { var answer = 0; for (let i = 1; i r !== i); } // 왼쪽 사람이 여분있음 else if (reserve.includes(i-1)) { // 여분있는사람이 도난당함 if (lost.includes(i-1)) { continue; } else { answe.. 2023. 9. 20.
[DP] N으로 표현 https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 로직 수를 만들어내는 방법 사칙연산 (+, -, *, /)와 숫자를 붙여서 만드는 방법 i+1길이의 배열을 만들어 i번째에 N을 i개 사용하여 만들 수 있는 모든 수를 추가한다. 문자열.repeat(n번) 먼저 i 번쨰 set에 숫자N을 i번 붙여만든 수를 추가한다 (5, 55, 555, 5555....) = i는 N을 사용한 갯수이다 2개의 N으로 만들 수 있.. 2023. 9. 3.
[DP] 등굣길 https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나.. 2023. 9. 1.

티스토리툴바