링크: https://www.acmicpc.net/problem/2096문제어떤 칸을 선택하면 선택 가능한 다음 칸이 정해지는 점에서 9465번 - 스티커와 굉장히 유사합니다. 사실 동일한 풀이로 해결되지만 다른 점이 있습니다.이 문제는 메모리의 제한이 4MB로 엄청 작다는 겁니다.적은 메모리 제한때문에 스티커 문제처럼 dp[3][N] 과 같은 배열을 선언할 수도 없고 재귀 함수까지도 염려해야하는 상황입니다. 그럼 어떻게 해결해야할까요?풀이어떤 r번째 줄에서 어떤 칸을 선택한다면, 이는 다음 줄인 r+1번째 줄에 영향이 갑니다. 어떤 칸을 선택할 때, 항상 2개의 줄만 확인하면 된다는 점으로 메모리를 줄일 수 있습니다. 왜냐하면 1번째 줄은 2번째 줄에 영향을 주고 2번째 줄은 3번째 줄에 영향을 주지만..

링크: https://www.acmicpc.net/problem/16964풀이문제의 가장 큰 힌트는 입력된 그래프의 모양이 트리라는 점이다. 즉, 사이클이 없다. 올바른 DFS 방문 순서가 되기 위해서는 자식이 부모보다 먼저 나오는 경우가 있어서는 안된다.이 특징을 살리면, 어떤 순서 \(i\)번째에 등장하는 노드 \(x\)의 깊이는 어떤 순서 \(i\)+\(x\)의 서브트리의 크기까지는 전부 그 노드의 자식이라는 점이다. 위 그림처럼 입력이 주어졌다고 해보자.여러 DFS 방문 순서가 가능하겠지만, 그 중 하나인 [1, 3, 5, 8, 6, 4, 7, 9, 2]의 순서를 예로 들자면 어떤 \(i\)번째 순서에 있는 노드 \(x\)는 자신의 서브트리의 크기만큼 다음 순서가 자신의 형제 노드이다.2번째 순서..

링크: https://www.acmicpc.net/problem/11447문제문제에서 정의되는 x, y, z 방향으로 1000을 넘지 않는 길이만큼 C번 움직인 후에, 마지막에 완성된 그림 속에 채워지는 삼각형의 수는 몇 개인지 맞추는 문제이다.삼각형들은 빈 공간이 없이 빽빽하게 채워져있고, 다시 시작점으로 돌아오지 않는 잘못된 입력은 주어지지 않는다. 처음에는 x,y,z 방향을 2차원 x,y 평면으로 적당히 전사시켜서 그 넓이를 구하는 방식으로 해야하나? 라는 생각을 했다. 그 외에도 문제를 변형시키는 별 생각을 다 했는데 결국 풀이는 다각형의 면적을 구하는 문제였다.풀이다각형을 이루는 꼭짓점들이 주어지면, 그 다각형의 면적을 구하는 문제이다. 이건 신발끈 공식으로 해결할 수 있다. 다각형의 각 꼭짓점..

링크: https://www.acmicpc.net/problem/1976문제\(n\)개의 도시 사이의 연결 상태가 인접 행렬로 주어지고 여행 계획에 있는 \(m\)개의 도시가 주어질 때, \(m\)개의 도시를 모두 방문할 수 있는가를 묻는 문제이다. 다시말하면, \(m\)개의 도시가 모두 연결되어있는가를 확인하면 된다. 이 문제는 서로소 집합(Disjoint-Set)으로 간단하게 해결할 수 있다. 각 도시들의 연결 상태만 확인하면 되므로, 연결된 도시들을 집합으로 묶어서 표현한 후 마지막에 주어지는 \(m\)개의 도시들이 모두 같은 집합에 속하는 지 확인하면 정답이기 때문이다.코드

링크: https://www.acmicpc.net/problem/1613이전 풀이: http://joonas-yoon.blogspot.com/2016/04/1613.html문제알고 있는 사건의 전후 관계를 방향성이 있는 간선으로 보면, 서로 다른 두 사건을 유추한다는 것은 어떤 방향으로건 일단 연결이 되어있는가를 물어보는 것이다. 방향 그래프에서 정점 a에서 b로 갈 수 있는 경로가 있는 지 물어보는 문제이다. a에서 b로 가는 경로가 있으면 앞에 있는 사건이 먼저 일어난 것이므로 -1b에서 a로 가는 경로가 있다면 1, 경로가 없다면 0을 출력하면 된다. 문제는 이러한 물음이 한두번이 아니라 s번(최대 50,000번) 물어보기 때문에, 경로를 빠르게 찾을 수 있어야한다. n이 400으로 작으므로 플로이..

링크: https://www.acmicpc.net/problem/9465예전 풀이: http://joonas-yoon.blogspot.com/2014/08/9465.html풀이한 스티커(칸)를 선택하면 인접한 칸은 선택할 수 없게 된다.그럼 대각선만 남게 되는데, 그 대각선 칸도 위 선택을 반복하게 된다. A B C DE F G H 만약 위와 같이 있다고 생각해보자. A를 고른다면 C, D, F, G, H 중에 골라야한다. E를 고른다면 B, C, D, G, H 중에 골라야한다.바로 다음 칸(열)에만 영향이 있고, 그 이후의 C, D, G, H를 고민하는 것은 변함이 없다. 즉 어떤 i번째 열을 볼때, i+2번째 이후의 열은 영향이 없다는 뜻이다. i번째 열에서 고민할 점은 3가지이다. 1. 고르지 않는..

링크: https://www.acmicpc.net/problem/10472문제각 칸이 색칠된 상태를 0/1로 보면, 3x3 크기의 보드는 크기가 9인 상태공간을 가진다.따라서 나타날 수 있는 보드의 상태의 수는 \(2^{9}\) = 512가지이다. 최초 보드의 상태에서 각 칸을 눌러보며 매번 9번의 상태 분기가 일어나는 BFS 탐색으로 해결 가능하다. 어떤 상태를 이미 확인했는 지에 사용되는 visit 배열은 취향에 따라 여러 형태가 가능할 것이다. 나는 000 000 000의 크기 9짜리 상태 공간을 2진법으로 변환하여 int 변수로 표현하였다. 그래서 visit[bit]로 했는데, key-value를 쓰면 string형으로 "000111000"처럼 저장할 수도 있다.어찌되었건 중요한건 중복 확인을 할..

링크: https://www.acmicpc.net/problem/1939 문제어떤 정점 S에서 다른 정점 E까지 가는 경로에서 등장하는 간선의 가중치의 최대값을 구하는 문제입니다. 최단 경로를 살피는 것이 아니라, 최대한 무거운 것을 옮기기 위한 다리만 선정한 경로를 만들어야하므로 최소 스패닝 트리의 반대인 최대 스패닝 트리가 떠오릅니다. 일반적으로 크루스칼 알고리즘은 최소 스패닝 트리를 위해 사용되지만, 이 경우에는 반대로 최대 스패닝 트리를 위해 사용할 수 있을 것 같습니다. (음수 가중치도 없으니 가능해보입니다.) 연결되지 않은 간선 중 가중치가 가장 큰 간선을 선택하면서 스패닝 트리를 만들어가면, 어떤 정점 S와 다른 정점 E이 같은 "연결된 집합"에 속하는 그 순간에 우리가 원하는 경로가 완성됩..