평소에 웹 개발을 하며 자바스크립트는 자주 사용했지만 이번 코테에 자바스크립트를 쓰려고 하니 생소한 부분이 있어서 코테용 자바스크립트 문법을 정리해보려고 한다. 입출력입력은 기본적으로 fs 모듈의 readFileSync를 사용한다. 그리고 입력 양 끝에 공백 혹은 newline이 있을 때를 대비해서 trim()을 붙이는게 좋다. 하지만 주로 파일을 읽을 때 사용하는 것이라서 알고리즘 문제 풀이를 위해서 적절한 타입으로 변환해야 한다.  1. 문자열 입력const fs = require("fs");const input = fs.readFileSync(0).toString().trim();2. 숫자 입력const fs = require("fs");const input = Number(fs.readFileSy..

https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 이전 포스팅에서 CCW 알고리즘을 활용하여 선분 교차하는 방법에 대해서 배웠다. https://growth-coder.tistory.com/163 이 방식을 그대로 사용하면 된다. 우선 세 점이 일직선 상에 존재하는 경우가 없다고 했으므로 ccw의 값이 0인 경우는 신경쓰지 않아도 된다. 그럼 예외 사항은 아래 그림과 같은 경우만 신경쓰면 된다. 이 경우는 선분 AC를 기준으로 한 번, 선분 BD를 기준으로 두 번 ..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 우선순위 큐를 사용하여 푸는 문제이다. 우선순위 큐의 삽입, 삭제 시간 복잡도는 O(log N)이다. 파이썬에서 우선순위큐인 heapq 모듈을 제공한다. heapq의 경우 사용방법이 특이한데 따로 리스트를 만들고 이 리스트를 heapq 메소드의 인자로 사용해야 한다. 1. 삽입 : heapq.heappush( list, value ) import heapq li=[] heapq..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 이 문제를 해결하기 위해선 알아야하는 수학적 지식이 있다. (a*b)%c=((a%c)*(b%c))%c 위 공식을 사용하면 이 문제를 분할 정복 방식으로 해결할 수 있다. 예를 들어 3을 12번 곱한 값을 7으로 나눈 나머지를 구한다면 3을 6번 곱한 값을 7로 나눈 나머지를 구하고 이를 제곱하여 다시 7로 나누면 된다. 3을 6번 곱한 값을 7로 나눈 나머지는 3을 3번 곱한 값을 7으로 나눈 나머지를 구하고 이를 제곱하여 다시 7로 나누면 된다. 이렇게 하향식..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 식은 +와 -로만 이루어져있고 괄호를 적절히 쳐서 최소값을 구하는 문제이다. 즉 식을 뺄 때는 괄호를 적절히 쳐서 최대한 큰 값을 빼야한다. 50 + 40 - 30 + 40 +20 - 10 + 20 위와 같은 식이 있다고하자. 식에서 -가 나오면 그 값부터 다시 - 가 나오거나 식의 끝까지 괄호를 치면 된다. 50 + 40 - (30 + 40 +20) - (10 + 20) 파이썬의 경우 문자..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 특정 수로 나누어 떨어지는 구간 합의 개수를 구하는 문제이다. 모든 (i, j)쌍을 구하면 너무 오랜 시간이 걸린다. 구간 합을 적절히 이용해서 효율적으로 답을 구하는 알고리즘을 짜야한다. 이 문제를 풀기 위해 우선 누적 합을 통해 구간 합을 구하는 방법을 알아야 한다. 백준 11659번 문제를 한 번 풀어보는 것을 추천한다. https://grow..