자료구조 & 알고리즘
-
[ 프로그래머스 ] 가장 먼 노드 (Kotlin )자료구조 & 알고리즘/Programmers 2022. 8. 5. 02:09
https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📌 문제 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를..
-
[ 프로그래머스 ] 정수 삼각형 (JAVA )자료구조 & 알고리즘/Programmers 2022. 6. 12. 19:20
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 📌 문제 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 📌 제한 사항..
-
[ 프로그래머스 ] 섬 연결하기 (Kotlin )자료구조 & 알고리즘/Programmers 2022. 6. 6. 02:34
📌 [ 프로그래머스 ] 섬 연결하기 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]에는 이 두 섬을 연결하는 다..
-
[ 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.이중 우선순위 큐 힙은 자바, 코틀린 에서 우..
-
[ 프로그래머스 ] 더 맵게 (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 너비 우선 탐색으로서 그래프와 트리 탐색 알고리즘이다. 자식 노드보다 형제 노드를 우선적으로 방문한다는 특징을 가진다. 구현의 핵심은 방문할 리스트를 생성하고 방문할 리스..