728x90 ps 공부 정리3 BOJ - 3584번, 가장 가까운 공통 조상 [LCA] 이번에 풀이한 문제는 3584번 LCA(Lowest Common Ancestor), 최소 공통 조상 문제입니다. 문제 제목에서 알 수 있듯이, 트리 정보를 입력받은 후에 두 개의 노드의 최소 공통 조상을 찾으면 되는 문제입니다. 최소 공통 조상은 위 그림과 같이 부모 노드로 타고 올라갈 때, 가장 높이가 낮으면서, 두 개의 노드의 공통 조상인 노드입니다. 이러한 유형을 풀어봤던 것 같은데, 각 노드의 부모 노드 정보를 저장한 뒤에 이를 활용해야 한다는 부분까지는 생각이 났는데, 정확한 알고리즘이 생각나지 않아 다른 분들의 풀이를 참고했습니다. 더 효율적인 방법이 있겠지만, 일단 이 문제에 적용할 수 있는 가장 쉬운 풀이는 하나의 노드가 먼저 부모를 거슬러 올라가며, 방문 처리하며 탐색한 뒤에 두 번째 노.. 2023. 1. 17. 백준 - 12100번 2048 - easy 문제 풀이 정리 이번에 풀어본 문제는 solved.ac 기준 class 5에 속하는 2048문제입니다. 다들 알고 계시는 2048게임을 5번까지 시뮬레이션했을 때 결과로 뽑아낼 수 있는 최대의 수를 찾는 문제로 원래 2048 게임은 한 번 이동이 발생할 때마다 새로운 블록이 등장하는 것과 다르게 이 문제에서는 새로운 블록이 등장하지 않는 전제 하에 시뮬레이션을 구현하면 됩니다. 문제 링크 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048 게임은 여기서 플레이 해보실 수 있습니다! 2048 J.. 2022. 10. 13. 백준 - 14938번, 서강그라운드 문제 풀이 - (C++) 이번에는 solved.ac에서 적당한 난이도의 문제를 고르다 class 4로 분류된 14938번 서강그라운드 문제가 적당히 풀만하지 않을까?라는 생각으로 풀어봤습니다. 난이도는 solved.ac 기준 골드 4로 class 4에 속한 평균적인 문제 같습니다. 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제 설명 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강.. 2022. 9. 30. 이전 1 다음 728x90
