개발 블로그

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 오랜만에 알고리즘 트리 문제를 풀어봤습니다. 이 문제는 트리에서 임의의 두 정점 사이의 가장 긴 거리를 출력하는 문제입니다. 입력의 경우 시작 정점(from)이 주어지고, 시작 정점과 연결된 정점(to)과 두 정점 사이의 거리(dist)를 입력으로 받습니다. 더불어 해당 정점에서 입력을 종료하려면 -1을 입력으로 받아야 합니다. 첫 번째로, 우선 임의의 정점에서 가장 거리가 먼 노..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 트리(tree)란 ? 그래프(Graph)의 일종으로, 한 노드에서 시작해 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프입니다. 최상단 노드를 루트노드, 자식이 없는 노드를 리프노드라고 합니다. 이 문제는 노드의 개수 n이 주어지고, n에 해당하는 부모노드 인덱스를 입력으로 받습니다(부모 노드가 없는 경우에는 -1) 마지막으로 삭제할 노드를 입력 받고, 이러한 과정을 ..

https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 이 문제는 동전을 하나만 떨어뜨리기 위한 최솟값을 구하는 문제입니다. 만약 횟수가 10번 넘기거나, 동전이 둘 다 떨어지는 경우는 -1을 출력해야 합니다. 코드로 설명드리겠습니다. #include #include using namespace std; int n, m; string a[20]; int mov[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; int go..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 이 문제는 DFS + 백트래킹 문제입니다. 보자마자, DFS보다 백트래킹 먼저 생각했습니다. 왜냐하면, 모든 말이 지날 수 있는 최대 칸수를 구해야 하기 때문입니다. 그래서 DFS로 탐색하면서, 조사한 모든 경우의 수(말이 지날수 있는 모든 경우의 수)들 중 최댓값을 구해주면 됩니다. #include #include using namespace std; char board[21][21]; ..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 백준 골드5 난이도이고, 비교적 간단한 DFS 였습니다. 적록색약인 사람(빨강, 초록 구분 x)이랑, 적록색약이 아닌 사람(빨강, 초록 구분 o)의 DFS 함수를 각각 따로 만들어주었습니다. 적록색약인 사람의 경우에는 기준점이 빨강이면, DFS함수를 돌렸을 때 상하좌우의 배열값이 빨강이랑 초록이면 DFS함수를 재귀적으로 돌려주는 방향으로 알고리즘을 설계하였습니다. 그렇지 않은 경우(파랑)일..