Lee 코딩 Lee 코딩

구슬 탈출 2 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 61321 18139 9804 26.714% 문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다...

문제 설명 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다. 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 ..

문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. 입출력 예numbersreturn "17" 3 "011" 2 소수인지 판별할 때 에라토스테네스의 체를 이용한다. 즉, 어떤 숫자 n이 소수인지 판별할 때 n을 2부터 n의 루트를 씌운 결과값까지 모두 나눠본..

자바의 Collection에는 Set, List, Map 3가지의 인터페이스가 있다. 1. Set 인터페이스 (집합) : 중복되는 요소를 허용하지 않음. 저장 순서를 유지하지 않음. - Hash Set Hash란? : 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 매핑(변환)하는 것 ex) apple -> eef6ecaf , a -> 89aee2fe Hash Set이란? : Hash와 set이 합쳐진 것으로 set 기능을 통해중복없이 데이터를 저장하고, Hash 기능을 통해데이터가 저장되어 있는지 빠르게 찾을 수 있게 하는 클래스이다 - Linked HashSet : Hash set을 개선한 것으로 중복은 허용하지 않으면서 입력 순서는 보장받고 싶은 경우 사용한다. -Tree set : hash s..

문제 설명 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 제한사항 차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다. 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다. 차량의 진입 지점, 진..

문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다..

크루스칼 알고리즘을 사용하기 위해서는 union-find 알고리즘을 알아야 한다 2022.04.14 - [자료구조, 알고리즘] - Union-Find(합집합 찾기)알고리즘 Union-Find(합집합 찾기)알고리즘 = Disjoint-Set 서로소 집합 알고리즘이라고도 불림. 그래프에서 여러 개의 노드 중 두 개의 노드를 선택해서 이 노드들이 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. - find : 노드의 부모 leeeehhjj.tistory.com - 신장 트리(Spanning tree) : 그래프 내에 있는 모든 정점들을 포함하고, 정점들 간에 서로 연결되며 사이클을 이루지 않는 그래프이다 신장 트리는 정점의 개수가 n개일 때 간선의 개수가 n-1개이다. 이때 간선의 가중치들의 합이 최소가 ..

= Disjoint-Set 서로소 집합 알고리즘이라고도 불림. 그래프에서 여러 개의 노드 중 두 개의 노드를 선택해서 이 노드들이 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. - find : 노드의 부모가 같은지 확인하여 현재 같은 집합에 속하는지 확인하는 것 - union : 두 노드가 각각 포함되어 있는 집합을 합치는 것 1. 처음에 모든 노드들이 연결되어 있지 않을 때 -> 자기 자신이 부모 i 0 1 2 3 4 5 parent[i] 0 1 2 3 4 5 2. 1과 3, 2와 5가 각각 연결되어 있을 때 i 0 1 2 3 4 5 parent[i] 0 1 2 1 4 2 1과 3의 부모를 합쳐주고, 2와 5의 부모를 합쳐 준다(Union) 이 때는 더 작은 값으로 합쳐준다 3. 1-2-3처럼 연..