잡동사니

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부 중 동적계획법 (Dynamic Programming)에 대해 학습한 내용을 공유하려고 합니다. 강의 : 권오흠 교수님의 2015 봄학기 알고리즘 개요 동적계획법 (Dynamic Programming)은 순환식을 기반으로 문제를 해결하는 기법입니다. Memoization(캐싱)도 동적계획법 (Dynamic Programming)의 일부로 볼 수 있는데요. 두 방식의 차이점은 Memoization(캐싱)은 top-down 방식을 취하며 캐싱되지 않은 subproblem만 풀어나가는 반면, 동적계획법 (Dynamic Programming)은 bottom-up방식으로 필요한 계산을 사전에 해나가는 방식으로 볼 수 있습니다. 동적계획법 (Dynamic Progra..

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부 중 압축(compression)에 대해 학습한 내용을 공유하려고 합니다. 강의 : 권오흠 교수님의 2015 봄학기 알고리즘 개요 압축을 하는 방식에는 무손실(lossless) 압축과 손실(lossy) 압축이 있습니다. 무손실 압축을 사용하는 경우는 text나 수치 데이터와 같이 디코딩시 원본 데이터가 온전히 보전되는 압축 방식을 말하며, 손실 압축을 사용하는 경우는 이미지나 영상 데이터와 같이 사람이 인지하지 못하는 수준내에서 디코딩시 원본 데이터가 손실되는 압축 방식을 말합니다. Huffman coding Huffman coding은 무손실 압축을 위한 방식 중 하나로 동일한 데이터에 대한 빈도를 기반으로 가변길이 데이터로 치환하는 방식을 사용합니다. ..

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부 중 최단경로(Shortest Path)에 대해 학습한 내용을 공유하려고 합니다. 강의 : 권오흠 교수님의 2015 봄학기 알고리즘 개요 가중치 그래프에서 경로상의 모든 엣지의 가중치의 합이 가장 작은 경로 (u, v)를 찾는 방법입니다. 이전 그래프 탐색 - BFS에서 그래프에서 BFS를 활용하면 최단 경로의 길이를 구할 수 있다는 내용이 있습니다. 현재 다루는 최단경로(Shortest Path)와 차이점은 그래프에서 BFS 탐색시 찾을 수 있는 최단 경로의 길이는 엣지의 갯수이고 최단경로(Shortest Path)는 가중치의 합이라는 것입니다. 최단경로문제는 다음과 같은 유형이 있습니다. Single-source: 하나의 출발노드에서 다른 모든 노드까지..

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부 중 최소비용신장트리(Minimum Spanning Tree)에 대해 학습한 내용을 공유하려고 합니다. 강의 : 권오흠 교수님의 2015 봄학기 알고리즘 개요 최소비용신장트리는 무방향 가중치 그래프에서 모든 노드를 이었을 때 가중치가 가장 적은 엣지들의 부분집합을 찾는 방식입니다. 이 때, MST(Minimum Spanning Tree) 는 유일하지 않기 때문에 선별한 엣지들을 많은 MST들 중 일부인 부분집합 이라는 표현을 한다. 공학적으로는 계층적 구조의 연결을 트리(rooted tree)라고 인식하지만 수학적으로는 싸이클이 없는 연결된(connected) 무방향 그래프를 트리라고 합니다. 게다가 MST 문제에서 싸이클이라는 것은 중복 경로라는 의미로 ..

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부 중 그래프(graph)에 대해 학습한 내용을 공유하려고 합니다. 강의 : 권오흠 교수님의 2015 봄학기 알고리즘 개요 그래프는 노드와 엣지, 두 집합으로 구성된 자료구조입니다. 그래프의 종류에는 무방향 그래프, 방향 그래프, 가중치 그래프가 있습니다. 그래프는 인접 행렬과 인접 리스트로 표현 가능합니다. 인접 행렬은 n*n 크기의 2차원 행렬로 표현하는 방식으로 저장 공간은 O(n^2)의 크기를 가지고, 인접한 모든 노드를 찾는 시간은 O(n), 엣지의 존재 여부를 찾는 시간은 O(1)의 특성을 가집니다. 인접 리스트는 노드 집합을 표현하는 1차원 배열과 각 노드마다 인접한 노드들을 연결 리스트로 표현한 방식입니다. 저장 공간은 O(n+m)의 크기를 가..

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부 중 해싱(hashing)에 대해 학습한 내용을 공유하려고 합니다. 강의 : 권오흠 교수님의 2015 봄학기 알고리즘 개요 해쉬 테이블(hash table)은 트리(tree)와 같이 dynamic set을 구현하는 효과적인 방법 중 하나입니다. 적절한 가정하에 Insert, Delete, Search 연산의 시간복잡도는 O(1)을 가지지만 최악의 경우에는 O(n)을 가집니다. Hash Table 해시 테이블은 일반적으로 일차원 배열을 활용하여 데이터를 관리합니다. 이 때, 배열의 인덱스가 특정 데이터의 키를 해시한 값을 활용하여 키를 해시하는 연산 시간만 주어지면 데이터에 바로 접근할 수 있는 특징을 가지고 있습니다. 하지만, 데이터의 크기가 해시 테이블의..

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부를 해보면서 공부하는 것이 안하는 것보다 프로그래밍을 함에 있어서 도움이 된다고 느낀점을 공유해보고자 합니다. 코테를 위한 알고리즘? 흔히들 알고리즘 공부라 하면 코테(코딩 테스트)를 준비하기 위해서 한다고 인식합니다. 저도 그랬었고 주변 의견을 들어봐도 그렇고, 알고리즘 공부를 한다고 해서 실무에 어디다가 쓰느냐. 좋은 기업에 입사하기 위해, 코테를 통과하기 위해, 알고리즘을 공부한다는 의견이 대다수 입니다. 하지만 최근 제 경험은 개발을 위한 사고를 하는데 도움이 된다고 느꼈습니다. 사고력 훈련 이전 글에서도 알고리즘을 공부해야하는 이유 라는 제목으로 알고리즘 공부의 필요성에 대해 공유한적이 있는데요. 해당 글에서는 논리적인 생각의 코드로써 직관적인 표..

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부 중 트리(tree)에 대해 학습한 내용을 공유하려고 합니다. 강의 : 권오흠 교수님의 2015 봄학기 알고리즘 트리 (Tree) 트리는 계층 구조를 표현하는 자료구조입니다. 트리에서 사용하는 용어는 다음과 같습니다. 노드 (node) 링크 (link) 루트 (root) 부모 (parent) 자식 (child) 형제 (sibling) 리프 (leaf) 조상 (ancestor) 자손 (descendant) 부트리 (subtree) 레벨 (level) 높이 (height) 이진트리 (Binary Tree) 이진트리는 자식 노드가 최대 2개인 트리를 말합니다. 이진트리의 종류에는 full binary tree 와 complete binary tree가 있습니다...

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부 중 정렬(sort)에 대해 학습한 내용을 공유하려고 합니다. 강의 : 권오흠 교수님의 2015 봄학기 알고리즘 개요 정렬은 프로그래밍에서 기본적이고 중요한 개념입니다. 저는 강의에서 공감을 했던 부분이 데이터를 탐색함에 있어서 정렬된 데이터를 유지하느냐 그렇지 않느냐에 따라 시간복잡도가 다를 수 있다는 것을 깨닫게 되었기 때문입니다. 조금 더 구체적으로 얘기해보면 무작위 순서를 가진 데이터에서도 순차적으로 데이터를 탐색하며 원하는 결과를 얻을 수도 있지만, 데이터가 정렬되어 있다면 탐색을 효율적으로 할 수 있기 때문입니다. 한 예시로 정렬되지 않은 배열 [5, 8, ..., 1]에서 7이 위치한 인덱스를 찾고 싶으면 첫 번째 원소부터 탐색을 해야하지만 정..

안녕하세요. yeTi입니다. 오늘은 알고리즘 강의의 시작인 recursion 에 대한 정보를 공유하고자 합니다. 의문 강의를 시작하면서 다음과 같은 의구심이 들었습니다. 알고리즘을 공부하는데 왜 recursion 부터 시작할까?? 문제를 푸는 방식에 대한 강의가 중요한거 아닌가?? 문제의 부분화 Recursion 은 프로그래밍에서는 재귀함수를 표현하는 의미로 쓰입니다. Recursion 은 문제를 해결하는 범위를 축소시키는 사고를 하기위한 방식이라는 느낌을 받았습니다. 예를 들어, 다음과 같은 문제가 주어진다면 주어진 n개의 수들에 총합을 구하라 직관적인 해결책은 절차적인 방식으로 반복문을 활용하여 n 회 반복하며 모든 수의 총합을 구하는 방식입니다. 하지만 recursion 을 활용하면 다음과 같이 사..