부동소수점에 대한 이해

부동 소수점은 실수의 표현과 아주 작은 수와 아주 큰수를 표현하기 위해 도입되었습니다. 또한 고정 소수점이라는 방식도 존재하며 우선 고정 소수점 부터 무엇인지 알아봅시다. 고정 소수점(Fixed Point) 소수점이 찍힐 위치를 미리 정해놓고 소수를 표현하는 방식입니다. 장점: 실수를 정수부와 소수부로 표현하여 단순합니다. 단점: 표현의 범위가 너무 적어서 활용하기 힘듭니다. (정수부는 15bit, 소수부는 16bit ) 정수부만 따졌을때 2^16 - 1 의 수 까지 표현이 가능한데, 터무니 없이 작은 수 입니다. 부동 소수점 지수의 값에 따라 소수점이 움직이는 방식을 활용한 실수 표현 방법입니다. 즉, 소수점의 위치가 고정되어 있지 않습니다. 실수를 가수부 + 지수부로 표현합니다. 가수: 실수의 실제값..

[백준/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..

자바스크립트의 해시테이블

해시테이블에 대해 공부하게 된 사연.. 백준에서 알고리즘 문제를 풀다 똑같은 로직인데, 배열로 value에 접근할 때와 object를 사용해 구현한 Map 을 통해 value에 접근했을때 속도차이가 유의미하게 나는 것을 경험했다. 자바스크립트에서 배열은 객체 보다 더 나은 성능을 가진다. 자바스크립트의 배열은 배열을 흉내낸 객체이다. 따라서 배열 요소에 접근할 때 일반적인 배열보다 느릴 수밖에 없는 구조적인 단점을 보완하기 위해 모던 자바스크립트 엔진은 배열을 일반 객체와 구별하여 좀 더 배열처럼 동작하도록 최적화하여 구현했다. 위 자료를 근거로 배열과 객체를 모두 사용할 수 있는 경우가 있다면 배열을 통해 value에 접근하는 편이 더 성능상 유리하다는 것을 알았다. (나는 객체를 Map 처럼 만들어서..

[백준/JS] 5052 전화번호 목록

문제링크: https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 문자열 + 배열 정렬 + 해쉬맵 으로 푼 문제이다. 프로그래머스에 비슷한 문제가 있었던 것 같다. 나는 해쉬맵에 번호를 저장하고, 다음 전화번호를 digit 하나씩 더하면서 합친 문자열이 해쉬맵에 있는지 확인하는 로직으로 문제를 해결했다. 위와 같은 로직을 사용하기위해서는 1. 우선 테스트 케이스 정렬을 해야한다. 1-1. 정렬하지 않는다면 91125426 , 9..

[백준/JS] 1026 보물

문제 링크: https://www.acmicpc.net/problem/1026 배열 문제이다. 1. 한쪽 배열은 asc 로 정렬한다. 2. 나머지 배열은 desc로 정렬한다. 3. 두배열의 인덱스를 0 ~ N 까지 곱하여 더한다. const fs = require('fs'); BOJkey = false; let input = fs .readFileSync(BOJkey ? './javascript/1026/input.txt' : './dev/stdin') .toString() .trim() .split('\n') .map(el => el.split(' ').map(Number)); const [N] = input.shift(); ascArr = input.shift().sort((a, b) => a - b..

[백준/JS] 1449 수리공 항승

문제링크: https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 그리디 문제이다. 프로그래머스에 똑같은 문제가 있다. 1. 수리해야하는 위치가 담긴 배열을 오름차순으로 정렬한다. 2. 테이프가 붙여진 위치를 저장한다. 2-1. 수리해야하는 위치가 [1, 2, 3, 4] 이고 테이프의 길이가 3(L) 이라고 하자. 테이프는 1(처음만난 수리지점) 부터 붙여나가야한다. 2-2. 이때 해당 테이프로 1 ,2 ,3 의 위치까지 커버가 가능하..