발자취

문제를 읽어보고 오자. https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제를 읽어 보면 그래프 탐색을 사용하는 문제인 것을 알 수 있다. 하지만 약간 까다로운 점은, 특정 조건의 이동을 특정한 횟수 안에 실행한다는 점이다. 이것에 대한 모든 경우를 세야 할까? 나는 처음에 말처럼 움직인 횟수를 큐에 저장해서 확인해 보았다. 하지만 이러한 방법을 사용하니 방문한 경우에 대해서 오류가 있다는 것을 알게 되었다. 벽 부수기 문제 (..

문제 설명을 잘 읽어보자. https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 빗물이 고이는 특성은 다음과 같다. 1. 좌측 끝과 우측 끝이 벽으로 막혀 있어야 한다. 2. 빗물이 찼을 때 양쪽 끝이 같다. 3. 중간에 구멍이 생길 일은 전혀 없다. (주어진 조건이 밑에서부터 위로 몇 칸 있는지 확인하므로) 이러한 특징을 기반으로 다음과 같은 풀이 알고리즘을 생각해 보았다. 1. 수면의 높이가 1~N 일때까지 탐색한다. 2. 물이..

문제 설명을 보고 오자. https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 이 문제는 백트래킹을 이용한 탐색 문제이다. 조건을 생각하는 구성이 복잡하지만, 역할을 잘 나누면 풀이가 한결 편해질 것이다. 인접한 두 개의 부분 수열이 동일한 것이 있으면, 해당 수열은 나쁜 수열로 다음 경우의 수로 넘어가야 한다. 그렇게 하기 위해서는 한 자리에 1~3이 들어가며, 조건에 맞으면 다음 과정을 탐색할 수 있는 백트래킹 기법으로 풀이하면 될 것이다. 탐색하는 함수를 ..

문제를 잘 읽어보고 오자. www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 이 문제도 평범한 그래프 탐색 문제이다. 주어진 사람들 중에 가장 많은 2-친구를 보유한 사람의 수를 출력하면 된다. 문제 읽어보면 복잡해 보이지만, 그냥 bfs로 탐색할 경우에 깊이가 2인 노드의 수를 체크하면 된다. 문제 분류에 플로이드-와샬 이라는 태그가 있는데, 사실 이거 뭔지 모르겠다. 몰라도 풀리긴 하는데, 나중에 한번 살펴봐야 할 듯 하다. 문제 풀이 구상을 간단히 해보자. ..

문제를 살펴보고 오자. www.acmicpc.net/problem/1325 > N >> M; while (M--) { cin >> a >> b; v[b].push_back(a); } ans = 0; for (int i = 1; i

문제에 대한 설명은 아래 링크를 들어가서 확인하도록 하자. www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 이 문제는 단순한 탐색 문제로 볼 수도 있다. Z 방향대로 탐색하여 탐색할 좌표의 번호를 출력하면 된다. 하지만 0부터 N까지 모조리 탐색해 버리면 시간초과가 뜬다. 그렇다면 어떻게 접근하는 것이 좋을까? 답은 확실하게 공간을 차지하는 곳에 대해서는 탐색을 진행하지 않는 것이다. 다음 사진을 예시로 들어 보자. 입력이 3 3 7 일 경우를 생각해..

'치즈' 라는 이름을 가진 문제가 2개 있다. 두 문제는 다른 문제이다. 링크에 들어가서 2638 '치즈' 문제의 설명을 보고 오자. www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 기존의 2636 '치즈' 의 문제랑 상당히 유사하다. 하지만 다른 점이 있다면, 치즈의 2면 이상이 공기랑 접촉해 있을 때, 치즈가 사라진다는 조건이다. 치즈가 2면 이상 공기랑 접촉해 있는 것을 어떻게 알 수 있을까? 답은 2번 방문했을 경우를 예외로 두면 된다. 2번..

링크를 들어가서 문제의 설명을 읽어보고 오자. www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 이 문제는 bfs를 적절히 활용하면 쉽게 풀리는 문제이다. 공기라고 판단되는 칸 부터 bfs를 실행하여, 한 면이라도 치즈에 닿으면 없애버리면 된다. 이러한 과정을 반복하면서, 치즈가 사라질 때 까지 반복하면 간단히 풀리는 문제이다. bfs 탐색의 시작점은 (0,0) 으로 정했다. 항상 (0,0)은 공기이기 때문이다. 이 코드에서는 loc라는 구조체를 선언하여 좌표의 정보를..

이번 문제에서 가장 큰 정사각형을 구하기 위해서 모든 경우의 수를 하나씩 탐색한다면, 이 문제를 풀 수가 없다. 최대 크기의 사각형에서 모든 경우의 수를 다 구하기 위해서는 방법이 무지막지하게 많아진다. 그렇다면 다른 방법은 무엇이 있을까? 답은 다이나믹 프로그래밍을 이용하는 것이다. 다이나믹 프로그래밍을 이용하여 시간복잡도 O(NM) 으로 풀이가 가능하다. 예시를 보면서 풀이 방법에 대하여 천천히 알아보자. 예시로 보여준 그림이 있다. 탐색 순서는 위에서 아래로, 좌측에서 우측으로 이동하며 탐색한다. dp 배열은 입력으로 들어온 배열과 크기가 같다. 첫번째 붉은색 상자를 보자. 상자 안에는 0이 2개, 1이 2개 있다. 해당 칸은 정사각형을 이룰 수 있는가? 답은 이룰수 없다. 이렇게 된 결과를 dp ..

너비 우선 탐색을 살짝 응용하면 되는 문제이다. 문제를 보면 노드의 수 (동기의 수), 주어지는 노드간 연결관계의 수 (리스트의 길이), 노드간 연결관계 (친구 관계) 가 주어진다. 이를 이용하여 문제를 풀 수 있다. 너비 우선 탐색 문제를 풀기 위해서는 너비 우선 탐색에 관한 알고리즘의 이해가 필요하다. 2중 반복문을 이용해서 풀 수도 있으나, 너비 우선 탐색을 사용하는 것이 다른 문제에 응용하기 좋다. 너비 우선 탐색은 그래프 탐색에 사용된다. 목표 지점에 도달하기 위해서 경로를 탐색하되, 출발점에서 같은 거리의 노드를 탐색한다. 여기에는 큐가 필이 사용된다. bfs의 기본 원리는 다음과 같다. 시작 노드를 queue에 저장한 후 bfs 탐색을 실행한다. 큐에 있는 노드를 pop 한 후 해당 노드에 ..