본문 바로가기

알고리즘 문제/백준50

[백준 - Java] 15681번 : 트리와 쿼리 문제 www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 설명 * 입력받을 때 Scanner로 받으면 시간 초과에 메모리 초과까지 난다;;; 꼭 BufferedReader와 같은 Buffer로 입력받아야 함!! * 이건 설명할게 따로 없다... 트리와 쿼리 문제 스크롤하다 보면 힌트라는 카테고리에서 이 문제를 그래프, 트리, 서브 트리 등 아주 자세히 설명해준다... 진짜 나도 어떻게 풀어야 할지 막.. 2021. 1. 6.
[백준 - Java] 15900번 : 나무 탈출 틀렸습니다!!! 나는 결국 다른 사람들의 풀이를 보고 문제를 해결했다ㅠㅠ 처음에 A가 고르고, B가 고르고 모든 경우를 다 따지고, 부모 노드로 바꿨다가. 노드를 삭제했다가 별별일을 다 하다 너무 시간이 오래 걸려서 포기함... 답을 봤더니 너무 허망했음ㅋㅋㅋㅋ역시 사람은 머리를 잘 굴려야함! 풀이는 아래에!! * 아 참 Scanner로 입력받으면 시간 초과!!!! 문제 www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 설명 게임은 리프 노드부터 시작되고, 리.. 2021. 1. 5.
[백준 - Java] 3584번 : 가장 가까운 공통 조상 문제 www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 백준 11437번 LCA 문제와 같은 문제이다. [백준 - Java] 1437번 : LCA 하지만 1을 루트 노드로 주는 11437과는 다르게 루트 노드를 찾아야 하는 점이 다르다. 그래서 코드에서 루트 노드를 찾는 부분만 추가하고, 나머지는 똑같다. 루트 노드는 부모가 없다. 따라서 문제에서 A가 B의 부모로 무조건 주어지기 때문에 부모가 없는 노드를 .. 2021. 1. 5.
[백준 - Java] 11437번 : LCA 최소 공통 조상 문제 www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net LinkedList를 통해 각 정점들을 저장하고 연결해준다. 인접 리스트로 구현된 트리를 DFS로 탐색한다. 탐색하면서 각 노드의 깊이와 부모 노드를 배열에 저장한다. 왜냐? 각 노드의 부모 노드 값을 저장해두면, 두 개의 노드가 어디에 있든 따라 올라가다 보면 최소 공통 조상을 찾을 수 있기 때문! 깊이를 맞추는 이유는 그게 비교하기 편함! (같은 깊이에서 시작해야 만나는 순간을 찾기가 쉬움) 정점.. 2021. 1. 4.
[백준 - Java] 2533번 : 사회망 서비스(SNS) 문제 www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 설명 자신이 얼리어답터인지, 아닌지 2가지의 경우로 나누어 얻을 수 있는 최솟값을 구하는 것이다. 1. 자신이 얼리어답터가 아니라면, 인접 노드들은 모두 얼리어답터여야 한다. (그래야 어떻게든 아이디어 전파가 가능) 2. 자신이 얼리어답터라면, 인접 노드들은 얼리어답터일수도 있고, 아닐 수도 있다. 이를 위해 인접리스트를 통해 정점들을 표현해주었다. 그리고 1을 루트로 가정하고, 1이 얼리어답터인지 .. 2021. 1. 3.
[백준 - Java] 1991번 : 트리 순회 문제 www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 전체 코드 import java.io.*; import java.util.*; class Node { char data; Node left; Node right; Node(char data) { this.data = data; } } class Tree { Node root; //루트 노드 처음엔 null 상태 public void createNode(char data, char leftData, c.. 2020. 11. 3.
[백준 - Java] 14502번 : 연구소 (삼성 SW 역량 테스트 기출 문제) 문제 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 설명 안전 영역 크기의 최댓값을 얻는 것이 목표. 그러기 위해선 1. 연구소에 3개의 벽을 세울 수 있는 모든 경우를 따진다. 각 경우에 따라 2. 바이러스를 퍼뜨린 뒤, 3. 가장 안전 영역이 큰 경우를 구해야 한다. main 메서드 - 연구소 map 구성하기 public static void main(String[] args) throws IOException { BufferedReader br = new Buff.. 2020. 10. 16.
[백준 - Java] 19236번 : 청소년 상어 (삼성 SW 역량 테스트 기출 문제) 문제 www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 공간과 물고기 표현 상어가 이동하며 먹을 수 있는 물고기 번호의 합의 최댓값을 구하는 문제이다. 조건에 따라 구현해보자. 4 ×4 크기의 공간이 있고, 크기가 1 ×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. -> 이차원 배열을 map을 만들어 공간을 나타낸다. -> map에는 물고기의 번호가 저장된다. (1 .. 2020. 10. 13.
[백준 - Java] 17143번 : 낚시왕(삼성 SW 역량 테스트 기출 문제) 문제 www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 삼성 SW 역량 테스트 기출문제이다. 문제에서 요구하는대로 구현하면 되는 시뮬레이션 문제이다. 구현 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판. 낚시왕이 1초에 한 칸씩 열을 이동하며 상어를 잡는다. (가장 오른쪽 열, C칸에 도착하면 이동 멈춤 -> 낚시 종료) 1초 동안 일어나는 조건을 고려해 C초까지 낚시를 하는 것이다! 낚시의 조건은 아래와 같고 이를 바탕으로 총 낚.. 2020. 10. 13.
[백준 - Java] 16236번 : 아기 상어 문제 더보기 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1 ×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수.. 2020. 6. 16.
반응형

티스토리툴바