수학

[C++] 9020번 골드바흐의 추측

골드바흐의 추측은 예전에 학교 정수론 강의에서 들었었다. (사실 기억이 어렴풋이 나는거라 자세히는 기억이 안난다.) 2보다 큰 짝수는 무조건 두 소수의 합으로 표현이 된다는 것이 골드바흐의 추측이다. 그리고 차이가 가장 적게 나는 방법으로 두 소수를 찾으면 된다. 처음에 풀었는데 시간이 1976ms가 나와서 다른 풀이를 찾아봤다. 24ms만 초과했어도 시간초과였다. 잘못된 방법으로 풀었기 때문에 다른 풀이로 풀었는데 0ms가 나왔다. 문제풀이 처음의 내가 푼 방식의 코드부터 보여주겠다. #include #include #include using namespace std; int testCase, num; int ans1, ans2; bool primeCheck[10001]; // true라면 소수아님. ..

[C++] 백준 1541번 잃어버린 괄호

문자열을 파싱하는 문제. 식을 해석하는 문제는 나같은 경우는 큐 자료구조를 이용해서 많이 푼다. 문제 접근 방식 우선 어떻게 해야 식의 값이 최소가 되는지를 알아보려고 했다. 식에 더하기와 빼기밖에 없으므로, 어떤 경우로 식을 처리를 해야 최소값이 될 수 있을지 혼자 식을 따로 적어서 생각해 보았다. 일단 식의 계산을 맨 앞에 숫자부터 해야된다고 가정할때, 10+20-10-20+30-20 -> 10+20-10-(20+30)-20 다음 식 같은 경우를 만들어서 살펴보았는데 다음과 같은 두 가지 경우를 고려하게 되었다. +의 경우는 그냥 앞에서 계산한다. -의 경우, 바로 뒤의 식이 +이면 +를 먼저 계산한다 (즉, 괄호를 씌워준다.) / 아니라면 그냥 앞에서 계산한다. 이렇게 고려해줄 경우 식의 값이 최소..

[C++] 백준 1002번 터렛

수학 문제. 예전에 처음 이문제를 봤을 때 원의 접점을 구하는 문제라고 생각 못했던 것 같다. 항상 그렇듯 알고리즘 문제에는 문제에 정말 많은 힌트가 들어있다 여기서도 변수에 r이라는 힌트가 주어져 있다. 그 말은 r은 원의 반지름. 원을 이용해서 풀라는 말이다. 문제 접근 방식 우선 두 원이 있을때 어떤 경우들이 있는지 확인해 보았다. 그렇게 보니 총 여섯 가지가 나오게 되었다. 따라서 두 원의 중점 사이의 거리, 반지름끼리의 합과 차만 알면 이 조건들을 구현할 수 있다. 우선 math.h 라이브러리를 사용해서 두 원의 중점 사이의 거리를 구할때 제곱과 루트 메서드를 사용했다. pow(수, 지수) : 수를 지수승 한다. sqrt(수) : 수에 루트를 씌운다. 메인함수의 시작부분에는 테스트 케이스 수를 ..

[C++] 백준 1011번 Fly me to the Alpha Centauri

처음 문제를 접근 했을 때 백트래킹으로 풀려고 시도했다. 재귀함수로 모든 경우를 돌면서 최소로 접근할 수 있는 것으로 계속해서 갱신하려고 했다. 구현은 했는데, 메모리 초과가 나면서 풀지 못했다. 단계별로 풀어보기에서 발견한 문제였는데, 분야가 수학이였다. 결국 조금 도움을 얻고자 게시판을 조금 검색해서 규칙성이 있다는 것을 얼핏 보았다. 그래서 이 규칙성을 가지고 어떻게 구현을 해야할까 고민했지만 결국 해답을 얻지 못했다. 글 읽기 - 풀이 정리해 보았습니다 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 그러다가 게시판을 찾던 중 이런 글을 발견했고, step마다 갈 수 있는 거리가 정해져 있다는 것이였다. 이동 횟수 과정 이동 거리 1 1 1 2 1 1 2 3 1 2 1 4 4 1..