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..

해슁/해싱 Hashing key K를 해시함수값인 h(K)의 위치에 저장하는 자료구조. Direct-Address 테이블에서의 공간 낭비를 줄이면서도, 시간복잡도를 낮추기 위해서 사용하지만 충돌문제가 있으며 이를 해결하기 위한 Chained Hash Table은 시간이 느려질 수 있음. 충돌 다른 Key K인데 해시함수값인 h(K)가 동일한 경우 체인을 이용한 충돌 해결법 중복되는 Key값이 있을 경우 해당 슬롯을 연결리스트로 저장한다. 수행시간 최악의 경우 : O(N) - 모든 Key 값 K가 하나의 해쉬함수 값를 갖는 경우 - 모든 Key 값이 하나의 연결리스트에 저장된 경우 평균의 경우 : O(1+a) - a는 적재율 = 윈소의 개수 / 슬롯(버킷)의 개수 좋은 해쉬 함수란? key가 중복없이 m개..

문제 : 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. 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다. 가장 작은 원소와 가장 큰 원소를 구한다. 가장 작은 원소부터 가장 큰 원소까지의 실제..

계수정렬(Counting Sort) 1. 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다. 가장 작은 원소와 가장 큰 원소를 구한다. 가장 작은 원소부터 가장 큰 원소까지의 실제 숫자를 key(index)로 가지는 배열을 만든다. 배열에서 실제 숫자의 갯수를 센다. 2. 갯수를 하나씩 줄여가면서 해당 위치에 요소를 넣어준다. 의사코드 수행시간 O(N+K) * k는 입력되는 정수의 범위이다. 계수정렬이 유리한 경우 동일한 숫자가 반복되고, MIN과 MAX 값의 범위가 적을 때 JAVA 구현 package algorithm; import java.util.Arrays; public class CountingSort { public int[] countingSort(int[] arr, int min, ..

문제 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) ② 마지막 단계(리프노드) 값 중 최대값을 출력한다. 참조 동적계획법, 위키백과 ..