본문 바로가기

CS

 (20)
[CS] 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary): 자료구조 이해 및 차이점 분석 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)란?맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)는 모두 키-값 쌍을 저장하고 빠르게 값을 검색하는 자료구조입니다. 이러한 자료구조들은 효율적인 데이터 저장과 접근을 가능하게 하며, 다양한 프로그래밍 언어에서 핵심적인 역할을 합니다. 각 언어와 구현 방식에 따라 사용법이 조금씩 다르기 때문에, 이 글에서는 맵, 해시맵, 딕셔너리의 개념과 차이점을 명확히 설명하고자 합니다.맵(Map) 개념 이해맵(Map)이란?맵(Map)은 키-값 쌍(key-value pair)으로 데이터를 저장하는 추상적인 자료구조로, 키를 통해 데이터를 효율적으로 검색, 추가, 삭제할 수 있습니다. 키(key)는 고유한 식별자 역할을 하며, 이를..
[Algorithm] LIS (Longest Increasing Subsequence) : 가장 긴 증가 부분 수열 알고리즘 이해하기 LIS (Longest Increasing Subsequence) 알고리즘 이해하기프로그래밍에서 가장 긴 증가 부분 수열(Longest Increasing Subsequence, LIS) 문제는 배열 데이터 분석, 최적화, 또는 게임 개발과 같은 다양한 분야에서 중요한 문제로 자주 등장합니다. 그렇다면, 주어진 배열에서 순서를 유지하며 가장 긴 증가하는 수열을 찾으려면 어떻게 해야 할까요?LIS 알고리즘은 이런 문제를 해결하는 강력한 도구입니다. 특히, 배열 내 숫자들의 증가 패턴을 찾아내고, 이를 효율적으로 계산하는 방법을 제시합니다. 이 글에서는 LIS란 무엇인지, 동적 프로그래밍과 이진 탐색을 활용한 구현 방법, 그리고 실무적 활용 사례까지 자세히 다룹니다.LIS 알고리즘의 개념LIS란 무엇인가요?..
[Algorithm] 세그먼트 트리(Segment Tree) 알고리즘 이해하기 출처: https://www.geeksforgeeks.org/euler-tour-subtree-sum-using-segment-tree/세그먼트 트리(Segment Tree) 알고리즘 이해하기프로그래밍을 하다 보면, 종종 배열의 특정 구간에 대한 정보를 빠르게 처리해야 할 때가 있습니다. 예를 들어, 배열의 특정 구간에 대한 합계를 구하거나, 최소값 또는 최대값을 빠르게 찾아야 하는 경우입니다. 이런 문제를 단순한 방법으로 해결하려면 많은 시간이 걸릴 수 있지만, 이를 더 효율적으로 처리할 수 있는 자료 구조가 바로 세그먼트 트리(Segment Tree)입니다.세그먼트 트리(Segment Tree)란?세그먼트 트리는 배열의 구간 정보를 트리 형태로 저장하는 자료 구조입니다. 이를 사용하면 배열의 특정 범..
[Algorithm] Binary Search - 이진 탐색(이분 탐색) 알고리즘 이해하기 이진 탐색(Binary Search) Algorithm안녕하세요! 오늘은 Python을 사용하여 이진 탐색(Binary Search) 알고리즘을 구현하고, 이 알고리즘의 원리, 장단점, 사용 예시 및 적용 기준 등을 함께 알아보겠습니다. 이진 탐색은 다양한 분야에서 활용할 수 있는 매우 유용한 알고리즘입니다. 그럼 시작해볼까요?이진 탐색 소개이진 탐색은 정렬된 배열이나 리스트에서 특정 값을 찾기 위해 사용되는 효율적인 검색 알고리즘입니다. 탐색 범위를 절반으로 줄여 나가면서 빠르게 값을 찾을 수 있습니다. 예를 들어, 사전에서 단어를 찾거나 데이터베이스에서 특정 레코드를 검색할 때 이진 탐색이 유용하게 쓰입니다.이진 탐색의 원리이진 탐색은 배열의 중간 요소를 선택하여, 이 값이 찾고자 하는 값과 같은지 ..
[Algorithm] Union-Find / DSU(Disjoint-Set Union) 알고리즘 이해하기 Union-Find 알고리즘, 또는 Disjoint-Set Union (DSU) 알고리즘은 효율적으로 서로 겹치지 않는 집합들을 관리하고 병합하는 데이터 구조입니다. 이 알고리즘은 네트워크 연결, 이미지 처리, Kruskal의 최소 신장 트리(MST) 찾기 등에 유용합니다.Union-Find / DSU(Disjoint-Set Union) Algorithm 개요Union-Find 알고리즘은 특정 요소들이 서로 연결되어 있는지 확인하고, 연결되지 않은 요소들을 하나의 그룹으로 병합하는 데 사용됩니다. 이 데이터 구조는 주로 그래프 이론에서 동적 연결성 문제를 해결하는 데 사용됩니다.Union-Find 알고리즘 특징효율성: Union-Find 알고리즘은 각 연산에 대해 거의 상수 시간 복잡도를 가집니다.동적 ..
[Algorithm] Dijkstra - 다익스트라 알고리즘 이해하기 안녕하세요! 오늘은 여러분과 함께 다익스트라 알고리즘에 대해 알아보겠습니다. 다익스트라 알고리즘은 그래프 이론에서 매우 중요한 알고리즘 중 하나로, 처음 접하면 다소 복잡해 보일 수 있지만, 차근차근 따라가다 보면 충분히 이해할 수 있습니다. 다익스트라 알고리즘이 무엇인지, 어떻게 동작하는지, 그리고 파이썬으로 어떻게 구현할 수 있는지 자세히 알아보겠습니다.다익스트라 알고리즘 개요다익스트라 알고리즘은 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)에 의해 1956년에 고안된 알고리즘입니다. 이 알고리즘은 하나의 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는 방법을 제공합니다. 특히 가중치가 있는 그래프에서 사용되며, 모든 가중치가 양수인 경우에만 적용됩니다.알고리즘..
[Algorithm] 투 포인터(Two Pointer) 알고리즘 이해하기 Two Pointer Algorithm투 포인터 알고리즘은 배열이나 리스트와 같은 데이터 구조에서 두 개의 포인터를 사용하여 문제를 효율적으로 해결하는 알고리즘입니다. 이 알고리즘은 주로 정렬된 데이터 구조에서 특정 조건을 만족하는 요소를 찾거나, 부분 배열의 합이나 특정 패턴을 찾는 데 사용됩니다. 투 포인터 알고리즘은 시간 복잡도를 줄이는 데 특히 유용하며, 일반적으로 O(n) 시간 복잡도를 가집니다.알고리즘의 작동 원리초기화: 두 개의 포인터를 배열의 시작과 끝에 배치합니다. 이를 통해 배열의 양 끝에서 중앙으로 접근할 수 있습니다. 예를 들어, left 포인터는 배열의 첫 번째 요소를 가리키고, right 포인터는 마지막 요소를 가리킵니다.조건에 따른 이동:두 포인터가 가리키는 요소의 합이 목표 ..
[Algorithm/알고리즘] Greedy - 그리디 알고리즘(탐욕법) 이해하기 그리디(Greedy) 알고리즘, 탐욕법그리디 알고리즘(Greedy Algorithm)은 각 단계에서 최적의 선택을 반복하여 문제를 해결하는 알고리즘입니다. 이 알고리즘은 매 순간 최선의 선택을 하기 때문에 단기적인 최적화를 목표로 합니다. 그러나 항상 전체 문제에 대한 최적해를 보장하지는 않습니다.그리디 알고리즘의 특징탐욕적 선택 속성(Greedy Choice Property): 각 단계에서 현재 상태에서 최적의 선택을 합니다.최적 부분 구조(Opimal Substructure): 문제의 최적해가 부분 문제의 최적해로 구성될 수 있습니다.그리디 알고리즘의 예1. 동전 거스름돈 문제예를 들어, 1원, 5원, 10원, 50원 동전이 있을 때 63원을 거슬러 주는 문제입니다. 그리디 알고리즘은 가장 큰 단위의..

티스토리툴바