본문 바로가기

자료구조+알고리즘/BOJ

[백준-Gold4] 11404 플로이드 - javascript https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net [풀이] 노드 --------간선-------> 노드 (도시) 버스 (도시) 예제) 도시 5개 버스 14개 시작점 끝점 비용 1 2 2 ... * 플로이드 알고리즘 설명 참고 : https://eonhwa-theme.tistory.com/178 [코딩테스트 알고리즘] 플로이드-워셜 - javascript ﹅ 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 모든 노드에서 다른.. 더보기
[백준18870-silver2] 좌표 압축 (javascript) https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net [풀이] 📌 좌표압축 ? 만약 x축의 좌표가 [0 ,1 ,2 ,3 ,100 ,150]과 같이 주어졌을 때, 0~3은 각 1씩 차이라 크게 문제 되지 않지만 100과 150을 탐색하기 위해서는 100까지, 150까지 탐색해야하는 문제점이 있다. 다시말해 4~99, 101~149는 쓰지 않는데 탐색하고 있는 시간낭비를 하고 있는 것이다. 숫자의 갭차.. 더보기
[백준2751-silver5] 수 정렬하기 2 (javascript) https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net [풀이] let fs = require('fs'); let [n, ...input] = fs.readFileSync('/dev/stdin').toString().trim().split('\n'); input.sort((a, b) => a - b); console.log(input.join('\n')); 📌 여기서 주의할점은! sort() js 내부함수 사용할 시 숫자 배열 정렬은 무조건.. 더보기
[백준11441-silver3] 합 구하기 (javascript) https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net [풀이] N 개 요소의 배열 에서 M 개마다 i, j 누적합을 구하는 문제이다 처음 풀이에서는 시간초과가 났다. 난이도에 비해 쉽다면,, 무조건 시간초과 나는 문제임을 주의하자! ✂️시간 초과 나는 문제 const fs = require('fs'); let input = fs.readFileSync('./input.txt')... 더보기
[백준2167-silver5] 2차원 배열의 합 (javascript) https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net [유형] - 구현 - 누적 합 [풀이] 첫번째 리턴된 숫자 63을 예로 들면, i j x y = 1 1 2 3 (1,1) 위치부터~ (2,3) 위치까지 저장된 숫자들 합 ---> j, y | i, x const fs = require('fs'); const [[n, m], ...arr] = fs.readFileSync('./input.txt').toString().tr.. 더보기
[BOJ-10845_silver4] 큐 (자바스크립트) https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net [유형] - 자료구조 - 큐 [문제 풀이] 명령어를 판단할 배열요소는 temp에 넣고 "출력" 명령시 새로운 변수에 넣어준다 한줄에 하나씩 출력해줌! [코드] ||❌ 시간초과 난 코드 const fs = require('fs'); let [n, ...input] = fs.readFileSync('./input.txt').toString().trim().split('\n'); let.. 더보기
[BOJ-11866_silver5]요세푸스 문제 0 (자바스크립트) https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net [유형] - 구현 - 자료 구조 - 큐 [풀이] K 번째를 제거하면서 배열에 넣어줌 대략 아래 처럼 [코드 풀이] const fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split(' '); const n = +input[0]; // string -> number const k = +input[1]; let ans = []; //n 길이의 1~n 배열 생성 let arr = Array.. 더보기
[BOJ-24511_silver3] queuestack (javascript) https://www.acmicpc.net/problem/24511 24511번: queuestack 첫째 줄에 queuestack을 구성하는 자료구조의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$) 둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번 자료구조가 큐라면 $A_i = 0$, 스택이라면 $A_i = 1$이다. 셋째 줄 www.acmicpc.net [유형] - 자료구조 - 스택 - 덱 - 큐 [풀이] N = 4 : 자료구조 4개 A = 0 1 1 0 : 각 자료구조의 종류 === Queue 혹은 Stack !! (문제에도 적혀있다 ....) B = 1 2 3 4 : 현재 각 자료구조에 들어있는 수 M = 3 : 넣을 수의 갯수 C = 2 4 7 : 넣을 수 x.. 더보기
[BOJ-17413_silver3] 단어 뒤집기2 (javascript) https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net [문제 유형] - 구현 - 자료 구조 - 문자열 - 스택 [풀이] 문자열 뒤집기 여기서 예외는 태그 안에 있는 문자열은 뒤집지 않는다. 하나하나 케이스 그려보면서 해보면 이해됨! [코드 풀이] const fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().tri.. 더보기
[BOJ-10773-Siver4]제로 (javascript) https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net [유형] - 스택 [문제] [풀이] K 숫자 입력 받고 K 갯수대로 숫자들 입력받기 0이 나오면 pop() ... 마지막 배열에 남은 숫자들 더하면 끝 [코드 풀이] // 파일 불러오기 -> fs모듈 let fs = require('fs'); let input = fs.readFileSync('./input.txt').toString().split('\n'); /.. 더보기
반응형

티스토리툴바