반응형 전체 글52 [알고리즘] 그래프 이론 (서로소 집합) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 서로소 집합 서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미한다. ■ 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 두 종류의 연산을 지원 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. 찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조 라고 불린다. 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정은 다음과 같다. 합집합(Union) 연산을.. 2023. 2. 22. [JavaScript] Template literals(`백틱) 그리고 JSP ■ Template literals 템플릿 리터럴은 내장된 표현식을 허용하는 문자열 리터럴이다. 이중 따옴표나 작은 따옴표 대신 백틱(` `)(grave accent)을 이용한다. 플레이스 홀더를 이용하여 표현식에 넣을 수 있다. ( $ {expression} ) ■ Syntax `string text` `string text line 1 string text line 2` `string text ${expression} string text` tag `string text ${expression} string text` ■ Expression interpolation(표현식 삽입법) 표현식(expression)을 일반 문자열(normal strings)에 삽입하기 위해서 다음의 문법을 사용할 수 있다... 2023. 2. 22. [알고리즘] 최단 경로 알고리즘 (2) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 최단 경로 알고리즘 (1) [알고리즘] 최단 경로 알고리즘 (1) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미 kks2140501.tistory.com ■ 우선 순위 큐(Priority Queue) 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우 우선순위 큐를 이용할 수 있다. Python, C++, Java를 포함한 대부.. 2023. 2. 17. [알고리즘] 최단 경로 알고리즘 (1) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 다양한 문제상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 ■ 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작 현실 세계의 도로(간선)는 음의 간선으로 표현되지 않는다. 다익스트라 최단 경로 알고리즘은 그리디 .. 2023. 2. 16. [알고리즘] 다이나믹 프로그래밍 (2) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 다이나믹 프로그래밍 VS 분할 정복 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다. 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다. 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다. 분할 정복의 대표적인 예시인 퀵 정렬을 살펴보자. 한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않는다. 분.. 2023. 2. 16. [알고리즘] 다이나믹 프로그래밍 (1) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상하는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운, 보텀업)으로 구성 다이나믹 프로그래밍은 동적 계획법이라고도 부른다. ■ 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까? 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다.. 2023. 2. 15. 이전 1 2 3 4 5 6 ··· 9 다음 반응형
