algorithm

플로이드 와샬(Floyd Warshall) 알고리즘

플로이드 와샬 알고리즘 모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 문제들이 있다. 이 경우 플로이드 와샬 알고리즘을 사용하면 쉽게 모든 정점의 최단 거리를 구할 수 있다. 플로이드 와샬을 기본적으로 DP를 기반으로 진행된다. 플로이드 와샬 알고리즘의 주요 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다. 위 와 같은 그래프가 존재한다고 가정하자.이 때 각 정점에서 다른 정점으로 가는 비용을 이차원 배열로 정리하면 아래와 같다. 해당 테이블이 의미하는 바는 '현재까지의 최단 거리'이다. 해당 테이블을 통해 지나치는 정점으로 다른 정점으로 가는 테이블을 그릴 것이다. 1. 노드 1을 거쳐가는 경우 노드 1을 거쳐가는 경우는 노드 2와 노드 3이다. 이를 테이블로 나타내면 아래와 같다..

[프로그래머스 / Javascript] 당구 연습

문제 https://school.programmers.co.kr/learn/courses/30/lessons/169198 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 하나의 공(startX, startY)를 가지고 주어진 공들(balls)들을 원 쿠션으로 맞추는 방법 중 가장 짧은 케이스의 길이의 제곱을 구하는 문제이다. 이 문제는 시작하는 공에서 벽, 벽에서 맞추어야 하는 공까지의 거리를 구하여 더할 수도 있지만, 간단하게 벽을 기준으로 하나의 공을 반전시켜 해당 공과의 거리를 구하면 이동 거리를 쉽게 구할 수 있다. 위 과정을..

[프로그래머스 / Javascript] 전력망을 둘로 나누기

문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 송전탑의 연결 상태를 파악한 후 모든 전선을 한번씩 잘라보며 각 전원의 송전탑의 수의 차이를 구하는 문제이다. 문제를 풀 때 송전탑의 연결을 송전탑의 오브젝트에 넣어두어 연결 상태를 확보한 후 끊긴 이 후 송전탑의 수를 구했다. 글보다 코드를 보면 이해가 쉬울 것 같다. function countLink (link,start) { let answer = 0; const..

소수(Prime number) 판별법/ javaScript

소수 (Prime number) 판별법 소수란 1, -1과 자기 자신, 자기 자신의 반수로 밖에 나누어 떨어지지 않는 1 이외의 정수, 즉 양의 약수가 2개인 자연수를 의미한다. 소수는 다양한 알고리즘 문제에 자주 등장하는 개념이다. 그러므로 소수를 판별하는 법을 알아두고, 효율적인 방법을 기억해두는 것이 좋다. 1. 3부터 자기 자신까지 비교 첫 번째 방법은 말 그대로 3부터 자기 자신까지 모든 수를 숫자에 나누어보아 약수 여부를 판단하는 것이다. 아래 코드를 보자 const isPrime = ( num ) => { if(num < 2) return false;// 0과 1은 소수가 아니다. if(num === 2) return true;// 2는 유일한 짝수인 소수이다. if(num % 2 === 0..

[프로그래머스 / C++] 이모티콘 할인행사

문제 문제 길이가 길어 문제는 링크로 확인 부탁드립니다. https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 조건에 부합하는 최적의 이모티콘 각 할인률을 구하는 문제이다. 문제에서 중요한 조건은 아래와 같다. 1. 1번 목표가 우선이며, 2번 목표가 그 다음입니다. 2. 1 ≤ emoticons의 길이 = m ≤ 7 , 할인율은 10%, 20%, 30%, 40% 중 하나로 설정 1번 조건은 이모티콘 판매 가격이 아무리 높더..

[프로그래머스 / C++] 롤케이크 자르기

문제 https://school.programmers.co.kr/learn/courses/30/lessons/132265 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 같은 토핑 가짓수로 나눌 수 있는 방법의 수를 반환하는 문제이다. 그렇기 때문에 모든 케이스를 확인해볼 필요가 있었다. 이때 모든 자르는 방법 마다 양쪽의 토핑 수를 카운트하면 시간 초과가 날 것 같았다. -> 시간 복잡도는 n^n이므로 최대 100000^100000이다. 그렇기에 초기 값을 구한 후 순서대로 올라가며 계산된 map에서 right -> left으로 값..