본문 바로가기

백준47

[백준 - 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] 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.
[백준 - Java] 12100번 : 2048(Easy) 문제 www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 생각할 것 최대 5번 상하좌우 어디든 그 결과 가장 큰 블록의 값 방향에 따른 이동으로 블록들이 한 방향으로 빈 블록 없이, '0' 없이 붙는다. 이때 같은 수의 블록이 만나면 합쳐진다. x 2 두배. 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없다. 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다 생각할 것! 배열 복사 - 그냥 하면 안 .. 2020. 6. 5.
[백준 - Java] 13023번 : ABCDE 문제 더보기 www.acmicpc.net/problem/13023 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 친구 관계가 존재하는지 안 하는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다. 둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 .. 2020. 5. 29.
반응형

티스토리툴바