잡동사니

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

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

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

안녕하세요. yeTi입니다. 오늘은 제가 알고리즘을 공부해봐야겠다고 마음먹은 계기에 대해 공유하고자 합니다. 의문 저는 스스로 의미있는 목표를 가졌을 때 행동하는 성향을 가지고 있습니다. 이러한 이유로 취준생시절 다들 토익공부에 매진할 때 저는 영어 회화를 공부했었고, 단순 암기를 수행하는 교과목을 비선호 했으며 관습에 의해 행해지는 업무를 좋아하지 않습니다. 알고리즘도 비슷하게 생각했습니다. 이전 수학을 배울 때 삶에 무슨 의미가 있는지 이해가 안된것 처럼 알고리즘이 실무에 어떤 개선을 제공하는지 알지 못하여 스스로 동기부여를 할 수 없었습니다. 깨달음 최근에 파트원 중 한분이 알고리즘 문제를 3일동안 풀어보고 파트내에 리뷰를 해준 경험이 있었습니다. 도형이 일치하는 위치의 수를 세는 문제 였는데요. ..