본문 바로가기

JavaScript

 (28)
[Programmers / JS] Lv.2 미로 탈출 문제 설명 제한 사항 입출력 예 Solve 어떤 맵이 존재하고 최단 거리를 구해야한다면 BFS를 가장 먼저 생각합니다. 레버를 꼭 거치고 난 후 출구에 도착해야 하기 때문에 "시작 지점에서 부터 레버까지의 거리 + 레버에서부터 출구까지의 거리"를 구해야합니다. BFS를 구현하고 각각 시작지점과 레버, 레버와 출구의 좌표를 넣어 거리를 구한 후 더하여 결과값을 리턴해주었습니다. 둘 중에 하나라도 거리값이 0이라면 탈출할 수 없는 경우이기 때문에 예외처리 하였습니다. Code function solution(maps) { let answer = 0; const col = maps.length; const row = maps[0].length; let start = null; let lever = null; ..
[Data Structure / JS] 이진 힙(Binary Heaps) / 우선순위 큐(Priority Queue) 힙(Heap)이란 ? 완전 이진트리 기반의 자료구조로, 최대 힙과, 최소 힙 두 종류로 구분됩니다. 최대 힙의 경우에는 루트노드에 가까울 수록 크고, 최소힙은 루트 노드에 가까울 수록 작은 값을 가집니다. 힙에서는 데이터의 중복이 허용되며, 주로 우선순위 큐를 구현하는데 사용됩니다. 나아가 힙 정렬, 다익스트라의 최단 경로 알고리즘에서도 사용됩니다. 힙은 부모자식간의 크기 차이만 비교합니다. 형제 노드 간에의 크기 차이를 고려하지 않습니다. 구현 힙은 일반적으로 각 요소에 효율적으로 접근할 수 있는 배열을 통해 구현됩니다. 인덱스 i에 위치한 노드의 부모는 (i-1)/2에 위치하며, 왼쪽 자식 노드는 2*i + 1, 오른쪽자식 노드는 2*i + 2에 위치하게 됩니다. Heap에서의 삽입 힙에서의 삽입은 ..
[BOJ / Node.js] 2841. 외계인의 기타 연주 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 문제 상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다. 보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다. 멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 ..
[Data Structure / JS] 연결 리스트 연결리스트 ? 연결리스트는 선형 구조로서 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 입니다. 배열이라는 편리한 자료구조가 자바스크립트에서 제공이 되지만 왜 연결리스트가 필요할까 라는 의문이 들 수 있습니다. 배열과 연결리스트의 차이 대해서 알아봅니다. 배열과의 차이점 1. 메모리 차이 배열은 순차적인 데이터, 즉 메모리 영역이 연속적으로 사용됩니다. 연결리스트는 각 데이터가 퍼져있습니다. 즉, 포인터를 사용하여 각 영역을 참조합니다. 2. 요소의 삭제 / 추가 배열은 O(n) 시간이 소요됩니다. 연결리스트의 삭제와 추가는 O(1) 시간이 소요됩니다. 연결 리스트의 특징 연결 리스트는 인덱스가 없습니다. 연결 리스트는 무작위 접근이 불가능합니다. 연결 리..
[BOJ / Node.js] 17299. 오등큰수 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다. Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다. 예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) ..
[BOJ / Node.js] 2529. 부등호 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 문제 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 3 1 7 ..
[BOJ / Node.js] 5635. 생일 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 반에 있는 학생의 수 n이 주어진다. (1 ≤ n ≤ 100) 다음 n개 줄에는 각 학생의 이름과 생일이 "이름 dd mm yyyy"와 같은 형식으로 주어진다. 이름은 그 학생의 이름이며, 최대 15글자로 이루어져 있다. dd mm yyyy는 생일 일, 월, 연도이다. (1990 ≤ yyyy ≤ 2010, 1 ≤ mm ≤ 12, 1 ≤ dd ≤ 31) 주어지는 생일은 올바른 날짜이며, 연, 월 일은 0..
[BOJ / Node.js] 2638. 치즈 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 문제 N×M의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 모양과 같은 치즈(회색으로 표시된 ..
728x90

티스토리툴바