생각 생각

https://acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 2263이 중위와 후위를 전위로 바꾸는 것이었다면, 4256은 전위와 중위를 후위로 바꾸는 문제였다. index를 기준으로 푸는 것은 2263번 문제와 동일했다. 다시 풀어도 왼쪽 자식 트리와 오른쪽 자식 트리의 길이를 어떻게 나타내야 하는지가 헷갈렸다. 이 문제에서 결국 푸는 데 가장 중요한 단서는 중위 순회식이다. 전위와 후위 표기식에서는 각각 맨 앞, 맨 뒤에 루트가 나오니 그 루트를 중..

https://acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 2493번 탑 계열의 스택 문제마다 어려워했다. 이것도 마찬가지로 꽤 어렵게 푼 문제였다. 다른 것들보다도 이런 문제를 풀 때 우선순위가 있으면 언제 pop을 해줘야 하는지가 너무 헷갈린다. 이 문제의 경우 우선순위가 명확하다. 괄호 연산이 최우선, 그 이후가 곱셈 나눗셈, 마지막이 덧셈 뺄셈이다. 괄호가 끝나면 새 괄호가 안에서 또 시작하지 않는 이상 무조건 스택 안에 남아있는 것들을 전부 빼내주어..

https://acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다 풀어놓고 이상한 곳에서 해멘 문제. 다익스트라 구현은 이제 조금 적응되었다. 두 점을 거쳐서 도착점에 도착한다면 가는 길의 경우의 수는 3개다. 시작점이 1, 도착점이 n, 두 점이 p1,p2이다. 1 -> p1 -> p2 -> n (처음으로 p1을 방문하는 경우) 1 -> p2 -> p1 -> n (처음으로 p2를 방문하는 경우) 1 -> n -> p1 ..

https://acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 전적으로 자력으로 처리한 문제였다. 더 간단한 방법이 있을 것이라고는 생각했는데, 실제로 있었다. 내가 푼 방법은, 파티에 참여한 모든 사람들이 서로를 향한 간선을 만들도록 하고, 진실을 알고 있는 사람에 대해 bfs를 시행해 진실을 알고 있는 사람과 만난 사람을 모두 구해 그런 사람이 없는 파티를 +=1 하는 것이었다. ​ 윗 부분은 간선을 만드는 과정이다. 아래 부분은 만든 간선을 바탕으로 bfs를 시행하는 과..

https://acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 평범한 다익스트라 문제. 지난 번 코딩페스티벌에 유사한 문제가 있었는데 틀리게 풀었다는 것을 오늘에야 알았다. 가는 길, 오는 길 해서 두 번 다익스트라를 해 주면 된다.

https://acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 금방 풀 수 있을 줄 알았는데, 메모리 제한때문에 생각보다 많이 헤맨 문제. 처음에는 원론적으로 이렇게 풀었다. 중위 순회 결과와 후위 순회 결과의 서브 트리를 각각 넣어가며 재귀적으로 풀었는데, 이렇게 풀려면 결국 매번 리스트를 만들어 넣어야 하니 메모리 부족이 떴다. ​ 그래서 결과적으로 찾은 풀이 방법은 똑같이 풀되, 리스트를 직접 만드는 게 아니라 index만 전달하기였다. 그러나 이렇게 하니 이번에는 시간 초과가 뜨더라...

​

https://acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 이진 트리 문제이다. 트리의 지름 문제에서는 트리가 직접 주어졌던 반면 여기서는 숫자를 전위 순회 순서로 주고 트리를 다시 후위 순회 순서로 출력하는 문제였다. 재귀 함수를 짜되, 시작점이 끝 점보다 커지면 끝나고, 시작점보다 현재 점이 크면 그때부터 그 지점을 경계로 후위 순회를 시작한다.