Manta Ray's

문제 : (1) All Paths From Source to Target - LeetCode All Paths From Source to Target - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 : DFS 구현 JAVA import java.util.LinkedList; import java.util.List; import java.util.Queue; class Solution { public List allPathsSourceTarget(int[]..

문제 https://leetcode.com/problems/find-center-of-star-graph/ Find Center of Star Graph - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 ① edges는 노드의 갯수-1 개 만큼만 들어오기 때문에 모든 노드가 1개의 노드와 연결되어 있는... 중앙 집중형 네트워크 그래프이다. ② 즉 모든 노드과 연결되는 노드를 구하면 된다. 구현 JAVA [그래프를 연결리스트로 구현] import java...

문제 : 프로그래머스 여행경로 https://programmers.co.kr/learn/courses/30/lessons/43164?language=java 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 풀이 ① DFS로 모든 경로 목록 구하기 ② 알파벳 순서로 정렬 후 가장 앞의 것을 출력 import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Sta..

문제 : https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 풀이 : ① DFS를 이용핸 도달할 수 있는 모든 경로를 탐색. ② 탐색 한 경로의 최소값을 출력 2021.09.19 - [알고리즘/알고리즘] - 깊이 우선 탐색 Depth-first search 깊이 우선 탐색 Depth-first search 깊이 우선 탐색 시작 노드와 직접 연관된 하위 노드 끝까지 모두 ..

문제 : https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 풀이 : BFS를 이용해 지점을 잇는 경로를 탐색 ① 지점을 잇는 경로를 탐색한다. ② ①에서 탐색되지 않은 지점를 시작으로 재탐색한다. * computer[i][i] 가 1이므로, 어느 지점과 연결되지 않으면 자기자신하고만 연결되는 경로 (네트워크) 1개가 세어진다. 2021.09.19 - [알고리즘/알고리즘] - 너비 우선 탐색 Breath-f..

문제 : 해쉬 셋 구현하기 Design HashSet - LeetCode Design HashSet - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 구현 JAVA class MyHashSet { int[] set; public MyHashSet() { set = new int[1000001]; } public void add(int key) { set[key] = 1; } public void remove(int key) { set[key] = 0; } pub..

문제 : https://leetcode.com/problems/height-checker/ Height Checker - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 : 선형시간 정렬 (계수정렬) 2021.10.05 - [알고리즘/알고리즘] - 선형시간 정렬 선형시간 정렬 계수정렬(Counting Sort) 1. 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다. 가장 작은 원소와 가장 큰 원소를 구한다. 가장 작은 원소부터 가장 큰 원소까지의 실제..

문제 https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 : 동적 계획법 Dynamic Programming ① 2번째 줄부터 시작 이전 단계 값들 중에 가장 큰 값과 현재 갑을 더해서 저장한다. 이전 단계 값 ( y = 현재 위치 or y = 현재위치 -1) ex) (0,1)의 이전 단계 값 : (0,0) / (1,1)의 이전단계값 : (0,0) / (2,1)의 이전단계 값 : (1,1), (1,0) ② 마지막 단계(리프노드) 값 중 최대값을 출력한다. 참조 동적계획법, 위키백과 ..

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 풀이 : 동적 계획법 Dynamic Programming ① N이 8개 이상이면 -1을 반환하도록 했으므로, N이 최대 8개일때까지만 계산을 수행 ② N을 0~x개 사용했을 때의 결과값 각각 저장함. - 1) N을 0~x개 만큼 이어붙인 자연수를 저장함. - 2) 1)에서 저장한 케이스를 조합해 사칙연산을 수행 (N*N, N/N, NN*N .... ) N3 = N1 사칙연산 N2 와 N2 사칙연산 N1, NN 사칙연산 N - 3) 2)의 결과에서 number(구하려는 값)이 나오면 연산을 중단하고 N의 갯수를 출력함. [케이스 예시] ① N..

https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이 : 탐욕 알고리즘 ① 구간 시작위치가 가장 먼저인 구간부터 차례로 비교하면서 카메라의 설치 구간을 탐색 ② 카메라가 설치된 구간과 route(자동차 통과구간)를 비교하면서 카메라 설치 구간을 줄여나감. ③ 겹치는 구간이 없으면 자동차 통과구간을 카메라 설치구간에 추가함. 구현 JAVA import java.util.*; public int solution(int[][] routes) { //먼저 빠져나가는 거리 순으로 정렬 Arrays.sort(routes, (..