전체 글
-
[ Algorithm ] Kruskal & UnionFind 알고리즘자료구조 & 알고리즘/알고리즘 2022. 6. 6. 02:33
크루스칼 알고리즘을 이해하는데 필요한 최소신장트리, UnionFind 알고리즘과 함께 공부 내용을 정리해보려고 합니다. 📌 최소신장트리 최소 비용 신장트리, 최소신장트리, MinimumspanningTree , MST 등등으로 불림 그래프 내의 최소 비용으로 모든 정점을 포함하는 트리 트리라는 말 속 노들들의 연결과 함께 사이클이 존재하지 않음을 내포하고 있음 크루스칼알고리즘과 프림 알고리즘등을 통해 구현가능 📌 크루스칼 알고리즘 코스트, 거리 등에 대해 오름차순으로 정렬한다. 오름차순으로 순회하며 사이클이 발생하지 않는다면 해당 노드를 연결 시킨다. 사이클에대한 판단은 UnionFind 알고리즘을 사용한다. 📌 Union-Find 알고리즘 여러개의 노드가 존재할 때 노드들 끼리 서로 같은 그래프에 속하..
-
[알고리즘] 힙 (programmers.이중우선순위큐)자료구조 & 알고리즘/알고리즘 2022. 5. 14. 15:48
📌 힙 알고리즘 이란? 완전 이진트리 기반의 트리형 자료구조 최댓값, 최소값을 찾아내는데 용이 최대힙 : 부모가 최대 값 , 최소힙 : 부모가 최소값 📌 힙 구조 (최대 힙) 부모 노드가 최대 값을 가짐 같은 깊이 내에서 왼쪽 >= 오른쪽 값 📌 시간 복잡도 힙 추가,삭제 : O(log N) 힙 정렬 : O(N log N) 일반 리스트를 힙 구조로 바꾼 다고 생각했을 때 한개씩 N 개 추가함 == 힙 정렬 시간 복잡도 📍 사용 의의 다른 고급 정렬과 같은 시간복잡도를 가지지만, 최대 최소 원소의 삽입, 삭제가 반복해서 일어나는 경우에 대해서 힙 자료구조를 사용하면 정렬이 아닌 원소 추가, 삭제 시간 복잡도가 적용되서 효율적임 📌 예제 : Programmers.이중 우선순위 큐 힙은 자바, 코틀린 에서 우..
-
[ Git & GitHub] Merge revert 후 재병합Git & Github 2022. 5. 7. 15:59
1. Revert 의 쓰임 (reset 과의 차별성) 취소에 대한 이력을 남길 수 있다. 특정 커밋만 취소할 수 있다. reset 은 특정 과거로의 회기인 반면 revert 은 특정 커밋의 내용만 지움 git resset --hard HEAD~1, git revert [커밋 hash] 2. PR Merge 커밋 지울 때 발생하는 오류 (-m 옵션) $ git revert 1123a41 error: commit 1123a419d52f8eea2273411b4afdfa1914e4195c is a merge but no -m option was given. fatal: revert failed Merge revert 에 대해서는 특별히 -m 옵션을 추가해주어야합니다. - m 옵션에 대한 설명은 아래와 같습니다...
-
[ Android ] 이미지 라이브러리 분석 : GlideAndroid & Kotlin 2022. 5. 4. 19:30
Android 이미지 처리 라이브러리중 하나로 Picasso, Fresco 와 함께 가장 널리 사용되고 있는 라이브러리입니다. 최근에는 Glide와 더불어 Coil이 많이 쓰인다고 합니다. Glide 에서도 caching 에 대해 좀 더 중점적으로 공부하고 정리해보았습니다. 1. Glide 기본 사용법 빌더 패턴을 사용하며 로딩을 위해 3가지의 함수를 호출 public static RequestManager with(Context context) // Glide.java public RequestBuilder load(String string) // RequestManager.java public ViewTarget into(ImageView view) // RequestBuilder.java resiz..
-
[ 프로그래머스 ] 더 맵게 (java)자료구조 & 알고리즘/Programmers 2022. 5. 4. 16:17
문제 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. 제한 사항 scoville의..
-
[ 백준 4963] 섬의 개수 (Kotlin 풀이)자료구조 & 알고리즘/BOJ 문제풀이 2022. 3. 8. 01:07
1.문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 2. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. 3. 출력 각 테스트 케이스에 대해서, 섬의 ..
-
[ 알고리즘 ] 그래프 & DFS , BFS자료구조 & 알고리즘/알고리즘 2022. 3. 8. 00:49
인접행렬에 대한 탐색문제에서 대표적으로 쓰이는 DFS 와 BFS 를 정리해보고자 합니다. 처음에는 DFS , BFS 의 구현에 있어서 잘 이해가 되지 않았지만 틀을 외워서 사용하다 보니 잘 이해가 되었습니다. 저와 같은 분이 계시다면 이 방법을 추천드립니다!! 공통 간선의 데이터를 자료형에 맞게 저장할 수 있어야합니다. 이차원 배열 형태 이차원 배열 + 내부적으로 mutablelis 필요에 따라서 방문한 위치를 표시 할 수 있어야 합니다. 위에서 저장한 이차원 배열을 수정 할 수 도 있음 따로 행렬을 만들어 관리 할 수 도 있음 BFS 너비 우선 탐색으로서 그래프와 트리 탐색 알고리즘이다. 자식 노드보다 형제 노드를 우선적으로 방문한다는 특징을 가진다. 구현의 핵심은 방문할 리스트를 생성하고 방문할 리스..
-
[ Android ] CustomView 필요성 및 구현 방법 (Kotlin)Android & Kotlin 2022. 3. 4. 15:14
1. CustomView의 필요성 기존의 View로는 구현할 수 없은 View 잠금해제 화면 : 터치를 받고 드레그를 인식해서 UI 에 나타내는 VIew 더 정밀한 제어가 필요한 경우 버튼과 일정 거리 이상 가까워지면 반응한단거나 하는 독특한 기능이 필요한 경우 특정 View lifecycle 에 따른 여러 뷰의 조작이 필요한 경우 여러 화면에서 사용하는 경우 재활용 가능 설정화면에서 설명과 토글 버튼 등등이 하나의 세트로 여러번 사용될 때 재활용할 수 있음 custom view 적용시 수정 상황에 대해서 일괄적인 수정이 가능함 CustomView 는 생각보다 복잡하고 손이 많이 가지만 한번 익혀놓으면 재활용성이 뛰어나 많은 도움이 되는 것 같습니다. ( 그러나 위와 같은 필요성이 없는 경우엔 구현에 손..