💡 Problem Solving/Baekjoon

[백준 - 7490] 0 만들기 [C++]

1. 문제 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 2. 풀이 전형적인 브루트포스 문제이다.. 나의 경우 두번 '출력 형식이 잘못되었습니다' 를 받았었는데.. '각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.' 이것을 간과한채 제출했었다.. 케이스별로 한 줄씩 띄워주니까 맞았다.. 문제는 연산자 3개로 표현가능한 모든 식을 만들어보고 그 식을 계산했을 때 0인지 판정하면된다. c++에는 eval함수가 없어서 직접 구현했다.. 3. 코드 #include #include #include #..

[백준 - 1629] 곱셈 [C++]

1. 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 2. 풀이 로직은 맞은채로 계속 틀렸다.. 간과하고 있었던 것은 곱셈하면 int 범위를 훨씬 넘어가버린다는 것.. 결국 리턴타입을 long long int로 변경해서 해결.. 이 문제의 핵심 세가지) 1. INT_MAX의 제곱은 long long int 범위에 들어온다. 2. a^5 = a^2 * a^3으로 쪼갤 수 있다. 3. (A * B) % M = ((A % M) * (B % M)) % M; 3. 코드 #include using namespace..

[백준 - 11286] 절댓값 힙 [C++]

1. 문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 2. 풀이 우선순위 큐 비교 컨테이너를 직접 만들어서 껴주면 된다. 3. 코드 #include #include #include using namespace std; struct Compare { bool operator()(int a, int b) const { if(abs(a) == abs(b)) return a > b; return abs(a) > abs(b);..

[백준 - 1931] 회의실 배정 [C++]

1. 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 2. 풀이 끝나는 시간이 빠른 회의를 우선적으로 선택함으로써 남은 시간을 최대한 활용할 수 있게 됩니다. 다시 말해, 어떤 회의가 빠르게 끝나면 그 후에 다른 회의들을 더 많이 배정할 수 있습니다. 예시) 회의 리스트: A: 1-4 B: 3-5 C: 0-6 D: 5-7 E: 3-8 F: 5-9 G: 6-10 H: 8-11 I: 8-12 J: 2-13 K: 12-14 1. 끝나는 시간을 기준으로 오름차순 정렬을 합니다: A: 1-4 B: 3-5 D: 5-7 F: 5-9 G: 6-10 C: 0-6 E: 3..

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

1. 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 2. 풀이 첫 번째 '-' 연산자가 나타날 때까지는 모든 숫자들을 더하고, 첫 번째 '-' 연산자가 나타난 이후의 모든 숫자들은 빼주면 된다. 3. 코드 #include #include #include using namespace std; string expression; string number; int answer; bool isNegative = false; // 1541 /..

[백준 - 15829] Hashing [C++]

1. 문제 https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 2. 풀이 NOTE - ans에서 곱할때 a와 r^i를 곱할때 int 범위를 벗어날 수 있으므로 long long int로 해주어야한다. 나머지 연산의 성질도 알고있으면 좋다.. - (A+B)%M = (A%M + B%M) % M - (AXB)%M = (A%M X B%M) % M - (A-B)%M = (A%M - B%M + M) % M ← 안 쪽에 + M을 해줘야 음수가 안 나오게 됨...