[백준/JS] 10775 공항

문제 접근 문제링크: https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 유니온 파인드 문제이다. 알고 풀었는데도 못풀었다. 문제에 그리디가 섞여있는데 그리디 적인 발상을 하지 못했다. 비행기를 해당되는 게이트에 우선적으로 넣고 그 게이트가 차있다면 -1 인 게이트에 넣는다. 라는 그리디적인 발상말이다. 엌엌 🥹 문제 풀이 1. Find 한 비행기의 Root 가 0 이면 break 아니라면 2번을 수행한다. 2. ..

[백준/JS] 4195 친구 네트워크

문제링크: https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 유니온 파인드 문제이다. 문제 종류를 알고 풀었는데도 쉽지 않아 해설을 보았다. 1. parent 배열과 relation 배열을 선언한다. 1-1. parent 배열은 기존의 유니온 파인드 방식처럼, 배열[index] = index 로 초기화한다. 1-2. relation 배열은 유니온 될때 서로의 친구관계의 수를 합하기 위해 선언된다. 모두 1로 초기화한다. 1-3. 배열의..

[백준/JS] 런타임 에러 (EACCES)

문제 상황 백준 1717번 문제를 풀고 있었다. 로직을 다 짜고 제출했는데 런타임 에러를 만나게 되었다. 문제 원인 입력에 관한 오류였다. fs 모듈을 사용하고 있는데, JS 같은 경우 간간히 fs 모듈로는 입력을 다 받을 수 없는 경우가 존재하는 것 같다. const fs = require("fs"); BOJkey = false; const input = fs .readFileSync(BOJkey ? "./ehddud1006/BOJ/1717/input.txt" : "./dev/stdin") .toString() .trim() .split("\n") .map((item) => item.split(" ").map(Number)) .reverse(); 해결 방법 JS 로 백준 문제를 풀때 사용할 수 있는 입..

[바킹독 강의] 플로이드 와샬

https://blog.encrypted.gg/1035 [실전 알고리즘] 0x1C강 - 플로이드 알고리즘 안녕하세요, 이번에는 플로이드 알고리즘을 다루겠습니다. 이제 최단경로 알고리즘인 플로이드, 다익스트라 알고리즘만 다루고 나면 나름 길었던 그래프 파트가 끝납니다. 목차는 눈으로 한 번 blog.encrypted.gg 위 강의자료를 보며 생각해본점들을 기록합니다. 위 코드를 자바스크립트 코드로 바꾸면 아래와 같다. const fs = require("fs"); BOJkey = false; const input = fs .readFileSync(BOJkey ? "./ehddud1006/BOJ/11404/input.txt" : "./dev/stdin") .toString() .trim() .split("\..

[바킹독 강의] 다익스트라

https://blog.encrypted.gg/1037 [실전 알고리즘] 0x1D강 - 다익스트라 알고리즘 네 반갑습니다. 이번에는 다익스트라 알고리즘을 해보겠습니다. 플로이드 알고리즘이랑 비슷하게 구현과 경로 복원 방법 모두 BOJ에 있는 문제를 가지고 직접 풀어볼거라 별도로 연습 문제 챕터 blog.encrypted.gg 위 강의자료를 공부하면서 한번 더 생각해본 점들을 기록합니다. 왜 O(VE) 일까? 강의 자료 1 ~ 13 페이지 설명을 구현한 로직은 O(VE) 를 가진다고 설명해주셨습니다. 왜 O(VE)일까를 한번 생각해봤습니다. 해당 로직에서는 다음 정점을 찾기위해서 fix 된 정점(노란색 표시된)에서 간선을 탐색하여 4번 5번 정점으로 이동할 수 있습니다. 따라서 정점의 모든 간선을 탐색하기..

[백준/Python] 3649 로봇 프로젝트

문제링크 : https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 고려했던 방법들 1. 조합으로 풀수 있을까? 생각해보았지만 n이 1000000 까지 이므로 O(2^1000000)이 되어버려 조합은 사용할 수 없다. 2. 두번째는 레고 조각의 길이를 key 로 하는 해쉬맵을 만들어 [구멍의 너비 - 레고블럭 하나] 의 값이 해쉬맵에 존재하는지 판단하는 방법이 떠올랐다. 하지만 메모리 초과가 났다. 3. 세번째로는 이분 탐색으..

[백준/JS] 1205 등수 구하기

문제링크: https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 배열 정렬과 해쉬맵을 사용해서 푼 문제이다. 카테고리를 보니까 구현이라고 되어있더라. 해쉬맵 말고 배열의 index 를 사용할까 했는데, 최악의 경우 2,000,000,000 이 들어올 수 있으므로 불필요한 메모리를 사용할 것 같아 해쉬맵을 사용했다. 1. 테스트 케이스를 보면 N 이 0인 경우가 존재한다. 이 경우 때문에 삼항 연산자를 사용해 data 를 ..

[백준/JS] 2529 부등호

문제링크: https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 완전탐색 + 순열을 사용해서 푼 문제이다. 1. DFS로 0 부터 N+1 까지의 순열을 만든다. 2. 재귀의 deps 가 N+1 이 되면 만들어진 순열의 값들이 부등호의 조건을 만족하는지 체크한다. const fs = require('fs'); BOJkey = false; let input = fs .readFileSync(BOJkey ? './javascript/2529/input.txt' : '..

[백준/JS] 1700 멀티탭 스케줄링

문제링크: https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 이 문제에 처음 접근할때 완탐을 생각했으나, 시간 복잡도가 3¹⁰⁰ 이 나와 안된다 라고 판단했다. 그래서 그리디 하게 접근을 했다. 스택을 하나 만들어 [사용횟수, 기기명] 으로 push 하여 사용횟수를 기준으로 내림차순 정렬을 했다. 그리고 멀티탭이 꽉찬경우 스택의 최상단을 pop 하고 새로운 기기를 넣는 방식을 사용했다. 하지만 위 방법으로도 문제를 풀 수 없었고, 도무지 해결방법..

[백준/JS] 1946 신입사원

문제링크: https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 정렬 + 그리디 문제이다. 첫번째 점수를 기준으로 정렬을 하고, 순회하면서 두번째 점수가 더 작은 값일때 count 를 하면된다. 1. 서류심사 성적을 기준으로 정렬을 한다. 2. target 이라는 Number.MAX_SAFE_INTEGER 를 저장한 변수를 생성한다. 2-1. if (target > 두번째 점수) 를 만족할 경우 target 을 갱신하고 coun..