알고리즘/Baekjoon

[C++] 백준 1965번 상자넣기

다이나믹 프로그래밍 문제. 어렵게 생각 안하고 풀었는데 틀렸습니다. 를 엄청많이 받고서야 풀었다. 그냥 완전탐색 비슷한 DP 느낌의 문제였다. 문제풀이 내가 푼 방식은 다음과 같다. 1번째 상자 ~ N번째 상자를 탐색한다. i번째 상자를 탐색하면서 자기 앞에 있는 상자들(1 ~ i) 중 가장 많이 담을 수 있는 상자를 골라서 + 1 해준 후 현재 상자가 최대 이만큼 담을 수 있다는 것을 기록해놓는다. 상자들 중 몇번째 상자가 가장 많이 기록할 수 있는지 출력한다. #include #include using namespace std; int boxCnt; int boxSize[1001]; int dp[1001]; int ans = 1; int main() { ios_base::sync_with_stdio(..

[C++] 백준 1890번 점프

다이나믹 프로그래밍 문제. 처음에 Bottom-Up 방식으로 시도했는데 틀렸다. Top-Down 방식으로 풀었을 때에도 방문처리를 안했어서 틀렸다. [C++] 백준 1520번 내리막 길 그래프 탐색 + 다이나믹 프로그래밍 문제 사실 이 문제를 본 건 엄청 오래 전이였는데, 그 당시엔 못 풀었었다. (검색도 했었는데, 그냥 이렇게 푸는거구나. 만 알고 넘어감. 바로 풀면 의미가 없 kimyunseok.tistory.com 위 문제와 거의 유사한 문제이다. 난이도는 왜이렇게 차이나는지는 모르겠지만, 위 문제를 풀 수 있다면 이 문제도 풀 수 있다. 문제풀이 다이나믹 프로그래밍의 TOP DOWN 방식과 DFS과 비슷한 로직을 혼용해서 풀었다. (1, 1)에서 시작해서 오른쪽, 아래쪽 방향으로 가면서 (r, c..

[C++] 백준 5014번 스타트링크

그래프 탐색 중 너비 우선 탐색으로 푸는 문제. [C++] 백준 1107번 리모컨 브루트 포스 완전탐색 문제. 이 문제는 두 번 풀게됐는데, 처음에 푼 완전탐색 코드에서 시간이 다른 사람들에 비해 너무 많이 나와서 백준 게시판을 참고해서 다시 풀게됐다. 정답 비율이 낮지 kimyunseok.tistory.com 위 리모컨 문제와 똑같은 문제였다. 예전에 푼 로직이 생각나서 바로 풀 수 있었다. 문제풀이 리모컨 문제와 아주 유사한 문제이다. BFS를 하게 되는데, 현재 층에서 위, 아래 층이 유효한 층이고 방문하지 않았다면 다음 층을 큐에 넣어주면서 계속 탐사하게 구현하면 된다. /* * 백준 5014번 스타트링크 * https://www.acmicpc.net/problem/5014 * 그래프 탐색 이론 ..

[C++] 백준 1167번 트리의 지름

[C++] 백준 1967번 트리의 지름 그래프 탐색 문제. 처음에 그냥 정점마다 DFS를 모두 돌려서 제출했는데 맞췄다. (시간 복잡도를 계산해도 가능할 것 같았다.) 그런데 문제가 의도하는 바가 이것도 아닌 것 같고, 제출 내역에 다 kimyunseok.tistory.com 위 문제와 거의 똑같은 문제. 차이점이라면, 루트 노드가 1이 아니다. 정점 번호가 작은 순서부터 입력되는 것이 아니라 랜덤으로 입력된다. -1이 나오기 전까지 노드를 연결시킨다. 정도가 되겠다. 3번 차이점은 사실 크게 중요하지는 않다. 위에 링크를 남긴 문제를 풀었다면 이 문제도 아마 크게 어렵지 않게 풀 수 있다. 문제풀이 자세한 풀이는 생략하겠다. (위 비슷한 문제와 거의 똑같은 방식으로 풀었다.) 우선, 루트 노드가 무엇인..

[C++] 백준 1967번 트리의 지름

그래프 탐색 문제. 처음에 그냥 정점마다 DFS를 모두 돌려서 제출했는데 맞췄다. (시간 복잡도를 계산해도 가능할 것 같았다.) 그런데 문제가 의도하는 바가 이것도 아닌 것 같고, 제출 내역에 다른 사람들 시간을 보니 다시 풀어야 겠다고 생각해서 다시 풀어서 제대로 맞출 수 있었다. DFS를 자유자재로 변형할 수 있으면 쉽게 맞출 수 있는 문제였다고 생각한다. 문제풀이 우선 처음 이 문제를 풀었을 때, 정점의 개수가 최대 10,000개인 것을 확인했고 간선의 개수가 최대 9,999개인 것을 확인했다. 각 정점마다 DFS를 한 번 하는데 소요되는 시간은 모든 정점을 방문했을 때, O(N)의 시간이 소요된다. 그러면 모든 정점에서 DFS를 한다면 총 소요되는 시간은 O(N^2)이다. N은 최대 10,000이..

[C++] 백준 1520번 내리막 길

그래프 탐색 + 다이나믹 프로그래밍 문제 사실 이 문제를 본 건 엄청 오래 전이였는데, 그 당시엔 못 풀었었다. (검색도 했었는데, 그냥 이렇게 푸는거구나. 만 알고 넘어감. 바로 풀면 의미가 없으므로!) 이번에 학교에서 주최한 프로그래밍 대회에서 비슷한 문제를 봤었는데, 이 문제에 대한 기억이 떠올라서 검색해서 비슷한 문제를 맞춘 후에 다시 풀어봤다. 그래프 탐색 이론과 DP (Top-Down)방식을 사용하는 문제가 있다니 신기했다. 문제풀이 결국, (1, 1)에서 (M, N)까지 몇 개의 길이 있는지를 구하는 문제다. 나는 지금까지 DP는 Bottom-Up 위주로 많이 풀었었는데 이 문제는 지금 (1, 1)에서 알 수 있는 경우의 수가 없다. 그런데 (M, N)에서 (M, N)으로 가는 경우의 수는 ..

[C++]백준 1806번 부분합

투 포인터 문제. 바로 이전에 풀었던 2230번 수 고르기 문제와 비슷한 유형의 문제이다. 정렬하지 않고 푸는 투 포인터 문제이다. 문제풀이 연속된 수들의 합 중에서 길이가 가장 짧은 것을 구하면 된다. 나같은 경우에는, front, tail(lo, hi)를 둘 다 0으로 초기화 시켜놓고 front부터 tail까지에 속하는 모든 원소의 합을 통해서 조건을 만들었다. 반복문은 front > numCnt >> minSum; int input; for (int i = 1; i > input; numVec.push_back(input); } int front = 0; int tail = 0; int curSum = numVec[0]; while (front = minSum) { ans = min(ans, tai..

[C++] 백준 2230번 수 고르기

투 포인터 문제. 투 포인터 문제를 오랜만에 풀었는데 틀렸다. 틀린 이유 위주로 정리하겠다. 문제 풀이 수열의 길이는 최대 100,000이다. 만일 한 index마다 끝까지 탐사하게 될 경우 시간 복잡도가 100,000 x 100,000이 되므로 10,000,000,000번의 연산을 하게된다. 이는 시간 초과가 발생할 것이다. 따라서 다른 방법을 생각했는데, 투 포인터 방법이 생각났다. 투 포인터는 한 줄의 배열이 있을 때 두 개의 포인터를 두어서, 포인터를 front, tail (혹은 lo, hi)로 두어서 포인터만 이동시키면서 푸는 방식이다. 이 문제는 최소의 차이를 구해야 하므로 정렬 시킨 후 투 포인터로 탐색해서 풀면 된다. 주의할 점은 고르는 두 수가 같은 수일수도 있다. A[i]를 두 번 고르..

[C++] 백준 2110번 공유기 설치

이분 탐색 문제. 시간 복잡도가 이게 되나? 생각되는 문제지만 이분 탐색 + 되는지 순차적으로 확인 해주면 풀리는 문제이다. 많이 틀렸었는데, 이유는 이분탐색 최소부분을 1부터 시작하지 않고 집의 번호들 중 가장 작은 부분부터 시작해서 틀렸다. 문제풀이 이분 탐색을 하면서 나오는 숫자들을 하나씩 가능한지 여부를 살펴보면 된다. 이분 탐색은 늘 그렇듯 front < tail일 때까지 고려해주면 된다. front는 1로 시작해야한다. 처음에 이 부분을 간과해서 집 번호 중 가장 작은 부분부터 시작해서 틀렸다. 만일 집이 3개가 있고 2개의 공유기를 설치한다고 해보자. 집의 번호가 각각 10000, 10001, 10002 이렇게 있다면 가장 멀리 공유기를 설치하는 법은 10000, 10002 이렇게 된다. 따..

[C++] 백준 1707번 이분 그래프

그래프 탐색 문제. 처음에 진짜 말도 안되는 방법으로 구현했다가 틀렸다. (아무 생각없이 풀어버렸다.) 근데 또 예제들은 잘 나와서 뭐가 틀렸는지 몰랐는데 반례 게시판에 나와있는 반례를 통해 해결했다. 이번에 대회에 이분 그래프 문제가 나왔었는데,(사실 이분 그래프보다는 심화적인 내용이였다. 당연히 못풀었음ㅠ) 이분 그래프 문제는 유명한 문제 같아서 이번에 풀어봤다. 문제풀이 문제내용에 따르면 그래프에서 인접하지 않은 정점들끼리 집합을 나눌 수 있는 그래프인지 여부를 확인하면 된다. 그래프에서 정점에 색을 칠하는데, 인접한 정점끼리는 다른 색을 가지게 되면 해당 그래프를 이분그래프라고 할 수 있다. 나는 이 문제를 내가 빨간색, 파란색 붓만 가지고있고, 색칠되지 않은 정점에 빨간색 붓을 칠하면서 시작하고..