복습 정리 노트

푼 사람 수가 많은 그리디 문제들 중에서, Solved.ac 기준 Gold 티어 이상의 그리디 문제들을 풀이해보았습니다. 백준 BOJ 2437번 : 저울 N개의 추의 무게가 주어졌을 때 자연수 무게 중 측정할 수 없는 가장 작은 무게를 구하는 문제입니다. 문제를 처음에 보았을 때는 백준 BOJ 2629번 : 양팔저울 문제가 생각이 났습니다. ↓ 풀이는 아래에 있으며, 간략히 설명하자면 dp + 재귀적 탐색으로 풀이하는 문제입니다. [백준/BOJ] 2629번 : 양팔저울, 2293번 : 동전 1, 7579번 : 앱 (DP, 동적 계획법 중급) 이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2629번 : '양팔저울', 2293번 : '동전 1', 7579번 : '앱' 문제의 ..

백준 BOJ 2618번 : 경찰차 N×N 크기의 도로가 있고 1번 경찰차는 (1, 1), 2번 경찰차는 (N, N)의 위치에 있다고 합니다. W개의 사건이 일어나는 좌표가 주어질 때, 두 개 중 하나의 경찰차를 움직여 해당 좌표로 이동을 시켜야하며 이 때 반드시 사건이 발생한 순서대로 이동이 발생해야합니다. 이동한 경찰차는 해당 좌표에 머물러 있다가 다음 이동에 그 자리로부터 이동한다고 할 때, W개의 사건을 모두 해결하는데 필요한 두 경찰차 이동 거리의 합의 최솟값과 그 때 이동한 경찰차의 번호를 순서대로 구하는 문제입니다. dp[i][j]를 1번 차가 마지막으로 i번째 좌표에 이동했고, 2번 차가 마지막으로 j번째 좌표에 이동했다고 했을 때 "앞으로 가야할 최소 거리"라고 정의합니다. dp[i][j]..

날마다 아무거나 골라서 풀고 있는데 어쩌다보니 또 다시 투 포인터(two pointer) 알고리즘 문제를 풀게 되었습니다. 문제가 나쁘지는 않은 것 같아 가지고 와봤습니다. 백준 BOJ 20922 : 겹치는 건 싫어 길이 N의 수열과 정수 K가 주어질 때, 이 수열에서 같은 정수를 K개 이하로 포함한 연속 부분 수열들 중 가장 긴 것의 길이를 출력하는 문제입니다. 시작점과 끝점의 위치를 각각의 변수로 놓고 생각하면 N * (N-1) / 2개의 경우의 수를 모두 해보면 좋겠지만, 이는 O(N^2) 알고리즘이므로 시간 초과가 발생하게 됩니다. 따라서 다음과 같이 투 포인터 알고리즘을 사용하여 구간을 탐색하는 것이 바람직합니다. 문제에서 주어진 예제 입력으로 알고리즘을 설명하자면, i와 j를 모두 시작점에 놓..

특이한 방식으로 해결하는 문제가 있어 풀이하기 위해 가져왔습니다. 백준 BOJ 2749번 문제인 '피보나치 수 3' 문제로, 풀이 코드를 작성하기 전 미리 별도의 코드를 작성하여 풀이에 대한 정보를 찾아야 하는 문제입니다. 백준 BOJ 2749 : 피보나치 수 3 피보나치 수의 0번째 항을 0, 1번째 항을 1로 두며, f[i] = (f[i-1] + f[i-2]) % 1000000라고 정의할 때 10^18 이하 번째의 피보나치 수의 값을 찾는 문제입니다. 피보나치 수를 K로 나눈 나머지는 항상 주기를 가진다는 성질이 있고, 이 때의 주기를 '피사노 주기'라고 합니다. 다만 우리는 이 성질을 모르더라도 아래와 같이 주기를 찾기 위해 시도를 해볼 수는 있습니다. #include #define MOD 1000..

백준의 단계별로 풀어보기의 '최단 경로' 단계에서, 각종 최단 경로 알고리즘들을 사용하여 문제들을 풀어보도록 하겠습니다. 이 포스트에서 다룰 알고리즘은 순서대로 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와셜 알고리즘입니다. 백준 Online Judge에서 풀어볼 문제들은 순차적으로 BOJ 9370 : '미확인 도착지', BOJ 11657 : '타임머신', BOJ 11404 : '플로이드'입니다. 다익스트라 알고리즘 (BOJ 9370 : 미확인 도착지) 가장 먼저 풀어볼 문제는 다익스트라 알고리즘을 사용하는 문제입니다. 문제를 요약해보면, 정점들을 이은 간선들의 번호 및 거리가 주어지고, s에서 출발하여 g, h를 거쳐 목적지의 후보지까지 갈 때, 만약 s에서 목적지 후보까지의 거리가 같다면 그..

백준 BOJ의 13714번 문제인 '괄호'의 풀이를 해보겠습니다. Solved.ac 기준 Diamond IV의 난이도에 해당하는 문제이고, 문제 분류는 '조합론'으로 되어있습니다. BOJ 13174 : 괄호 올바른 괄호 문자열을 ( ) ( ( ) ( ) )과 같이, 괄호가 문법에 어긋나지 않게 열고 닫힌 문자열이라고 정의합니다. 이러한 괄호 문자열 중에서 길이 2N인 "대칭" 괄호 문자열에 대해서 생각해봅시다. 열고 닫는 괄호의 쌍에 맞게 K가지 색을 이용하여 괄호의 색을 칠한다고 할 때, 존재하는 괄호 문자열의 수는 몇 가지가 있는지 구하여 그 값의 mod 1,000,000,007을 구하는 문제입니다. 문제에 대한 더 자세한 설명과 조건은 BOJ의 13174번 문제를 직접 참고하시면 좋을 것입니다. 여..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge BOJ 17318 Highway Cycling 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Diamond I이며, 문제를 풀이하기 위해 라그랑주 승수법(Lagrange Multiplier Method)에 대한 배경지식과 이분탐색의 활용에 대한 이해가 필요합니다. BOJ 17318 Highway Cycling 17318번: Highway Cycling DanDan is always interested in challenging himself. This summer, he prepares to cycle along the Sichuan-Tibet highway to reach Lhasa. It is wi..

이 포스트는 C++에서 getline으로 입력받을 때, EOF 조건문 (ex : while(cin.eof())) 없이 입력이 더 이상 주어지지 않을 때 프로그램을 종료 처리하는 방법에 대해 다루고 있습니다. 구체적인 예시를 들어 설명하기 위해 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 10820번 : '문자열 분석' 문제를 같이 풀이하도록 하겠습니다. 먼저 문제를 풀이하기 전에 결론부터 정리하자면, while(getline(cin, str))과 같이 getline문을 그냥 whlie문의 조건문 안에 넣어버리면, 입력이 종료되고 EOF 시그널이 전달됨과 동시에 getline 함수 자체가 false를 반환하므로 자동 종료가 됩니다. 따라서 while(cin.eof()) { string s..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 3474번 : '교수가 된 현우', 22864번 : '피로도', 13458번 : '시험 감독' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Bronze ~ Silver 티어에 해당하며, 랜덤으로 문제를 골라 풀이하는 중이므로 카테고리 역시 랜덤입니다. 3474번 : 교수가 된 현우 N!이 10의 몇 제곱을 약수로 가지는지 구하는 문제입니다. 1 ~ N의 수에 대해 2와 5 약수의 개수를 모두 count 해주는 방법이 가장 쉽겠지만, 시간 초과가 발생하므로 더 빨리 구할 수 있는 방법을 찾아야합니다. #include using namespace std; int main() { ios_base::sync_with_s..

이 포스트에서는 자료구조 중 하나인 해시맵을 C++에서 활용하여 리스트에 문자열들을 저장하고, 해당 리스트에 어떤 문자열이 존재하는지를 검사하는 기능을 간단하게 구현해보는 내용을 다루고 있습니다. 예시로 풀어볼 문제는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 14425번 : '문자열 집합'입니다. 14425번 : 문자열 집합 N개의 문자열로 이루어진 집합을 S라고 할 때, M개의 문자열을 입력받아 그들 중 집합 S에 포함되는 문자열이 몇 개나 존재하는지를 구하는 문제입니다. 집합에 포함된다는 것은 해당 문자열과 완전히 일치하는 문자열을 원소로 가지고 있다는 것을 의미합니다. 이 문제는 대표적인 해시맵 활용 예제로, 해시맵을 활용하여 문제를 해결해보도록 하겠습니다. #include u..