24266번: 알고리즘 수업 - 알고리즘의 수행 시간 5 (acmicpc.net) 24266번: 알고리즘 수업 - 알고리즘의 수행 시간 5 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 문제해설 알고리즘 수행 시간 시리즈 문제들은, 문제에서 제시한 함수의 시간 복잡도를 계산하는 문제들로, 로직을 구현하는게 아닌 문제에서 제시한 함수의 시간 복잡도를 사고하고 입력받은 값 N에 어떻게 비례하는지만 출력해주면 되는 문제이다. 이번 문제는 3중 for문이니 n 의 3제곱으로 수행시간이 비례하는 것을 알 수 있다. 시간 복잡도를 계산..

14215번: 세 막대 (acmicpc.net) 14215번: 세 막대 첫째 줄에 a, b, c (1 ≤ a, b, c ≤ 100)가 주어진다. www.acmicpc.net 문제해설 삼각형이 되기 위해서는 가장 큰 변의 길이가 나머지 두 변의 길이의 합을 넘지 않아야 한다. 그러니 먼저 삼각형의 가장 길이가 긴 변을 찾고, (모든 변의 길이의 합 - 가장 큰 변의 길이) 은 가장 큰 변을 제외한 나머지 두 변의 길이의 합이니, 두 변의 길이의 합이 가장 큰 변의 길이보다 짧다면 가장 큰 변의 길이를 (모든 변의 길이의 합 - 가장 큰 변의 길이) - 1 만큼 줄여주면 삼각형으로 만들 수 있다. 전체코드 const fs = require("fs"); var input = fs.readFileSync("/d..

3009번: 네 번째 점 (acmicpc.net) 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 문제풀이 문제는 간단하다. 직사각형의 네 번째 점의 좌표를 출력하는게 문제인데, 말 그대로 직사각형이기 때문에, 한 꼭짓점의 x좌표와 y좌표는 반드시 같은 x좌표를 갖는 다른 꼭짓점과, 같은 y좌표를 갖는 다른 꼭짓점이 존재한다. 만약 제공된 꼭짓점들의 좌표가 위와 같다면, 꼭짓점들의 x좌표는 10이 두개, 30이 한개이니 남은 꼭짓점의 좌표가 30이란 것을 알 수 있다. y좌표도 마찬가지로 20이 두개, 10이 한개이니 남은 꼭짓점의 y좌표는 10이 되겠다. 이를 로직으로 구현하면 각각의 꼭..

11653번: 소인수분해 (acmicpc.net) 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제해석 입력받은 N을 2로 나누어지지 않을때까지 나누고 나눌 때마다 2를 measure 배열에 추가한다. 나누어 떨어지지 않으면 3으로 증가, 마찬가지로 3으로 나누어지지 않을때까지 나누고 나눌때마다 3을 배열에 추가한다. 나누어 떨어지지 않으면 5로 나눈다. 3에서 4로 넘어가지 않은 이유는 4로 나누어질 수는 이미 2로 나뉘었기 때문이다. 이를 N이 1이 될때까지 반복하면 (3 -> 5)로 넘어가는 과정에서 보였 듯 배열에는 자연스럽게 소수만 들어가게 된다. 마지막으로 measure 배열의 원소들을 차례대로 모두 출력해주면 끝...

1978번: 소수 찾기 (acmicpc.net) 1978번: 소수 찾기첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.www.acmicpc.net 문제풀이 처음에는 N 범위가 크지 않아서 이중 for문으로 하나하나 모든 숫자에 모든 숫자를 %연산을 돌려서 무식하게 찾아내려고 했다가. 옆에서 지켜보던 친구가 에라토스테네스의 체를 사용해보라고 말해줘서 에라토스테네스의 체가 뭐지? 하고 검색해봤다. ...  에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (wikipedia.org) 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾..

9506번: 약수들의 합 (acmicpc.net) 9506번: 약수들의 합 어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다. n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라. www.acmicpc.net 이번 문제는 풀면서 알고리즘을 구상하는 사고력이 늘었다기 보다는 javascript는 이런 것도 있구나 알게된 점이 더 컸다. 문제풀이 n의 약수중 본인을 제외한 가장 큰 약수는 짝수일 경우에는 1을 제외한 가장 작은 약수인 2로 n을 나눈 값과 같을 것이고, 홀수일 경우에는 2로 나눈 값보다 작을 것이다. 그러니 1부터 n을 2로 나눈 값까지만 범위를 잡고 for문을 실행해도 모든 약수를 탐색할 수 있다..