너비우선탐색이란 무엇인가? 트리나 그래프를 탐색하는 기법 중 하나로써 너비(Breadth)를 우선적으로 탐색하는 방법이다. 너비우선탐색 구현을 위해서 보통 큐(Queue) 자료구조를 이용한다. 너비우선탐색의 동작 루트 노드부터 탐색을 시작한다. 기준 노드에 자식 노드들이 존재한다면 큐에 추가하고, 자기 자신은 큐에서 나온다. 위의 과정을 반복한다. 큐에 아무것도 존재하지 않게 된다면 탐색이 종료된다. 너비우선탐색 주의사항 만약 너비가 넓은 트리나 그래프라면 큐에 저장해야하는 너비 요소들이 많아지므로 공간복잡도가 증가한다. 따라서 너비우선탐색을 효과적으로 사용하기 위해서는 너비가 좁은 트리나 그래프를 대상으로 사용하는 것이 좋다. 구현 // 트리 구현체 class BST { constructor() { t..
사진출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC 트리란 무엇인가? 트리는 부모, 자식 노드의 관계를 정의한 자료구조라고 볼 수 있다. 트리에 속한 노드는 부모-자식 관계에 따라 부모가 자식을 가르키는 방향으로 진행된다. 이 때 모든 노드는 루트 노드와 멀어지는 방식으로 연결된다. 이진 탐색 트리의 동작 모든 부모 노드가 최대 2개의 자식 노드(left, right)를 가진다. (모든 이진트리의 공통점) 왼쪽 자식 노드는 부모보다 항상 작고, 오른쪽 자식 노드는 부모보다 항상 크다. 이진 탐색 트리가 단순 이진 트리보다 빠른 이유 단순 이진 트리는 부모 노드가 최대 2개의 자식노드만 가진..
문제 링크 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 답안 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "text.txt"; const [n, r, c] = fs.readFileSync(filePath).toString().trim().split(" ").map(Number); function solution(n, r..
문제 링크 https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 답안 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "text.txt"; const newLine = process.platform === "linux" ? "\n" : "\r\n"; const input = fs.readFileSync(filePath).toString()...
에라토스테네스의 체 고대 그리스 수학자인 에라토스테네스가 고안했다. 주어진 자연수보다 작거나 같은 소수들이 어떤 것들이 있는지 찾아내는 알고리즘이다. 주어진 자연수 만큼 표를 그려놓은 뒤, 소수의 배수들을 지워나간다. 최종적으로 남은 숫자들은 소수이다. 자연수 25에 소수가 몇개 포함되어 있는지 에라토스테네스의 체를 이용해 판별해보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 자연수 1은 소수가 아니다. 2는 유일한 짝수인 소수이다. 2는 소수로써 남겨두고 2의 배수들은 전부 지워준다. 3은 소수이다. 3은 소수로써 남겨두고 3의 배수들은 전부 지워준다. 4는 이미 합성수라고 이전에 결론이 났다. 넘어간다. 5는 소수이다. 5는..
유클리드 알고리즘 유클리드 알고리즘은 두 자연수의 최대공약수를 효과적으로 구하는 알고리즘이다. 두 자연수의 최대공약수를 알고 있다면, 두 자연수의 최소공배수도 쉽게 구할 수 있다. 두 자연수의 최대공약수를 구하는 원시적인 방법은 아래와 같다. 각각 자연수의 약수들을 전개한다. 전개된 약수 들 중 공통된 숫자들을 곱한다. 하지만 각 자연수의 약수를 구하는 작업은 굉장히 번거롭다. 프로그래밍적으로도 시간이 많이 걸리는 작업이다. 이를 간단히 해결하기 위해 두 자연수의 최대공약수를 구할때는 유클리드 알고리즘을 사용한다. 유클리드 알고리즘은 유클리드 호제법이라고도 한다. https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC..
문제 링크 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 답안 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "text.txt"; const newLine = process.platform === "linux" ? "\n" : "\r\n"; const key = fs.readFile..
문제 링크 https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 군수열 문제이다. 인덱스(파란색 글씨)마다 배열되는 분수의 분자/분모 증가 방향이 달라지는데, 인덱스가 홀수라면 분자가 1씩 감소되고 분모는 1씩 증가하는 방향으로 전개되고 인덱스가 짝수라면 분자가 1씩 증가하고 분모는 1씩 감소하는 방향으로 전개된다. 답안1 ( 수정한 풀이 ) const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "text.txt"; let num = parseInt(fs.readFileSync..
테이블 설정하기 전에 스키마(데이터베이스)가 설정되었다고 가정하고 진행한다. 명령프롬프트로 테이블 설정 스키마에 접근한다. 여기에서 스키마명은 nodejs 이다. TABLE을 만든다. CREATE TABLE 테이블명 으로 TABLE 생성을 선언한다. CREATE TABLE 테이블명 ( ) 에서 괄호 내부에 있는 내용들은 데이터베이스의 각 컬럼에 대한 정보를 설정하는 것이다. 괄호 바깥에 있는 내용들은 테이블에 대한 설정에 관한 것이다. 테이블의 소개, 기본 캐릭터셋, 데이터베이스 엔진등을 설정할 수 있다. 위의 프롬프트에서 볼 수 있듯이, id부터 created_at까지는 컬럼에 대한 설정이다. 해당 테이블에 대한 설정도 존재하는데, 일단 컬럼에 대한 설정부터 알아보자. 컬럼에 대한 설정 INT는 정수를..
MySQL을 명령프롬프트로 실행시키기 위해 MySQL이 설치된 폴더 > bin 으로 이동한다. 명령프롬프트에 접속했으면 mysql -h localhost -u root -p 를 입력하고 엔터를 친다. Enter password가 나왔다면 그대로 패스워드를 입력하고 엔터를 친다. mysql -h localhost -u root -p 에서 -h는 호스트명을, -u는 유저명을, -p는 비밀번호를 사용하겠다는 뜻이다. 호스트명은 localhost이니 MySQL에서 개방한 포트에 따라 localhost:8080/ 과 같은 형식으로 세팅될 것이고, 유저명은 root를 사용했으며, -p를 통해 비밀번호를 입력하고 접속할 수 있게 되었다.
