https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net https://www.acmicpc.net/problem/10815 10815번: 숫자..
알고리즘 풀이
1. 좌표 정렬 const fs = require('fs'); const input = fs.readFileSync("dev/stdin").toString().trim().split("\n"); input.shift() const arr = input.map(item => item.split(" ").map(Number)) console.log('origin: ', arr) arr.sort((a, b) => { if (a[0] > b[0]) return 1 else if (a[0] b[1]) return 1 else if (a[1] < b[1]) return -1 else 0 } }) // 위의 소스코드를 아래와 같이 간단하게 줄일 수 있다..
일단 dy라는 다이나믹 배열을 만들겠습니다. 그리고 그 안에 1부터 5까지는 미리 세팅해 두겠습니다. 그리고 6부터 시작해서 처음에는 왼쪽 다섯칸 가서 dy[1]이 0보다 크다면 d[6] = dy[1] + 1을 해줍니다. 만약 dy[1]이 -1이라면 두번째로 dy[6]에서 왼쪽으로 세칸을 가서 dy[3]이 0보다 크다면 dy[6] = dy[3] + 1을 해줍니다. 만약 dy[3]도 -1이라면 dy[6] = -1을 해줍니다. 이렇게 예제에 입력된 대로 18까지 이 로직을 반복해주면 아래의 dy배열처럼 각 자릿값에 숫자가 들어갈 것입니다. 마지막으로 dy[18]을 출력해주면 됩니다. 소스코드로 재현해 보겠습니다. var fs = require('fs'); let input = fs.readFileSync('..
백준으로 문제를 풀고있으면 테스트하기 어렵다는 단점이 있습니다. 이 때, Replit을 통해 테스트를 할 수 있는 방법을 소개하겠습니다. 1. https://replit.com/ 에 접속합니다. 2. 회원가입을 진행합니다. 3. 로그인합니다. 4. 아래의 화면이 표시되는데요. 우측 상단에 '+'버튼을 누릅니다. 5. Template: Node.js 선택 6. Title 입력 7. '+ Create Repl'을 클릭한다. 8. 아래와 같이 Repl이 생성된 것을 알 수 있습니다. Repl이란 Read Eval Print Loop라는 뜻으로 읽고 평가하고 출력하고 반복하라는 뜻입니다. 사용자의 입력을 취하고 이를 평가하고 결과를 사용자에게 반환시키는 단순한 상호작용 컴포터 프로그래밍 환경입니다. 9. 백준의..
1. 이진트리 넓이우선탐색(BFS) 출발지에서 도착지까지 가는 최단거리를 구할 때 사용한다. 2. 문제풀이 5에서 시작해서 -1, +1, +5를 해서 4, 6, 10을 만든다. Level 2인 4로 가서 3, 5, 9를 만드는데 5부터 다시 하면 무한루프를 돌기 때문에 이미 지나친 곳은 제거해준다. 그럼 Level 2는 3, 9, 7, 11, 15가 된다. 도착지인 14가 없으므로 Level3으로 간다. 2, 8, 14,... 진행되는데 14가 나왔으므로 끝낸다. function solution (s, e) { let answer = 0; let ch = Array.from({ length: 10001 }, () => ); let queue = []; queue.push(s); ch[s] = 1; let..
1. 그래프와 인접행렬 기호로는 G(V, E)로 표시된다. V(vortex) = 노드, 정점 E(edge) = 노드와 노드를 연결하는 간선 1. 무방향 그래프 예시로 노드가 도시이고 간선이 도로일 경우가 된다. 1번 도시에서 2번 도시로 이동할 수 있고 2번 도시에서 1번 도시로 이동할 수 있다. a b 1 2 2 1 1 3 3 1 2 4 4 2 2 5 5 2 3 4 4 3 위의 그래프(인접행렬)를 표현하려면 2차 배열로 표현한다. 1 2 3 4 5 1 0 1 1 0 0 2 1 0 0 1 1 3 1 0 0 1 0 4 0 1 1 0 0 5 0 1 0 0 0 위 그래프는 무방향이기 때문에 아래와 같이 표현한다. 각 행과 열은 노드가 된다. graph[a][b] = 1; grahp[b][a] = 1; 2. 방..
이번주 스터디 주제는 DFS와 BFS이다. 첫번째로 풀어야하는 문제는 '백준 2606 바이러스' 이다. DFS에 대한 인강을 찾아봤는데 Deep 의 약자로 일반적으로 재귀함수로 구현되면 재귀를 타고, 타고, 타서 탈출조건에 도달하고 그 다음에 파라미터를 하나씩 바꿔 가면서 정답을 찾는 방식이라는 것까지만 알고 일단 문제를 풀어보기로 했다. 단순히 개념만 가지고 알고리즘을 푸려고 하니 어려워서 일단 다른 사람들이 만든 코드를 보고 공부하려고 했다. 그런데 다른 사람이 짠 코드 이해가 잘 가지 않는다. 그래서 DFS에 대한 개념공부를 하기로 했다. 공부는 예전에 인프런에서 구매해두었던 '자바스크립트 알고리즘 문제풀이(코딩테스트 대비)'를 활용하도록 하겠다. INDEX 재귀함수와 스택프레임 이진수 출력 이진트..
Hash Table 검색하고자하는 key값을 입력받아서 hash function을 돌려서 반환받은 hash code를 배열의 index로 환산을 해서 데이터에 접근하는 방식의 자료구조 Hash Table의 이점 선형구조로 데이터에 접근할 경우의 시간복잡도는 0(N)이어서 아이템이 많을 수록 찾는 시간도 오래 걸린다. 하지만, Hash Tables의 시간복잡도는 0(1)로 Constant Time(상수 시간)이다. Hash Tables의 collision(충돌) 각기 다른 Key에 대하여 동일한 Index를 환산해 같은 공간에 들어가게 되는 상황을 말한다. 이 경우는 찾고자 하는 여러 데이터들이 들어간 공간에서 선형검색을 하게 된다. 이 때문에 Hash Tables는 언제나 상수 시간인 것은 아니다. Ha..
