넘치게 채우기

https://www.acmicpc.net/problem/1520BOJ - 내리막 길문제 유형: 다이나믹 프로그래밍, dfs문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB 문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 ..

https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/description/leetcode - Recover a Tree From Preorder Traversal문제 유형: 스택, 트리, dfs, 문자열 처리문제 난이도: Hard 문제We run a preorder depth-first search (DFS) on the root of a binary tree.At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node.  If the depth of a node is D..

https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/description/leetcode - Construct the Lexicographically Largest Valid Sequence문제 유형: dfs, 재귀, 백트래킹, 비트마스킹문제 난이도: Medium 문제Given an integer n, find a sequence that satisfies all of the following:The integer 1 occurs once in the sequence.Each integer between 2 and n occurs twice in the sequence.For every integer i ..

https://www.acmicpc.net/problem/2263BOJ - 트리의 순회문제 유형: 트리, dfs, 분할 정복문제 난이도: Gold I시간 제한: 5초메모리 제한: 128MB 문제n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력첫째 줄에 프리오더를 출력한다. 풀이중위순회의 정보는 노드들간의 좌우관계를 알려준다.후위순회에서의 마지막원소는 항상 루트노드의 값이다.즉, 루트노드를 중위순회..

https://www.acmicpc.net/problem/2583BOJ - 영역 구하기문제 유형: dfs, bfs, 그래프문제 난이도: Silver I시간 제한: 1초메모리 제한: 128MB 문제눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다.와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머..

https://www.acmicpc.net/problem/2098BOJ - 외판원 순회문제 유형: TSP(외판원 순회), 비트마스킹, 다이나믹 프로그래밍, dfs문제 난이도: Gold I시간 제한: 1초메모리 제한: 128MB 문제외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 ..

https://www.acmicpc.net/problem/1707BOJ - 이분 그래프문제 유형: 그래프, bfs/dfs, 이분 그래프문제 난이도: Gold IV시간 제한: 2초메모리 제한: 256MB 문제그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다..

https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/description/leetcode - Maximum Number fof Fish in a Grid문제 유형: bfs/dfs문제 난이도: Medium 문제You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:A land cell if grid[r][c] = 0, orA water cell containing grid[r][c] fish, if grid[r][c] > 0.A fisher can start at any water cell (r, c) and can do the following operati..

https://leetcode.com/problems/find-eventual-safe-states/description/leetcode - Find Eventual Safe States문제 유형: dfs, 위상 정렬문제 난이도: Medium 문제There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in gra..

https://www.acmicpc.net/problem/2606BOJ - 바이러스문제 유형: 그래프, 연결 요소, bfs, dfs문제 난이도: Silver III시간 제한: 1초메모리 제한: 128MB 문제신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때..