- Total
목록전체 글 (255)
꿈꾸는리버리
[백준 알고리즘] 4153 직각삼각형
문제: https://www.acmicpc.net/problem/4153 4153번: 직각삼각형 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. www.acmicpc.net 풀이방법: 1. 세 변의 길이 중 가장 큰 수(max) 찾기 -> 나머지는 mid에 넣었다. 2. 피타고라스 max^2 == mid1^2 + mid2^2 일 경우 right 출력 #include pow(max,2) -> max *max라고도 할 수 있지만, 헤더 파일을 인스톨해서 c++ 수학 연산자를 사용해서 계산하였다. 작성한 코드는 다음과 같다. #include #include using namespac..
[백준 알고리즘] 3009 네 번째 점
문제: https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 풀이방법: 30 20 10 10 10 20 그래프에 나타내어 봤더니 보였던 규칙 ! x축) 짝이 있는 10과 짝이 없는 30 y축) 짝이 있는 20과 짝이 없는 10 --> 짝이 없는 30, 10이 결과값으로 출력이 되어야 함 작성한 코드는 다음과 같다. #include using namespace std; int Coordinates(int point[]){ if(point[0] == point[1]){ return point[2]; }else{ if(point[0] ..
[백준 알고리즘] 1085 직사각형에서 탈출
문제: https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 풀이방법: 최단거리 구하기.. 각 모서리에 수선의 발 내리기.. 좀... 뜬금없이 easy한 문제였다.. 작성한 코드는 다음과 같다. #include using namespace std; int min_distance(int a, int min){ if(a < min){ min = a; } return min; } int main() { int x, y, w, h; ci..
[백준 알고리즘] 9020 골드바흐의 추측 C++
문제: https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 풀이 방법 : 단계 1) 해당 수의 제곱근까지만 나누어보는 것 && 에라토스테네스의 체 (1929 소수 구하기와 동일) 에라토스테네스의 체를 사용해야 하는 이유는 시간초과 때문이다. 소수를 판별하기 위해서 이전의 수를 모두 나누어보는 것은 시간복잡도가 엄청나게 커지는 방법이기 때문이다. 해당 수의 제곱근까지만 나누어보는 것: 쉽게 생각해보자. 예를 들어 18의 소수를 구..
[백준 알고리즘 4948] 베르트랑 공준
https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 풀이방법 : 해당 수의 제곱근까지만 나누어보는 것 && 에라토스테네스의 체 (백준 1929 소수구하기 문제와 동일) 에라토스테네스의 체를 사용해야 하는 이유는 시간초과 때문이다. 소수를 판별하기 위해서 이전의 수를 모두 나누어보는 것은 시간복잡도가 엄청나게 커지는 방법이기 때문이다. 해당 수의 제곱근까지만 나누어보는 것: 쉽게 생각해보자. 예를 들어 18의 소수를 구하려고 한다. 1,2,3..
[백준 알고리즘 11653] 소인수분해
https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이 방법 : 재귀함수를 이용해서 문제를 풀었다. 작성한 코드는 다음과 같다. #include using namespace std; void calculate(int n){ if( n
[백준 알고리즘] 1929 소수구하기 C++
문제 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 방법 : 해당 수의 제곱근까지만 나누어보는 것 && 에라토스테네스의 체 에라토스테네스의 체를 사용해야 하는 이유는 시간초과 때문이다. 소수를 판별하기 위해서 이전의 수를 모두 나누어보는 것은 시간복잡도가 엄청나게 커지는 방법이기 때문이다. 해당 수의 제곱근까지만 나누어보는 것: 쉽게 생각해보자. 예를 들어 18의 소수를 구하려고 한다. 1,2,3,4,5,6,7,8,...,18 -> 루트 18은 대략 4. xx이다...