본문 바로가기

java98

[프로그래머스 - Java] 기둥과 보 설치 (2020 KAKAO BLIND RECRUITMENT) 문제 programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr 1. 기둥과 보를 저장하기 기둥과 보가 같은 (x, y) 좌표에 있을 수 있기에, 둘을 나누.. 2021. 1. 11.
[백준 - 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] 트리 Tree 2 - 이진 트리의 순회(전위, 중위, 후위, 반복, 레벨) / 구현 4. 이진트리의 순회 이진트리에 속하는 모드 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미 이진트리를 순회하는 표준적인 방법에는 전위, 중위, 후의의 3가지 방법이 있다. 루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분된다. 루트를 방문하는 작업을 V 왼쪽 서브 트리 방문을 L 오른쪽 서브트리 방문을 R 루트를 서브 트리에 앞서서 먼저 방문하면 전위 순회 루트를 왼쪽과 오른쪽 서브 트리 중간에 방문하면 중위 순회 루트를 서브 트리 방문 후에 방문하면 후위 순회가 된다. 이진트리에서 각각의 서브 트리 역시 이진트리이다. 전체 트리 순회의 알고리즘을 서브 트리에도 똑같이 적용해 순회한다. -> 문제의 구조는 같고 크기만 작아지는 경.. 2020. 11. 6.
[Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현 1. 트리 1차원 배열로 구현 주로 포화 이진 트리나 완전 이진트리의 경우 많이 쓰이는 방법이다. 그외의 이진트리도 저장이 불가능한 것은 아니지만 기억공간의 낭비가 심해진다. 따라서 포화 이진 트리이진트리 또는 완전 이진트리를 1차원 배열로 구현해보자. 루트 노드는 1부터 시작한다.(인덱스 0은 사용하지 않는 편이 계산을 간단하게 함) 원하는 노드 n개까지 총 n+1 크기의 1차원 배열을 만든다. 그다음 이진트리의 번호대로 노드들을 저장한다. 배열 표현법에서는 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 있다. 노드 i의 부모 노드 인덱스 = i / 2 노드 i의 왼쪽 자식 인덱스 = 2i 노드i의 오른쪽 자식 인덱스 = 2i + 1 /** * @author Gwon Minha * * 루트가 1인 완.. 2020. 11. 5.
[C & Java] 트리 Tree 1 - 트리? / 이진트리? / 트리 표현법 1. 트리(Tree)의 개념 계층적인 자료를 표현하는데 적합한 자료구조 한 개 이상의 노드로 이루어진 유합 집합 A~J를 노드(node) 이들 중 하나의 하나의 노드를 루트(root) 노드라 하고 나머지 노드들을 서브 트리(sub tree)라 한다. 계층적 구조에서 가장 높은 곳에 있는 노드 A가 루트가 됨 루트와 서브트리는 간선(edge)으로 연결됨 ex) {A, B, C, D, E, F, G, H, I, J} 중에서 루트 노드는 A이고 나머지 {B, E, F, G}, {C, H}, {D, I, J}의 3개의 노드 집합들은 A의 서브 트리라 한다. 다시 서브 트리 {B, E, F, G}의 루트는 B가 되고, 나머지 {E}, {F}, {G} 노드들은 다시 3개의 서브 트리로 나뉜다. 나머지도 마찬가지이다.. 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.
728x90
반응형

티스토리툴바