본문 바로가기
728x90

algorithm

[백준알고리즘] 4948번: 베르트랑 공준 -C++ [백준알고리즘] 4948번: 베르트랑 공준 -C++ 4948번: 베르트랑 공준 (acmicpc.net) 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 소수 문제들은 다 비슷비슷한 것 같기도 하다. 에라토스테네스의 체를 사용해서 가능한 범위의 모든 수들의 소수 여부를 판단해주었다. 이후 입력되는 수에 대해서 에라토스테네스의 체를 이용해 소수 판정을 한다. 주의할 점은 입력으로 들어오는 \(n\)이 \(1\) 이상 \(123456\) 이하라는 것이고, 문제에서는 \(n\)보다 크고 \(2n\)보다 작거나.. 더보기
[백준알고리즘] 1929번: 소수 구하기 -C++ [백준알고리즘] 1929번: 소수 구하기 -C++ 1929번: 소수 구하기 (acmicpc.net) 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 소수 구하기 문제다. 이전 1978 소수 찾기 문제와 2581 소수 문제와 유사하다. 각 문제별 풀이는 아래와 같다. [백준알고리즘] 1978번: 소수 찾기 -Python, C++ (tistory.com) [백준알고리즘] 1978번: 소수 찾기 -Python, C++ [백준알고리즘] 1978번: 소수 찾기 -Python, C++ https://www.acmicpc.net/problem/1978 .. 더보기
[백준알고리즘] 2581번: 소수 -C++ [백준알고리즘] 2581번: 소수 -C++ 2581번: 소수 (acmicpc.net) 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 예전에 풀었던 문제다. 파이썬으로 푼 줄 알았는데, 자바로만 예에에에엣날에 풀고 안 풀었던 문제였다. 파이썬으로 안 푼 이유는 이전 1978번 소수 문제와 유사해서 안 푼 것 같다. 1978번 문제에 대한 풀이는 아래의 주소에서 했었다. [백준알고리즘] 1978번: 소수 찾기 -Python, C++ (tistory.com) [백준알고리즘] 1978번: 소수 찾기 -Python, C++ [.. 더보기
[백준알고리즘] 2775번: 부녀회장이 될테야 -C++ [백준알고리즘] 2775번: 부녀회장이 될테야 -C++ 2775번: 부녀회장이 될테야 (acmicpc.net) 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 동적 계획법을 이용해 풀었다. \(i\) 층 \(j\)호에는 \(i-1\) 층의 \(0\) 호부터 \(j\)호의 모든 거주민의 수만큼 살고 있다. 이때 \(0\)호부터 \(j-1\) 호까지의 모든 거주민의 수는 \(i\) 층의 \(j-1\) 호에 살고 있는 사람 수와 같다. 따라서 dp[i][j] = dp[i-1][j] + dp[i][j-1]이 성립하게 된다. #include void solv.. 더보기
[백준알고리즘] 1193번: 분수찾기 -C++ [백준알고리즘] 1193번: 분수찾기 -C++ 1193번: 분수찾기 (acmicpc.net) 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 각 대각선 방향마다 \(step\)이라 정해주었다. 각 \(step\)에서 분자와 분모의 합은 같다. 짝수 \(step\)과 홀수 \(step\)이 다른 점은 짝수 \(step\)에서는 \(1/step\)에서 \(step/1\) 로 점점 분자는 1씩 증가하고 분모는 1씩 감소하게 된다. 반대로 홀수 \(step\)에서는 \(step/1\)에서 \(1/step\)로 점점 분자는 1씩 감소하고 분모는 1씩 증가하게 된다. 하지만 각 단계에서 \(total\)이 각 \(step\)의 마지막 값을 기준으로 구.. 더보기
[백준알고리즘] 2292번: 벌집 -C++ [백준알고리즘] 2292번: 벌집 -C++ 2292번: 벌집 (acmicpc.net) 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 이 문제도 좀 쉽다 보니 다른 분들의 코드를 보니 다양하게 풀 수 있는 문제라고 생각한다. 다만 입력 숫자의 범위가 10억까지 들어올 수 있으니 int 형이나 unsigned int 형으로는 처리할 수 없다. 따라서 64비트를 처리하기 위해 uint64_t (unsigned long long)을 사용했다. #include int main(void) { uint64_t n; std::ci.. 더보기
[백준알고리즘] 2941번: 크로아티아 알파벳 -C++ [백준알고리즘] 2941번: 크로아티아 알파벳 -C++ 2941번: 크로아티아 알파벳 (acmicpc.net) 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 크로아티아 알파벳과 변경된 문자를 맵핑하는 개념이 필요했다. set을 만들고, 변경 후의 문자들을 넣어주었다. 이때 "dz="의 경우만 길이가 3이고 나머지는 2이기 때문에 "dz="를 제외한 것들을 넣어주었다. 이후 하나씩 인덱싱하면서 앞 글자와 현재 글자를 한 쌍으로 만들어 길이가 2인 substr을 만들었다. .. 더보기
[백준알고리즘] 2908번: 상수 -C++ [백준알고리즘] 2908번: 상수 -C++ 2908번: 상수 (acmicpc.net) 2908번: 상수 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 www.acmicpc.net 풀이 방법이야 여러 가지 있는 것 같다. 모든 숫자는 0이 없이 세 자리 숫자라는 조건 덕분에 각 자리의 숫자를 모두 찾아서 뒤집힌 숫자를 일일이 구할 수도 있다. 나는 여기서 string으로 입력받고 reverse하기로 결정했다. reverse()의 경우 헤더에 존재하며 뒤집을 주소의 iterator type의 first와 last를 인자로 받는다. 따라서 begin()과 end()를 사.. 더보기
728x90

티스토리툴바