BOJ
-
[백준 / BOJ] 2933 :: 미네랄알고리즘/BOJ(C++) 2021. 2. 6. 22:56
www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 문제 설명 : 막대기를 한번은 왼쪽에서 오른쪽으로, 다른 한번은 오른쪽에서 왼쪽으로 던질 것이다. 이때 각 방향으로 탐색해서 오면서 처음 만나는 미네랄을 캘 것이다.(미네랄이 있는 곳이 0 처리됨) 미네랄은 클러스터(군집)이 있다. 상하좌우로 연결된 미네랄은 같인 미네랄 클러스터이다. 미네랄을 캐면서 하나의 미네랄이 없어지는데, 이 때 기존에 연결되어 있던 클러스터가 서로 분리 될 수도 있다. 그러면 그 두 클러스터 중 하나..
-
[백준 / BOJ] 16988 :: Baaaaaaaaaduk2 (Easy)알고리즘/BOJ(C++) 2021. 1. 2. 21:35
www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net Easy..? 다들 알고리즘 잘하시나봐요..이게 easy라니 ㅠ 문제 : 우선, 앞에 장황한 쓸데없는 설명은 안읽어도 됩니다. 결론적으로 말하면, 우리는 돌 두개를 놓을 것인데, 돌 두개를 놓아서 상대방 돌을 최대한 많이 따먹어야 합니다. 상대방 돌을 딸 수 있는 조건은 Baduk2에서는 일반적인 바둑과 동일하게 자신의 돌로 상대방의 그룹을 빈틈없이 에워싸면 갇힌 돌을..
-
[백준 / BOJ] 1600 :: 말이 되고픈 원숭이알고리즘/BOJ(C++) 2020. 12. 30. 23:03
www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 설명: - 시작 지점(제일 왼쪽, 제일 위 (H,1))에서 도착지점 (제일 오른쪽, 제일 아래(1,W))까지 이동하는 최단 거리를 찾자 - 이동할 수 있는 방법에는 두가지가 있다. 1. 체스판의 나이트 처럼 이동하는 경우(현 자리에서 8가지) 2. 인접한 칸으로 이동하는 경우(현 자리에서 4가지) - 이 때 1번의 방법으로 이동하는 경우는 최대 K번까지 사용 가능하다. 풀이 / 구현 방법 ..
-
LCA(Lowest Common Ancestor) / 최소 공통 조상 알고리즘알고리즘/개념 정리 2020. 12. 27. 01:26
LCA(Lowest Common Ancestor) / 최소 공유 조상 목차 1. LCA란? 2. O(N) LCA 알고리즘 3. O(logN) LCA 알고리즘 LCA란? LCA란 말 그대로 최소 공유 조상이다. 그래프에서 두 노드 각각의 부모들을 쭉 타고 올라갔을 때 최초로 공유하는 부모를 말한다. 이 예시에서 노드 5와 노드 3의 최초 공유 조상은 1이 된다. 이 경우에 노드 12와 노드3의 최소 공유 조상은 1이 된다. O(N) LCA 알고리즘 자 그러면 이제 LCA 알고리즘을 구현해 봅시다. LCA 구현을 위해 3가지 단계가 필요합니다. 각 노드들의 depth를 구하여 가지고 있는다 ( depth : root 노드부터 자기 노드까지의 거리(깊이)) LCA를 구하려는 두 노드 중 더 깊은 노드의 dep..