본문 바로가기

분류 전체보기

 (146)
[ BOJ 백준 4256번 - 트리 ] 해설 및 코드 https://www.acmicpc.net/problem/4256 목적 이진트리의 전위 순회와 중위 순회 결과가 주어졌을 때, 후위 순회 결과를 구하자. 접근법 1. 다음 그림을 보자. 3은 루트 노드, 파란 부분과 노란 부분은 각각 루트 노드의 왼쪽과 오른쪽 노드들이다. 세번째 후위 순위의 그림을 보면, 나머지는 어떤 수인지 몰라도, 파란 부분의 노드들과 노란 부분의 노드들 순으로 나온뒤에, 루트 노드가 맨 마지막으로 나온다는 것을 알 수있다. 2. 두 가지의 배열(전위, 중위 순회)로 어떻게 마지막과 같은 형태로 만들 수 있을까?(아래 코드의 sol() 함수 참고...) 부분 트리 단위로 접근해야하며, 이를 재귀적으로 구현한다. 전위 순회 배열을 부분 트리로 이용할 것이며, 중위 순회 배열은 부분 트..
[ BOJ 백준 2250번 - 트리의 높이와 너비 ] 해설 및 코드 https://www.acmicpc.net/problem/2250 목적 입력으로 주어지는 노드의 정보로 트리구조를 형성하고, 각 레벨의 너비가 최대인 레벨과 너비를 구하자. 접근법 1. DFS를 이용하여 왼쪽 자식, 부모, 오른쪽 자식 순으로, 트리의 각 노드에 열번호를 지정한다. 2. 번호를 지정하면서 레벨 정보를 같이 넘겨주어, 각 레벨의 좌우 양 끝 노드의 열 번호를 갱신한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #define LEN 10001 #define f(i,l,r) for(int i=l;i>n; f(i,1,n..
[ BOJ 백준 16437번 - 양 구출 작전 ] 해설 및 코드 https://www.acmicpc.net/problem/16437 목적 N개의 섬들이 트리의 형태로 되어있고, 양이 있는 섬에서 구명보트가 있는 1번 섬까지 양을 몇마리나 살려보낼 수 있는지 구하자. 접근법 1. 경로를 따라 양이 이동할 때, 섬을 탐색하는데 경로의 수를 줄이는 것이 문제의 해결법이다. 2. 어떠한 섬에 양을 먹어야하는 늑대가 더이상 없는 경우, 그 섬을 탐색에서 제외시켜야 한다. 따라서 양이 최대로 이동한 섬의 번호를 제귀적으로 반환하여 경로를 갱신하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #define f(i,l..
[ BOJ 백준 4803번 - 트리 ] 해설 및 코드 https://www.acmicpc.net/problem/4803 목적 트리(사이클이 없는 연결요소)의 개수를 구하자. 접근법 1. disjoint-set 자료구조를 이용하여 트리를 형성하며 사이클 존재여부를 확인한다. 2. 주의할 점 노드쌍의 번호가 같은 것이 입력으로 주어지는 경우도 고려하자. m이 0인 경우 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include #define f(i,l,r) for(int i=l;in>>m&&n){ f(i,1,n)p[i]=i,size[i]=..
[ BOJ 백준 11725번 - 트리의 부모 찾기 ] 해설 및 코드 https://www.acmicpc.net/problem/11725 목적 노드의 쌍이 주어질 때, 부모를 찾아내자. 접근법 1. 노드의 쌍을 입력 받을 때마다, 부모를 알아낼 수 있다면, 즉, 노드 쌍 중의 하나의 부모가 정해진 경우라면, 나머지 노드의 부모를 결정한다. 2. 그렇지 않은 경우 큐에 넣어서 남은 쌍의 부모를 찾아나가는데, 큐에 넣는다면 최악의 경우에 큐의 맨 뒤에 있는 쌍만 처리될 수 있다. 그렇다면 O(N^2)의 시간복잡도가 걸리게 되므로, deque 자료구조를 이용해서 순서를 번갈아가면서 처리해 준다. 3. 다른 접근법으로 노드의 쌍을 입력받아 저장한 뒤에 DFS로 부모를 결정할 수도 있는데, O(N)의 시간복잡도로 AC를 받을 수는 있으나, 메모리가 과도하게 많이 필요하다. 1 2 ..
[ BOJ 백준 1865번 - 웜홀 ] 해설 및 코드 https://www.acmicpc.net/problem/1865 목적 음의 가중치가 존재하는 방향 그래프에서 음의 사이클이 존재하는지 알아내자. 접근법 1. 최단 거리를 구하기 위해 흔히 알려진 3가지 알고리즘 중에 음의 가중치가 존재할 때 최단 거리를 O(VE)의 시간복잡도로 구할 수 있는 '벨만 포드'로 접근하자. 2. 출발지로부터 모든 정점으로의 최단거리를 갱신하면서, 출발지인 정점 1의 최단 거리가 음수가 되는 순간, 음의 사이클이 존재한다는 결론으로 귀결난다. 3. V번째 loop를 돌고 값의 갱신 여부를 확인한다. #include #define f(i,l,r) for(int i=l;itmp){ if(edge[j][1]==1)return true; d[edge[j][1]]=tmp,updated..
[ BOJ 백준 1238번 - 파티 ] 해설 및 코드 https://www.acmicpc.net/problem/1238 목적 각자 마을에서 X로 모였다가 다시 자기 마을로 돌아가는 최단 거리를 구하고, 그중 최대값을 구하자. 접근법 1. 다익스트라 알고리즘을 활용할 수 있는지 묻는 문제이다. X에서 각자 마을로 가는 최단 거리는 흔히 알고있는 다익스트라 알고리즘으로 구할 수 있다. (One to All) 2. 그러나 다익스트라 알고리즘을 이용해서 각자 마을에서 X로 가는 최단 거리를 구하기 위해서는 같은 다른 형식의 그래프가 필요하다. 바로 출발지와 목적지를 바꾼 형태의 그래프이다. (All to One) 3. 결국, 다익스트라 알고리즘에서 거리의 초기화 값을 0으로 주는 주체가, 출발지냐 목적지냐에 따라 구해지는 최단 거리 배열은 One to All과 A..
[ BOJ 백준 11657번 - 타임머신 ] 해설 및 코드 https://www.acmicpc.net/problem/11657 목적 음의 가중치가 존재하는 방향 그래프에서 최단 거리를 구하고 음의 사이클이 존재하는지 확인하자. 접근법 1. 밸만 포드 알고리즘 연습하라고 만든 문제이다. 따라서 목적에 맞는 알고리즘으로 구현한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include #define f(i,l,r) for(int i=l;i>n>>m; f(i,1,m){ int a,b,c;cin>>a>>b>>c; edge[i][0]=a; edge[i][1]=b; edge[i][2]=c; } dist[1]=0;f(i,2,n)dist[i]=I..

티스토리툴바