알고리즘 (30) 썸네일형 리스트형 [백준] 1766번 문제집 [C++] https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 접근 방식 위상정렬과 우선순위 큐를 이용하여 문제를 풀었다. 우선순위 큐를 쓰는 이유는 3번조건인 난이도가 쉬운 문제부터 풀어야 하기 때문에, 푸는게 가능한 문제중에서 가장 숫자가 작은 숫자부터 풀기 위해서이다. 먼저, X번의 문제를 풀기위해서 선행적으로 풀어야 하는 문제들이 i개 있다고 생각하자. 그렇다면 이 i의 값이 0이 되는 문제는 선행으로 아무것도 풀지 않아.. [백준] 1005번 ACM Craft [C++] https://www.acmicpc.net/problem/1005 문제 접근 방법 위의 그림을 예시로 들어 설명하자면 , 3번을 짓기 위해서는 1번이 선행적으로 건설이 되어 있어야 한다. 이러 한 경우에 3번까지 짓는데 걸리는 시간은 1번을 짓는데 걸리는 시간+3번을 짓는데 걸리는 시간이 된다. 4번을 짓기 위해서는 2번과 3번이 선행적으로 건설이 되어 있어야 한다. 여기서 2번을 짓는데까지 걸리는 시간과, 3번을 짓는데까지 걸리는 시간이 다를텐데, 두개 다 완성이 되어야 4번 건설 시작이 가능하므로 둘 중 큰 값을 구해야 한다. 따라서 max(2번까지 걸리는 시간,3번까지 걸리는시간)에 4번을 짓는데 걸리는 시간이 4번까지 짓는데 걸리는 시간이다. 이러한 식으로 X번 건물을 지을 때 선행적으로 지어야 .. [백준] 1167번 트리의 지름 [C++] https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 접근 방법 트리의 지름이란 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 먼저 이 두 점을 찾기위해서는 임의의 한 점에서 DFS를 해서 가장 멀리 있는 점을 찾아낸다. 그 점은, 내가 처음에 임의로 지정한 점이 지름에 포함되어있든, 아니든 지정한 점으로부터 가장 먼 거리에 있기 때문에, 트리의 지름에 포함된 점이라고 할 수있다. 이렇게 찾아낸 점에서 부터 다시 DFS를.. [백준] 2206번 벽 부수고 이동하기 [C++] https://www.acmicpc.net/problem/2206 문제 접근 방법 BFS를 통해 문제를 해결하였다. 중요한점은 벽을 부술 수 있는 경우가 딱 한번 있다는 점이다. 따라서 다른 BFS 문제들과 다르게 해당 경우가 벽을 부수고 들어간 경우인지, 아닌지를 구분을 해야한다. 벽을 부수고 들어간 경우일 때, 벽을 만나면 더 진행을 못하지만, 벽을 부수고 들어간 경우가 아니라면 벽을 만나도 한번 통과가 가능하다. 이러한 구분은 큐에 위치값(x,y)이외에도 큐에 들어온 경우가 벽을 부쉈는지, 아닌지 구분할 bool 변수까지 포함을 시키면 된다. 따라서 큐에서 상하좌우를 판별할때 벽을 이미 부수고 들어왔을 경우 상하좌우 벽을 부순 상황에서 한번도 방문을 안 했고, 벽이 아닐 때의 x,y값과 벽을 이미 .. [백준] 1937번 욕심쟁이 판다 [C++] https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제 접근 방법 판다는 기본적으로 현재 내 위치보다 대나무의 수가 적은곳에서 현재 위치로 이동이 된다. 주위에 현 위치 보다 대나무가 적은 곳이 없어서 현재 위치로 이동할 수 있는 경로가 없다면 그 곳으로 갈 수 있는 경로는 오직 그 위치에서 시작하는 경우 한 개이다. 따라서 위의 경우는 dp라는 array에 1이라는 값을 정해두고, 주위에 현 위치보다 대나무가 적은 곳이 있는 곳까지 .. [백준] 1039번 교환 [C++] https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 접근 방법 BFS를 이용하여 문제를 해결하였다. 먼저 , 0번 교환했을 때의 초기 문장을 큐에 넣고, 그 안에서 각각의 자릿수를 교환한 문장을 만든후 큐에 넣어준후 팝 해준다. 그 후 1번 교환했을때의 문장들이 Q에 있으므로, 다시 자릿수를 교환한 후 큐에 넣어준 후 팝해준다. ...를 N번 교환까지 진행 해 준다. 큐에 넣을때 예외처리 해 줄 부분이 있는데 교환 한 후 문장의 맨 처음이 0일 때 문장의 길이가 1이여서 교환을 할 수 없을때 는 각각 "-1"을 .. 이전 1 2 3 4 다음
