본문 바로가기

[백엔드TIL] SET, TreeSet, LinkedHashSet 개념 Set은 특별한 순서 없이 고유한 값을 저장할 수 있는 추상 자료구조다. 유한 집합의 수학적 개념을 컴퓨터로 구현한 것이다. 대부분의 다른 컬렉션 유형과 달리 집합에서 특정 요소를 검색하는 대신 일반적으로 집합의 구성원 자격에 대한 값을 테스트한다. 일부 집합 자료구조는 구성된 후 변경되지 않는 고정 집합 또는 고정 집합을 위해 설계됐다. 정적 집합은 주어진 값이 집합에 있는지 확인하거나, 랜덤하게 값을 열거하는 것과 같은 요소에 대한 쿼리 작업만 허용한다. 동적 또는 변경 가능한 집합(mutable set)이라 하는 다른 변형을 사용하면 집합에서 요소를 삽입, 삭제할 수도 있다. 다중 집합(multiset)은 요소가 여러 번 나타낼 수 있는 특별한 집합이다 고유한 값을 저장한다면 중복되는 값은 집어넣을.. 더보기
[Java] K번째 수 구하기 (선택정렬 활용) 문제 K번째수 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 array의 길이는 1 이상 100 .. 더보기
[백엔드TIL]다익스트라 알고리즘(Dijkstra Algorithm) 원리 [Java]다익스트라 알고리즘(Dijkstra Algorithm) Algorithm/그래프&최단경로 2021. 3. 12. 00:40 *다익스트라 알고리즘(Dijkstra Algorithm) -> 다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다. -> 초기 모델은 O(V^2)의 시간복잡도를 가졌다. 이후 우선순위 큐 등을 이용한 고안된 알고리즘이 탄생했고, 현재는 O((V+E)log V)의 시간복잡도를 가지고 있다(만일 연결 그래프라면 O(ElogV)까지 시간 복잡도를 줄일 수 있다고 한다). 일반적으로는 그래프가 희소 그래프인 경우에 우선순위 큐를 이용하는 것이 낫다고 한다. ※음의 가중치를 가지면 안되는 이유.. 더보기