본문 바로가기

Solved.ac26

[BOJ] 백준 11437번: LCA www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net LCA는 최소 공통 조상 (Lowest Common Ancestor)로 두 노드를 잇는 가장 짧은 경로 중 깊이가 가장 얕은 노드입니다. 아래 트리에서 빨간 노드와 하늘색 노드의 LCA는 초록색 노드가 됩니다. "트리 노드의 부모 노드는 유일하므로 루트를 향해 거슬러 올라가면서 가장 처음으로 공통된 노드를 찾자!" 아이디어를 기반으로 좀 더 빠르게 위로 올라갈 수 없을까 하는 고민이 생기게 됩니다. 효율.. 2020. 9. 22.
[BOJ] 백준 2467번: 용액 www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net -10억~10억 사이의 용액의 특성값이 오름차순으로 주어지며, 주어진 특성값 중 서로 다른 용액 A, B를 선택했을때 특성값의 합이 0에 가까운 조합을 출력하는 문제입니다. 예를 들어 -98 1 2 97 의 네 가지 용액이 주어진다면 -98과 97의 특성값을 같는 두 용액을 선택하는 것이 답이 됩니다. 즉 절대값이 가장 작은 조합을 고르는 문제로 생각할 수 있습니다. i번째 용액을 A로 고정시키면, 용액 .. 2020. 9. 22.
[BOJ] 백준 1697번: 숨바꼭질 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 순간이동이 현재 좌표에 2배까지 가능하므로 최대 배열 크기를 20만으로 잡고, dp[i]는 i 좌표로 이동하는데 걸리는 최소 시간이라고 보면 아래 코드와 같이 해결 가능합니다. 먼저 n보다 작은 좌표 위치는 -1 로 이동할 수밖에 없으므로 최소 시간은 n - i로 초기화해주고 과정 1. 반복적으로 +1 이동하는 경우 과정 2. 2배 이동하는 경우 두 가지 경우에 대하여 최솟값을 .. 2020. 9. 7.
[BOJ] 백준 14500번: 테트로미노, 브루트포스, 필터링 www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 주어진 블록모양에 대하여 회전, 반전 한 상대적인 좌표 위치를 필터로 저장하여 (아래 첨부했으니 고통을 덜어가세요.) 모든 좌표에 대하여 총 19가지의 필터를 씌워 필터내의 숫자의 합 중 제일 큰것을 찾아가면 됩니다. int filter[19][2][4] = { {{0,0,1,1},{0,1,0,1}}, {{0,0,0,0},{0,1,2,3}}, {{0,1,2,3},{0,0,0,0}}, {{0,1,2,2},{0,.. 2020. 9. 7.

티스토리툴바